Mapping "C" to a Turing equivalent abstract model of computation

[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 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

[olcott]

[Jeff Barnett]

On 9/5/2020 10:38 AM, olcott wrote:

Suggestion for you, our resident dunce: Use Lisp, not C. Writing a TM
interpreter is basically a homework problem I know it may still be
difficult for you but it will save another 16 years. Here is a list of
some available implementations. Note, some of these are time-limited URL
because their authors put them in a public place so they could be
reached. I really don't expect you to pay any attention to all of this
but it could save you decades. I'm not sure what you will do with your
time after this project is over via failure.

https://github.com/fmdkdd/turisp (CL)

http://www.lysator.liu.se/~davidk/elisp/turing.el (GNU ELISP)

https://github.com/dieggsy/turing-machine (GNU ELISP + GNU emacs interface)

https://drive.google.com/file/d/1DUCuwaVR5ElQSD8poKfxRXmmLjNprkJF/view?usp=sharing

https://ln.sync.com/dl/5a02647d0/75mxr3ta-n9ymydu2-su64kn7p-wdjtzb4p

You can even find UTM code TM form in some books or, perhaps, on the
internet. Perhaps, Ben can give you a pointer - it's been too long ago
for me.
--
Jeff Barnett

[olcott]

Using the RASP equivalent model of the x86 programing language is most
effective because this model hands me all of the control flow of the
entire system as a fully encoded directed graph. When creating a halt
decider it is very handy to have all of control flow already encoded as
a directed graph.

It is also very handy because all the code that derives this directed
graph can be specified as the high level abstraction of the "C"
programming language.

How much easier is it to understand the architecture of a system
specified in "C" than it would be to examine this same architecture on
the basis of (TM 5-tuple) microcode?

[Jeff Barnett]

Gibberish. Your just stalling.
--
Jeff Barnett

[olcott]

Ben backed out of an equivalent claim going so far as to say that he
never made any such claim.

This is my x86utm operating system interface:
It is very close to fully operational.

// Saves the state of the current virtual-machine
void SaveState(u32* s);

// Loads the state of a saved virtual-machine
void LoadState(u32* s);

// Allocates memory from the heap
u32* Allocate(u32 size);

// The master machine executes the slave machine
void DebugStep(u32* master_state, u32* slave_state);