Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

The world is coming to an end ... SAVE YOUR BUFFERS!!!

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

o Transforming "C" into a Turing equivalent language 001 [Providingolcott

Subject: Transforming "C" into a Turing equivalent language 001 [Providing
From: olcott
Newsgroups: comp.theory,, comp.lang.c, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sun, 30 Aug 2020 18:40 UTC
From: (olcott)
Newsgroups: comp.theory,,comp.lang.c,comp.lang.asm.x86
Subject: Transforming "C" into a Turing equivalent language 001 [Providing
Date: Sun, 30 Aug 2020 13:40:20 -0500
Organization: A noiseless patient Spider
Lines: 44
Approved: - comp.lang.asm.x86 moderation team.
Message-ID: <>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info:; posting-host="5970141a266d4c6c423ed544a077f490";
logging-data="6231"; mail-complaints-to=""; posting-account="U2FsdGVkX1+zta1x98C5W5/eyUSTuG9a01QrjJYYqz0="
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101
Cancel-Lock: sha1:jQ29cFOGkd2F+VY2d33OiohhLqw=
View all headers
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

rocksolid light 0.7.2