Discussion:
Mapping x86/x64/C to a Turing equivalent abstract model of
(too old to reply)
olcott
2020-09-05 17:14:58 UTC
Permalink
There is no possible way for any concrete implementation of "C" to be
made equivalent to a Turing machine. If we used every atom in the whole
universe to each store a single binary digit we would still be woefully
short of unlimited memory.

We can override and supersede the standard "C" and map its syntax and
semantics to an abstract model of computation that is Turing equivalent.
The RASP model of computation is a model that "C" can be mapped to.
https://en.wikipedia.org/wiki/Random-access_stored-program_machine

A variation of the RASP model is shown below that the x86/x64 language
maps to. Since it is already known that "C" maps to the x86/x64 concrete
models of computation we know that "C" maps to the following abstract model:

Instruction
: INTEGER ":" OPCODE // Address:Opcode
| INTEGER ":" OPCODE INTEGER // Address:Opcode Operand
| INTEGER ":" OPCODE INTEGER "," INTEGER // Address:Opcode
Operand, Operand
HEXDIGIT [a-fA-F0-9]
INTEGER {HEXDIGIT}+
OPCODE HEXDIGIT{4}

The above abstract machine maps the x86 language to machines with a
fixed pointer size of the largest unlimited integer address that is
actually needed by the computation. This provides the basis for
recognizing the set of Turing equivalent x86/x64/C computations.

Turing equivalent computations derive equivalent output or fail to halt
on equivalent input between the concrete machine and its Turing machine
equivalent.

Some machines that (for example) count to infinity and store the counter
at each increment do not map to any finite computation.
--
Copyright 2020 Pete Olcott
Terje Mathisen
2020-09-05 19:06:31 UTC
Permalink
Please, no more!

Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(

Terje
Post by olcott
There is no possible way for any concrete implementation of "C" to be
made equivalent to a Turing machine. If we used every atom in the whole
universe to each store a single binary digit we would still be woefully
short of unlimited memory.
We can override and supersede the standard "C" and map its syntax and
semantics to an abstract model of computation that is Turing equivalent.
The RASP model of computation is a model that "C" can be mapped to.
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
A variation of the RASP model is shown below that the x86/x64 language
maps to. Since it is already known that "C" maps to the x86/x64 concrete
Instruction
     : INTEGER ":" OPCODE                     // Address:Opcode
     | INTEGER ":" OPCODE INTEGER             // Address:Opcode Operand
     | INTEGER ":" OPCODE INTEGER "," INTEGER // Address:Opcode
Operand, Operand
HEXDIGIT [a-fA-F0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}
The above abstract machine maps the x86 language to machines with a
fixed pointer size of the largest unlimited integer address that is
actually needed by the computation. This provides the basis for
recognizing the set of Turing equivalent x86/x64/C computations.
Turing equivalent computations derive equivalent output or fail to halt
on equivalent input between the concrete machine and its Turing machine
equivalent.
Some machines that (for example) count to infinity and store the counter
at each increment do not map to any finite computation.
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
olcott
2020-09-05 19:20:54 UTC
Permalink
Post by Terje Mathisen
Please, no more!
Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(
You did not bother to notice that I concurrently refer to x86/x64?
I am referring to x86/x64/C as a single concrete model of computation.
Post by Terje Mathisen
Terje
Post by olcott
There is no possible way for any concrete implementation of "C" to be
made equivalent to a Turing machine. If we used every atom in the
whole universe to each store a single binary digit we would still be
woefully short of unlimited memory.
We can override and supersede the standard "C" and map its syntax and
semantics to an abstract model of computation that is Turing
equivalent. The RASP model of computation is a model that "C" can be
mapped to.
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
A variation of the RASP model is shown below that the x86/x64 language
maps to. Since it is already known that "C" maps to the x86/x64
concrete models of computation we know that "C" maps to the following
Instruction
      : INTEGER ":" OPCODE                     // Address:Opcode
      | INTEGER ":" OPCODE INTEGER             // Address:Opcode Operand
      | INTEGER ":" OPCODE INTEGER "," INTEGER // Address:Opcode
Operand, Operand
HEXDIGIT [a-fA-F0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}
The above abstract machine maps the x86 language to machines with a
fixed pointer size of the largest unlimited integer address that is
actually needed by the computation. This provides the basis for
recognizing the set of Turing equivalent x86/x64/C computations.
Turing equivalent computations derive equivalent output or fail to
halt on equivalent input between the concrete machine and its Turing
machine equivalent.
Some machines that (for example) count to infinity and store the
counter at each increment do not map to any finite computation.
--
Copyright 2020 Pete Olcott
Frank Kotler
2020-09-06 04:50:10 UTC
Permalink
Post by Terje Mathisen
Please, no more!
Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(
I fear I made an error on approving this in the first place. I saw a
reference to "x86" and thought "well maybe..." But we are not about C
here... Hopefully it will die put quietly...

Best,
Frank
[moderator]
olcott
2020-09-06 05:17:07 UTC
Permalink
Post by Frank Kotler
Post by Terje Mathisen
Please, no more!
Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(
I fear I made an error on approving this in the first place. I saw a
reference to "x86" and thought "well maybe..." But we are not about C
here... Hopefully it will die put quietly...
Best,
Frank
[moderator]
No one here seems to care about how x86/x64 computations are Turing
equivalent. I created an Universal Turing Machine (UTM) equivalent that
has the x86 language as its description language.
--
Copyright 2020 Pete Olcott
Terje Mathisen
2020-09-06 16:27:42 UTC
Permalink
Post by olcott
Post by Frank Kotler
Post by Terje Mathisen
Please, no more!
Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(
I fear I made an error on approving this in the first place. I saw a
reference to "x86" and thought "well maybe..." But we are not about C
here... Hopefully it will die put quietly...
Best,
Frank
[moderator]
No one here seems to care about how x86/x64 computations are Turing
equivalent. I created an Universal Turing Machine (UTM) equivalent that
has the x86 language as its description language.
Turing-complete computers are the rule rather than the exception. I.e.
_all_ existing microprocessors, from the original 4004 and up are TC.

Going down to more esoteric "computers", both Minecraft and the Game of
Life have been shown to be TC. :-)

Please don't bring back the requirement for infinite storage since that
simply reduces the number of TC architectures to zero.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
olcott
2020-09-06 16:47:09 UTC
Permalink
Post by Terje Mathisen
Post by olcott
Post by Frank Kotler
Post by Terje Mathisen
Please, no more!
Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(
I fear I made an error on approving this in the first place. I saw a
reference to "x86" and thought "well maybe..." But we are not about C
here... Hopefully it will die put quietly...
Best,
Frank
[moderator]
No one here seems to care about how x86/x64 computations are Turing
equivalent. I created an Universal Turing Machine (UTM) equivalent
that has the x86 language as its description language.
Turing-complete computers are the rule rather than the exception. I.e.
_all_ existing microprocessors, from the original 4004 and up are TC.
Going down to more esoteric "computers", both Minecraft and the Game of
Life have been shown to be TC. :-)
Please don't bring back the requirement for infinite storage since that
simply reduces the number of TC architectures to zero.
Terje
My whole point of this posting is to prove that programs implemented on
x86 machines have identical behavior to the same programs executed on
actual Turing Machines. As long as the x86 machine has as much memory as
it needs it performs a Turing equivalent computation.

The idea of a [Turing equivalent computation] may be a brand new idea.
--
Copyright 2020 Pete Olcott
olcott
2020-09-07 04:24:16 UTC
Permalink
Post by Terje Mathisen
Post by olcott
Post by Frank Kotler
Post by Terje Mathisen
Please, no more!
Turing-complete "C" has absolutely _nothing_ to do with
comp.lang.asm.x86, and does not belong here. :-(
I fear I made an error on approving this in the first place. I saw a
reference to "x86" and thought "well maybe..." But we are not about C
here... Hopefully it will die put quietly...
Best,
Frank
[moderator]
No one here seems to care about how x86/x64 computations are Turing
equivalent. I created an Universal Turing Machine (UTM) equivalent
that has the x86 language as its description language.
Turing-complete computers are the rule rather than the exception. I.e.
_all_ existing microprocessors, from the original 4004 and up are TC.
Going down to more esoteric "computers", both Minecraft and the Game of
Life have been shown to be TC. :-)
Please don't bring back the requirement for infinite storage since that
simply reduces the number of TC architectures to zero.
Terje
https://www.researchgate.net/publication/343838609_The_x86_language_has_Turing_Complete_memory_access
--
Copyright 2020 Pete Olcott
a***@nospicedham.spamtrap.com
2020-09-08 19:52:54 UTC
Permalink
On Sun, 6 Sep 2020 23:24:16 -0500, olcott
Post by olcott
...
https://www.researchgate.net/publication/343838609_The_x86_language_has_Turing_Complete_memory_access
...
It is much more fun to actually do it!

This assembles to 16-bit code (for dosbox-debug to show the mnemonics
correctly) so the smc instructions have +2 instead of +1, because of
the prefix:
------
tc.asm
------
org 100h
mov eax,0x100
mov ebx,eax
sub ebx,0x100
.1: mov dword [ebx],0x40404040
add ebx,byte +0x4
cmp ebx,eax
jl .1
mov ecx,dword [eax+0x2]
add ecx,0x100
mov dword [eax+0x2],ecx
mov ebx,eax
mov edx,eax
add edx,0x54
.2: mov ecx,[ebx]
mov [ebx+0x100],ecx
add ebx,byte +0x4
cmp ebx,edx
jl .2
jmp .3
times 100h-($-$$) db 0
.3:

nasm -f bin -o tc.com tc.asm
copy the com file to where you mounted c: in dosbox.
start dosbox-debug in supervisor-mode
in the dosbox window type debug tc
change to the debug window and type:
MEMDUMP 213:0 400 (the segment may by different?)
The first 256 bytes are of course the PSP.
go to the directory of dosbox.exe and copy the file memdump.txt to the
directory where you mounted c:, and rename it memdump1.txt
in the debug window type:
BP 213:451
LOGL 1000
MEMDUMP 213:0 400
close dosbox-debug with CTL-PAUSE
copy the files memdump.txt and logcpu.txt to where you mounted c:
start dosbox and type
copy memdump1.txt+logcpu.txt+memdump.txt log.txt
open log.txt in notepad.
--
aen
olcott
2020-09-08 20:12:27 UTC
Permalink
Post by a***@nospicedham.spamtrap.com
On Sun, 6 Sep 2020 23:24:16 -0500, olcott
Post by olcott
...
https://www.researchgate.net/publication/343838609_The_x86_language_has_Turing_Complete_memory_access
...
It is much more fun to actually do it!
This (byte sequence) code runs directly in libx86emu: x86emu-demo.c
(See second page of the PDF). I used Intel XED to disassemble it.

The original code was written in Microsoft "c" as embedded assembly
language. x86emu-demo.c can begin its execution at any point in the
COFF object file generated by the "c" compiler.

100: B800010000 mov eax, 0x100
105: 8BD8 mov ebx, eax
107: 81EB00010000 sub ebx, 0x100
10d: C70340404040 mov dword ptr [ebx], 0x40404040
113: 83C304 add ebx, 0x4
116: 3BD8 cmp ebx, eax
118: 7CF3 jl 0x10d
11a: 8B4801 mov ecx, dword ptr [eax+0x1]
11d: 81C100010000 add ecx, 0x100
123: 894801 mov dword ptr [eax+0x1], ecx
126: 8BD8 mov ebx, eax
128: 8BD0 mov edx, eax
12a: 83C241 add edx, 0x41
12d: 8B0B mov ecx, dword ptr [ebx]
12f: 898B00010000 mov dword ptr [ebx+0x100], ecx
135: 83C304 add ebx, 0x4
138: 3BDA cmp ebx, edx
13a: 7CF1 jl 0x12d
13c: E9BF000000 jmp 0x200
Post by a***@nospicedham.spamtrap.com
This assembles to 16-bit code (for dosbox-debug to show the mnemonics
correctly) so the smc instructions have +2 instead of +1, because of
------
tc.asm
------
org 100h
mov eax,0x100
mov ebx,eax
sub ebx,0x100
.1: mov dword [ebx],0x40404040
add ebx,byte +0x4
cmp ebx,eax
jl .1
mov ecx,dword [eax+0x2]
add ecx,0x100
mov dword [eax+0x2],ecx
mov ebx,eax
mov edx,eax
add edx,0x54
.2: mov ecx,[ebx]
mov [ebx+0x100],ecx
add ebx,byte +0x4
cmp ebx,edx
jl .2
jmp .3
times 100h-($-$$) db 0
nasm -f bin -o tc.com tc.asm
copy the com file to where you mounted c: in dosbox.
start dosbox-debug in supervisor-mode
in the dosbox window type debug tc
MEMDUMP 213:0 400 (the segment may by different?)
The first 256 bytes are of course the PSP.
go to the directory of dosbox.exe and copy the file memdump.txt to the
directory where you mounted c:, and rename it memdump1.txt
BP 213:451
LOGL 1000
MEMDUMP 213:0 400
close dosbox-debug with CTL-PAUSE
start dosbox and type
copy memdump1.txt+logcpu.txt+memdump.txt log.txt
open log.txt in notepad.
--
Copyright 2020 Pete Olcott
Loading...