From: NoOne@nospicedham.NoWhere.com   
      
   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   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)