Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

There are new messages.


programming / comp.lang.asm.x86 / Re: Mapping x86/x64/C to a Turing equivalent abstract model of

SubjectAuthor
* Mapping x86/x64/C to a Turing equivalent abstract model ofolcott
`* Re: Mapping x86/x64/C to a Turing equivalent abstract model ofTerje Mathisen
 +- Re: Mapping x86/x64/C to a Turing equivalent abstract model ofolcott
 `* Re: Mapping x86/x64/C to a Turing equivalent abstract model ofFrank Kotler
  `* Re: Mapping x86/x64/C to a Turing equivalent abstract model ofolcott
   `* Re: Mapping x86/x64/C to a Turing equivalent abstract model ofTerje Mathisen
    +- Re: Mapping x86/x64/C to a Turing equivalent abstract model ofolcott
    `* Re: Mapping x86/x64/C to a Turing equivalent abstract model ofolcott
     `* Re: Mapping x86/x64/C to a Turing equivalent abstract model ofaen
      `- Re: Mapping x86/x64/C to a Turing equivalent abstract model ofolcott

1
Subject: Mapping x86/x64/C to a Turing equivalent abstract model of
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sat, 5 Sep 2020 17:14 UTC
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.lang.asm.x86
Subject: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sat, 5 Sep 2020 12:14:58 -0500
Organization: A noiseless patient Spider
Lines: 38
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="22b79ff0dc4692c6394fd5df7481c0d9";
logging-data="21391"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19eqHHlymQHj/dzp7zdbDfXDGqPxboKYqY="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:6OFcdISUyBdwVnx+4ePKFGLs/24=
View all headers
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



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: Terje Mathisen
Newsgroups: comp.lang.asm.x86
Organization: Aioe.org NNTP Server
Date: Sat, 5 Sep 2020 19:06 UTC
References: 1
Path: i2pn2.org!i2pn.org!news.swapon.de!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: terje.ma...@nospicedham.tmsw.no (Terje Mathisen)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sat, 5 Sep 2020 21:06:31 +0200
Organization: Aioe.org NNTP Server
Lines: 50
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rj0njl$1n26$1@gioia.aioe.org>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="22b79ff0dc4692c6394fd5df7481c0d9";
logging-data="29906"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/1mIz0gBVvD794CZC15QoGiAHanxq63tY="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.3
Cancel-Lock: sha1:Y70Sfx3gysIbW4vebKMgO8HhDR4=
View all headers
Please, no more!

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

Terje

olcott wrote:
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.



--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sat, 5 Sep 2020 19:20 UTC
References: 1 2
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sat, 5 Sep 2020 14:20:54 -0500
Organization: A noiseless patient Spider
Lines: 57
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <AJWdncP1o5OKeM7CnZ2dnUU7-aGdnZ2d@giganews.com>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="22b79ff0dc4692c6394fd5df7481c0d9";
logging-data="3053"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+yxwKtnc20WaScgcJWovx7qhTH9ja8STI="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:bq6sVRU9w1HpwI/X4f5WLmyTtnA=
View all headers
On 9/5/2020 2:06 PM, Terje Mathisen wrote:
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.

Terje

olcott wrote:
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



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: Frank Kotler
Newsgroups: comp.lang.asm.x86
Organization: Aioe.org NNTP Server
Date: Sun, 6 Sep 2020 04:50 UTC
References: 1 2
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: fbkot...@nospicedham.myfairpoint.net (Frank Kotler)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sun, 6 Sep 2020 00:50:10 -0400
Organization: Aioe.org NNTP Server
Lines: 15
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rj1ptm$9vl$1@gioia.aioe.org>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="1e2fe217903c7baab0714017c1d012e0";
logging-data="5953"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18FroA+QEp4jZKErCH9JAE1DkavkVwhzj4="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
Thunderbird/52.5.2
Cancel-Lock: sha1:5DFQqJJF6+l0JSXwUnZ0E0gBW9E=
View all headers
On 09/05/2020 03:06 PM, Terje Mathisen wrote:
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]




Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sun, 6 Sep 2020 05:17 UTC
References: 1 2 3
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sun, 6 Sep 2020 00:17:07 -0500
Organization: A noiseless patient Spider
Lines: 24
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <mdGdnfXBgu1J7cnCnZ2dnUU7-IXNnZ2d@giganews.com>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org> <rj1ptm$9vl$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="1e2fe217903c7baab0714017c1d012e0";
logging-data="13491"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+myCCDiN7bw7jewMZ65eQFBOSDcJNOnrc="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:HXw0O9DpR/m052+tGFx9ehv+Cbc=
View all headers
On 9/5/2020 11:50 PM, Frank Kotler wrote:
On 09/05/2020 03:06 PM, Terje Mathisen wrote:
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



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: Terje Mathisen
Newsgroups: comp.lang.asm.x86
Organization: Aioe.org NNTP Server
Date: Sun, 6 Sep 2020 16:27 UTC
References: 1 2 3 4
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: terje.ma...@nospicedham.tmsw.no (Terje Mathisen)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sun, 6 Sep 2020 18:27:42 +0200
Organization: Aioe.org NNTP Server
Lines: 37
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rj32lt$1k5m$1@gioia.aioe.org>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org> <rj1ptm$9vl$1@gioia.aioe.org>
<mdGdnfXBgu1J7cnCnZ2dnUU7-IXNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="1e2fe217903c7baab0714017c1d012e0";
logging-data="12906"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX186ZvRGAFy0y3xRTYUC76on8cys9+AVem0="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.3
Cancel-Lock: sha1:luVRjRgR8K1ZMx78sZGdSvYVehI=
View all headers
olcott wrote:
On 9/5/2020 11:50 PM, Frank Kotler wrote:
On 09/05/2020 03:06 PM, Terje Mathisen wrote:
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"



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sun, 6 Sep 2020 16:47 UTC
References: 1 2 3 4 5
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sun, 6 Sep 2020 11:47:09 -0500
Organization: A noiseless patient Spider
Lines: 45
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <YPOdnQaqE8IRj8jCnZ2dnUU7-efNnZ2d@giganews.com>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org> <rj1ptm$9vl$1@gioia.aioe.org>
<mdGdnfXBgu1J7cnCnZ2dnUU7-IXNnZ2d@giganews.com>
<rj32lt$1k5m$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="1e2fe217903c7baab0714017c1d012e0";
logging-data="25615"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX188xpNglbj7R0OFX3BWiV4t1sqHXPWJnMY="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:Wmq0bVouNRHpE0/ndZk0iKgSVyo=
View all headers
On 9/6/2020 11:27 AM, Terje Mathisen wrote:
olcott wrote:
On 9/5/2020 11:50 PM, Frank Kotler wrote:
On 09/05/2020 03:06 PM, Terje Mathisen wrote:
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



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Mon, 7 Sep 2020 04:24 UTC
References: 1 2 3 4 5
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Sun, 6 Sep 2020 23:24:16 -0500
Organization: A noiseless patient Spider
Lines: 41
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <BZKdndjtYZJyKMjCnZ2dnUU7-dOdnZ2d@giganews.com>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org> <rj1ptm$9vl$1@gioia.aioe.org>
<mdGdnfXBgu1J7cnCnZ2dnUU7-IXNnZ2d@giganews.com>
<rj32lt$1k5m$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="4f93015889ff861e006e01e75b604fef";
logging-data="15661"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19siLZqUaVea659BlmBUskU6/WTqJOA5T8="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:IORCzZiOGLM56qiLrBbLS2C92IQ=
View all headers
On 9/6/2020 11:27 AM, Terje Mathisen wrote:
olcott wrote:
On 9/5/2020 11:50 PM, Frank Kotler wrote:
On 09/05/2020 03:06 PM, Terje Mathisen wrote:
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



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: aen...@nospicedham.spamtrap.com
Newsgroups: comp.lang.asm.x86
Organization: Aioe.org NNTP Server
Date: Tue, 8 Sep 2020 19:52 UTC
References: 1 2 3 4 5 6
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: aen...@nospicedham.spamtrap.com
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Tue, 08 Sep 2020 19:52:54 GMT
Organization: Aioe.org NNTP Server
Lines: 57
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <5f57e107.478234109@nntp.aioe.org>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com> <rj0njl$1n26$1@gioia.aioe.org> <rj1ptm$9vl$1@gioia.aioe.org> <mdGdnfXBgu1J7cnCnZ2dnUU7-IXNnZ2d@giganews.com> <rj32lt$1k5m$1@gioia.aioe.org> <BZKdndjtYZJyKMjCnZ2dnUU7-dOdnZ2d@giganews.com>
Injection-Info: reader02.eternal-september.org; posting-host="977adf50e65fb70f12ad8b1d87377ca3";
logging-data="4454"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19BYn/a/5AoByaizl2kbFSU53FYocPv/Uw="
Cancel-Lock: sha1:HsHxvFOZcnaWx5BSGgCasVC/wDo=
View all headers
On Sun, 6 Sep 2020 23:24:16 -0500, olcott
<NoOne@nospicedham.NoWhere.com> wrote:
...
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



Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Tue, 8 Sep 2020 20:12 UTC
References: 1 2 3 4 5 6 7
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.lang.asm.x86
Subject: Re: Mapping x86/x64/C to a Turing equivalent abstract model of
Date: Tue, 8 Sep 2020 15:12:27 -0500
Organization: A noiseless patient Spider
Lines: 91
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <1qudnTPMyN03eMrCnZ2dnUU7-UPNnZ2d@giganews.com>
References: <ZaKdneAKx4gNWs7CnZ2dnUU7-W-dnZ2d@giganews.com>
<rj0njl$1n26$1@gioia.aioe.org> <rj1ptm$9vl$1@gioia.aioe.org>
<mdGdnfXBgu1J7cnCnZ2dnUU7-IXNnZ2d@giganews.com>
<rj32lt$1k5m$1@gioia.aioe.org>
<BZKdndjtYZJyKMjCnZ2dnUU7-dOdnZ2d@giganews.com>
<5f57e107.478234109@nntp.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="977adf50e65fb70f12ad8b1d87377ca3";
logging-data="20267"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/L/sKwmb1SGL8q/DpdCwmViByfLJZDJ8k="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:0XYPf8IeTUO02e7MZoRm99nlocc=
View all headers
On 9/8/2020 2:52 PM, aen@nospicedham.spamtrap.com wrote:
On Sun, 6 Sep 2020 23:24:16 -0500, olcott
<NoOne@nospicedham.NoWhere.com> wrote:
...
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



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.



--
Copyright 2020 Pete Olcott



1
rocksolid light 0.7.2
clearneti2ptor