Transforming "C" into a Turing equivalent language 001 [Providing

[olcott]

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.

[olcott]

Post by olcott
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/

[George Neuner]

On Wed, 2 Sep 2020 12:18:42 -0500, olcott

Post by olcott
Mapping x86 programs to a Turing equivalent abstract model

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

[George Neuner]

On Sun, 30 Aug 2020 13:40:20 -0500, olcott

Post by olcott
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.

[olcott]

Post by George Neuner
On Sun, 30 Aug 2020 13:40:20 -0500, olcott

Post by olcott
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.