Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Why are there always boycotts? Shouldn't there be girlcotts too? -- argon on #Linux


programming / comp.lang.asm.x86 / Transforming the x86 language into its Turing equivalent 002

SubjectAuthor
* Transforming "C" into a Turing equivalent language 001 [Providingolcott
+* Transforming the x86 language into its Turing equivalent 002olcott
|`- Re: Transforming the x86 language into its Turing equivalent 002George Neuner
`* Re: Transforming "C" into a Turing equivalent language 001 [ProvidingGeorge Neuner
 `- Re: Transforming "C" into a Turing equivalent language 001 [Providingolcott

1
Subject: Transforming "C" into a Turing equivalent language 001 [Providing
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sun, 30 Aug 2020 18:40 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.theory,comp.ai.philosophy,comp.lang.c,comp.lang.asm.x86
Subject: Transforming "C" into a Turing equivalent language 001 [Providing
Date: Sun, 30 Aug 2020 13:40:20 -0500
Organization: A noiseless patient Spider
Lines: 44
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <zs2dnQoe4sMIb9bCnZ2dnUU7-WfNnZ2d@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="5970141a266d4c6c423ed544a077f490";
logging-data="6231"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+zta1x98C5W5/eyUSTuG9a01QrjJYYqz0="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:jQ29cFOGkd2F+VY2d33OiohhLqw=
View all headers
The end goal of this sequence of posts is to show that the basic "C" programming language (without the "C" libraries) can be fully mapped to an abstract model of computation that is equivalent to a Turing machine in such a way that any Turing complete computation can be written in the "C" programming language.

When "C" is mapped to an abstract model of computation that can provide an arbitrary number of arbitrary length linked lists, then "C" acquires Turing complete memory access. This is computationally the same as providing "C" with an unlimited number of Turing machine tapes.

When we define this abstract memory access such that it can be concretely implemented on machines with finite memory and this concrete implementation automatically scales to any increase in physical memory then the memory access aspect of the concrete implementation is computationally identical to the abstract Turing complete machine.

Such a virtual machine would provide Turing complete memory access to "C" because the memory access aspect would behave exactly the same across the Turing complete abstract machine and the concrete machine for all computations not requiring more memory than the concrete machine has.

The virtual machine code that the "C" programs would be translated into would be a Turing equivalent language. Thus the machine description language would have identical execution on the concrete physical machine as it would on the abstract Turing equivalent machine.

The input, output, state changes, and moves of the Tape head would be identical between the two machines for any computation not requiring more memory that the physical machine actually has.

The intention is to define the Turing equivalent abstract model of computation in terms of the x64-relative addressing model. Conditional jumps and RIP-relative addressing both have signed offsets of 0x7fffffff bytes.

When we simply assume no upper bound to memory, then this abstract model is identical to a Turing machine that can move its tape head to the left or right in increments of 1 to 0x7fffffff bytes and can access data on the tape in {8,16,32,64}-bit sized chunks.

--
Copyright 2020 Pete Olcott



Subject: Transforming the x86 language into its Turing equivalent 002
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Wed, 2 Sep 2020 17:18 UTC
References: 1
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: Transforming the x86 language into its Turing equivalent 002
Date: Wed, 2 Sep 2020 12:18:42 -0500
Organization: A noiseless patient Spider
Lines: 72
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <-4qdncoPX4tsTtLCnZ2dnUU7-QfNnZ2d@giganews.com>
References: <zs2dnQoe4sMIb9bCnZ2dnUU7-WfNnZ2d@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="bc30823d34f37bfbf38cc24e012d1329";
logging-data="25049"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19QPTDpnAZMCm0YyLIGFY7oX/nyNOHXHXs="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:cluWTfWHFsi1gH+A5f8KGdNH+W4=
View all headers
On 8/30/2020 1:40 PM, olcott wrote:
The end goal of this sequence of posts is to show that the basic "C" programming language (without the "C" libraries) can be fully mapped to an abstract model of computation that is equivalent to a Turing machine in such a way that any Turing complete computation can be written in the "C" programming language.

When "C" is mapped to an abstract model of computation that can provide an arbitrary number of arbitrary length linked lists, then "C" acquires Turing complete memory access. This is computationally the same as providing "C" with an unlimited number of Turing machine tapes.

When we define this abstract memory access such that it can be concretely implemented on machines with finite memory and this concrete implementation automatically scales to any increase in physical memory then the memory access aspect of the concrete implementation is computationally identical to the abstract Turing complete machine.

Such a virtual machine would provide Turing complete memory access to "C" because the memory access aspect would behave exactly the same across the Turing complete abstract machine and the concrete machine for all computations not requiring more memory than the concrete machine has.

The virtual machine code that the "C" programs would be translated into would be a Turing equivalent language. Thus the machine description language would have identical execution on the concrete physical machine as it would on the abstract Turing equivalent machine.

The input, output, state changes, and moves of the Tape head would be identical between the two machines for any computation not requiring more memory that the physical machine actually has.

The intention is to define the Turing equivalent abstract model of computation in terms of the x64-relative addressing model. Conditional jumps and RIP-relative addressing both have signed offsets of 0x7fffffff bytes.

When we simply assume no upper bound to memory, then this abstract model is identical to a Turing machine that can move its tape head to the left or right in increments of 1 to 0x7fffffff bytes and can access data on the tape in {8,16,32,64}-bit sized chunks.


Mapping x86 programs to a Turing equivalent abstract model

The following 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.

Instruction
      : INTEGER ":" OpCode
      | INTEGER ":" OpCode Integer
      | INTEGER ":" OpCode Integer "," Integer

HEXDIGIT [a-fA-F-0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}

Address:OpCode
Address:OpCode Param
Address:OpCode Param, Param

This would guarantee that the execution of an x86 program on an input would be equivalent to the execution of a Turing machine on equivalent input for all x86 programs that complete executing and halt.

The Church-Turing thesis makes no such guarantee:
https://plato.stanford.edu/entries/church-turing/

--
Copyright 2020 Pete Olcott



Subject: Re: Transforming the x86 language into its Turing equivalent 002
From: George Neuner
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Thu, 3 Sep 2020 14:19 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: gneun...@nospicedham.comcast.net (George Neuner)
Newsgroups: comp.lang.asm.x86
Subject: Re: Transforming the x86 language into its Turing equivalent 002
Date: Thu, 03 Sep 2020 10:19:03 -0400
Organization: A noiseless patient Spider
Lines: 9
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <1nu1lfpo2mlt7fm3gli8m2tk8jao8dtbbm@4ax.com>
References: <zs2dnQoe4sMIb9bCnZ2dnUU7-WfNnZ2d@giganews.com> <-4qdncoPX4tsTtLCnZ2dnUU7-QfNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="f02f923047af1f7dc1d5bbb2e6157734";
logging-data="7741"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+f8zc/suVFC8smO5iR3a00SC/81MRZMi8="
User-Agent: ForteAgent/8.00.32.1272
Cancel-Lock: sha1:IaLa9Z/TQLzxpjwZ04zCm+tuROg=
View all headers
On Wed, 2 Sep 2020 12:18:42 -0500, olcott
<NoOne@nospicedham.NoWhere.com> wrote:

Mapping x86 programs to a Turing equivalent abstract model
 :

According to this paper, 'mov' alone is turing complete.
http://stedolan.net/research/mov.pdf



Subject: Re: Transforming "C" into a Turing equivalent language 001 [Providing
From: George Neuner
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Thu, 3 Sep 2020 14:22 UTC
References: 1
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: gneun...@nospicedham.comcast.net (George Neuner)
Newsgroups: comp.lang.asm.x86
Subject: Re: Transforming "C" into a Turing equivalent language 001 [Providing
Date: Thu, 03 Sep 2020 10:22:23 -0400
Organization: A noiseless patient Spider
Lines: 13
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <bru1lfd1d457v55209shunjenkil5ivl6e@4ax.com>
References: <zs2dnQoe4sMIb9bCnZ2dnUU7-WfNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="f02f923047af1f7dc1d5bbb2e6157734";
logging-data="7772"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/h3zeSN8Tg9/pvwYKncunuP+shxTbb0AE="
User-Agent: ForteAgent/8.00.32.1272
Cancel-Lock: sha1:vKCwmFtwkYTR7uH8vjLlTj7Ychg=
View all headers
On Sun, 30 Aug 2020 13:40:20 -0500, olcott
<NoOne@nospicedham.NoWhere.com> wrote:

The end goal of this sequence of posts is to show that the basic "C"
programming language (without the "C" libraries) can be fully mapped to
an abstract model of computation that is equivalent to a Turing machine
in such a way that any Turing complete computation can be written in the
"C" programming language.
    :


It's already well known that C is Turing complete.



Subject: Re: Transforming "C" into a Turing equivalent language 001 [Providing
From: olcott
Newsgroups: comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Thu, 3 Sep 2020 15:02 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: Transforming "C" into a Turing equivalent language 001 [Providing
Date: Thu, 3 Sep 2020 10:02:03 -0500
Organization: A noiseless patient Spider
Lines: 33
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <2sqdnYuDt533mMzCnZ2dnUU7-YnNnZ2d@giganews.com>
References: <zs2dnQoe4sMIb9bCnZ2dnUU7-WfNnZ2d@giganews.com>
<bru1lfd1d457v55209shunjenkil5ivl6e@4ax.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="f02f923047af1f7dc1d5bbb2e6157734";
logging-data="30997"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/QUtBZkBNdf1Fq4ampa80Xl+hsI9Paf2c="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Thunderbird/68.12.0
Cancel-Lock: sha1:n7xC0QZFAg3hyjAAcTuEOF1mw1w=
View all headers
On 9/3/2020 9:22 AM, George Neuner wrote:
On Sun, 30 Aug 2020 13:40:20 -0500, olcott
<NoOne@nospicedham.NoWhere.com> wrote:

The end goal of this sequence of posts is to show that the basic "C"
programming language (without the "C" libraries) can be fully mapped to
an abstract model of computation that is equivalent to a Turing machine
in such a way that any Turing complete computation can be written in the
"C" programming language.
     :


It's already well known that C is Turing complete.


It is well known that "C" is Turing complete except for its lack of unlimited memory.

I needed to show that concrete C/x86 computations on physical hardware are equivalent to corresponding computations on a Turing Machine.

This may be a new concept:
Computational equivalence means that two machines will always produce equivalent output for equivalent input or fail to halt on equivalent input.

I need this to show the relevance of my x86 based Universal Turing Machine equivalent. This machine has the x86 language as its machine description language and can execute a UTM that executes another UTM in debug step mode. It can do this to an arbirary recursive depth.

--
Copyright 2020 Pete Olcott



1
rocksolid light 0.7.2
clearneti2ptor