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