olcott

2020-09-05 17:14:58 UTC

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.

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

Copyright 2020 Pete Olcott