<ul>
<li><p>If your students have done any functional programming, the nicest approach I know is to start with the untyped lambda calculus, and then use the <a href="http://www.cantab.net/users/antoni.diller/brackets/intro.html" rel="nofollow noreferrer">bracket abstraction theorem</a> to translate it into SKI combinators. Then, you can use the $smn$ and $utm$ theorems to show that Turing machines form a <a href="http://ncatlab.org/nlab/show/partial+combinatory+algebra" rel="nofollow noreferrer"><em>partial combinatory algebra</em></a>, and so can interpret the SKI combinators. </p>

<p>I doubt this is the simplest possible approach, but I like how it rests  on some of the most fundamental theorems in computability (which you may well wish to cover for other reasons). </p>

<p>It appears that <a href="https://mathoverflow.net/questions/132800/a-proof-that-the-natural-numbers-form-a-pca">Andrej Bauer answered a similar question on Mathoverflow</a> a few months back.</p></li>
<li><p>If you are set on a C-like language, your path will be a lot rougher, since they have a rather complicated semantics -- you'll need to </p>

<ol>
<li>Show that Turing machines can simulate a stack and a heap at the same time, and </li>
<li>Show how variables can be implemented with a stack, and</li>
<li>Show that procedure calls can be implemented with a stack. </li>
</ol>

<p>This is much of the contents of a compilers class, honestly. </p></li>
</ul>

CC BY-SA 4.0
2021-06-17T00:15:15.500Z
Number 1 seems rather easy if you have the rest of the language down - a stack is simply an array used in a certain way. Basically you'd go to some sort of assembler before you go down to the Turing level. I'm still trying to understand this myself. Given how often the word Turing-complete is used, it's surprising that nobody REALLY checks whether C and a Turing machine are the same thing.
Stefan Reich
CC BY-SA 3.0
2013-08-20T09:07:35.450Z
2013-08-21T10:07:12.730Z
2017-04-13T12:57:54.777Z
Neel Krishnaswami
<p>My Theory of Comp professor in undergrad started by proving that a single-tape Turing machine can implement a multi-tape Turing machine.  This handles variable declaration: if a program has six variable declarations, then it can be easily implemented on a seven-tape Turing machine (a tape for each variable, and a "register" tape to help perform tasks like arithmetic and equality-checking between tapes).  He then showed how to implement basic FOR and WHILE loops, and at that point we had a basic Turing-complete C-like language.  I found it satisfying, anyways.</p>

CC BY-SA 3.0
2013-09-14T19:53:20.317Z
2013-09-14T19:53:20.317Z
GMB
<p>I'm thinking right now about how to convince myself that Turing machines are a general model of computation.   I agree that the standard treatment of the Church-Turing thesis in some standard textbooks, e.g. Sipser, is not very complete.  Here is a sketch of how I might go from Turing machines to a more recognizable programming language.</p>

<p>Consider a block-structured programming language with <code>if</code> and <code>while</code> statements, with <em>non-recursive</em> defined functions and subroutines, with named <em>boolean</em> random variables and general boolean expressions, and with a single unbounded boolean array <code>tape[n]</code> with an integer array pointer <code>n</code> that can be incremented or decremented, <code>n++</code> or <code>n--</code>.  The pointer <code>n</code> is initially zero and the array <code>tape</code> is initially all zero.   So, this computer language can be C-like or Python-like, but it is very limited in its data types.   In fact, they are so limited that we do not even have a way to use the pointer <code>n</code> in a boolean expression.  Assuming that <code>tape</code> is only infinite to the right, we can declare a pointer underflow "system error" if <code>n</code> is ever negative.   Also, our language has an <code>exit</code> statement with one argument, to output a boolean answer.</p>

<p>Then the first point is that this programming language is a good specification language for a Turing machine.  You can easily see that, except for the tape array, the code only has finitely many possible states:  The state of all of its declared variables, and the current line of execution, and its subroutine stack.  The latter only has a finite amount of state because recursive functions are not allowed.  You could imagine a "compiler" that creates an "actual" Turing machine from a code of this type, but the details of that are not important.  The point is that we have a programming language with pretty good syntax, but very primitive data types.</p>

<p>The rest of the construction is to convert this to a more livable programming language with a finite list of library functions and precompilation stages.  We can proceed as follows:</p>

<ol>
<li><p>With a precompiler, we can expand the boolean data type to a larger but finite symbol alphabet such as ASCII.  We can assume that <code>tape</code> takes values in this larger alphabet.  We can leave a marker at the beginning of the tape to prevent pointer underflow, and a movable marker at the end of the tape to prevent the TM from skating to infinity on the tape accidentally.  We can implement arbitrary binary operations between symbols, and conversions to boolean for <code>if</code> and <code>while</code> statements.  (Actually <code>if</code> can be implemented with <code>while</code> as well, if it weren't available.)</p></li>
<li><p>We want an unbounded integer data type in order to implement both random access of the tape and (positive) integer arithmetic.  To this end, we simulate a $k$-tape TM  for some fixed $k$ with the one tape that we have.   This construction is given as a theorem in Sipser.  The idea is to interleave the emulated tapes on the low-level tape we have, with marker symbols representing the head positions.  If the low-level tape pointer is at zero, it services the $i$th subtape by moving to position $i$ and then jumping $k$ steps at a time; after each read or write, the low-level tape pointer decrements back to zero.  Just as in the previous stage, it is easier to implement this as a precompiler.</p></li>
<li><p>We designate one tape as symbol-valued "memory" and the others as unsigned, integer-valued "registers" or "variables".  We store the integers in little-endian binary with termination markers.   We first implement copy of a register and binary decrement of a register.  Combining that with increment and decrement of the memory pointer, we can implement random access seek of the symbol memory.  We can also write functions to calculate binary addition and multiplication of integers.  It is not hard to write a binary addition function with bitwise operations, and a function to multiply by 2 with left shift.  (Or really right shift, since it is little-endian.)  With these primitives, we can write a function to multiply two registers using the long multiplication algorithm.</p></li>
<li><p>We can reorganize the memory tape from a one-dimensional symbol array <code>symbol[n]</code> to a two-dimensional symbol array <code>symbol[x,y]</code> using the formula <code>n = (x+y)*(x+y) + y</code>.  We can now use each row of the memory to express an unsigned integer in binary with a termination symbol, to obtain a one-dimensional, random-access, integer-valued memory <code>memory[x]</code>.  We can implement reading from the memory to an integer register, and writing from a register to the memory.  Many features can now be implemented with functions:  Signed and floating point arithmetic, symbol strings, etc.</p></li>
<li><p>Only one more basic facility strictly requires a precompiler, namely recursive functions.  This can be done with a technique that is widely used to implement interpreted languages.  We assign each high-level, recursive function a name string, and we organize the low-level code into one large <code>while</code> loop that maintains a call stack with the usual parameters:  the calling point, the called function, and a list of arguments.</p></li>
</ol>

<p>At this point, the construction has enough features of a high-level programming language that further functionality is more the topic of programming languages and compilers rather than CS theory.  It is also already easy to write a Turing-machine simulator in this developed language.  It is not exactly easy, but certainly standard, to write a self-compiler for the language.  Of course you need an outer compiler to create the outer TM from a code in this C-like or Python-like language, but that can be done in any computer language.</p>

<p>Note that this sketched implementation not only supports the logicians' Church-Turing thesis for the recursive function class, but also the extended (i.e., polynomial) Church-Turing thesis as it applies to deterministic computation.  In other words, it has polynomial overhead.   In fact, if we are given a RAM machine or (my personal favorite) a tree-tape TM, this can be reduced to polylogarithmic overhead for serial computation with RAM memory.</p>

CC BY-SA 3.0
2015-05-17T01:50:08.987Z
2015-05-17T01:50:08.987Z
Greg Kuperberg
<p>The LLVM compiler allows one to fairly straightforwardly "plug in" a new architecture.  They call this <em>writing a new back-end</em>, and give <a href="http://llvm.org/docs/WritingAnLLVMBackend.html">detailed instructions and examples</a> for how to do it. I suspect that you will have to jump through some hoops with respect to random access memory, if you do not wish to target a RAM Turing machine, but this is definitely doable, as I've seen a number of projects that cause LLVM to generate VHDL or other very different machine languages. </p>

<p>This would have the interesting effect of having a state-of-the-art optimizing compiler (in many ways LLVM is more advanced than GCC) generating code for a Turing machine.</p>

CC BY-SA 3.0
2013-09-16T06:34:30.683Z
2013-09-16T06:34:30.683Z
apw
<p>I am not in the cs theory but I have somethint which might be usefull. I have taken another approch.  I designed a simple processor directly programmable with a small sub-set of C. There is NO assembly code, only C-like code.  You could use use the same tool I used and modify this processor to design your Turing machine simulator.  It took me 4 days to design, simulate and test this processor, well a few instructions! The Tools I used even enabled me to generate real VHDL synthetizable code.  It is a true working processor.</p>

<p>Here is what a program looks like:
<img src="https://i.sstatic.net/tBxBt.png" alt="Example of C-Like Assembly Program"></p>

<p>Here is a picture of the processor using theses Tools.:
<img src="https://i.sstatic.net/oM7Nv.png" alt="Processor Circuit"></p>

<p>The Tools "Novakod Studio" uses a High Level Language Hardware Description Language.  As an example, here is the code of the program counter:
<img src="https://i.sstatic.net/rzTMz.png" alt="psC - Parallel and synchronous C - code sample">
Enough talking, if anyone is interested, here is the public information to contact me:
<a href="https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&amp;link=1" rel="nofollow noreferrer">https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&amp;link=1</a> </p>

<p>Luc</p>

CC BY-SA 3.0
2013-10-10T18:31:04.627Z
does the memory addressing use a fixed # of bits to locate addresses?
vzn
CC BY-SA 3.0
2013-10-10T21:05:30.423Z
Yes, but it is simple to change memory size (int DataMemory[SIZE]. The language supports variable length integer (int:10). But, since it targets FPGA, array are static and dimension constant.
Luc Morin
CC BY-SA 3.0
2013-10-10T18:25:42.427Z
2013-10-10T18:25:42.427Z
Luc Morin
<p>How about taking the idea represented by user GMB here <em>(Turing machine with one tape can simulate a Turing machine with N tapes by interlacing the N tapes to a single tape and reading any one of those tapes by jumping N locations at a time, a Turing machine with N tapes can implement...)</em> and write a Turing machine program that implements a simplistic RAM-machine. The RAM-machine might actually be some simplistic, real, CPU with available LLVM or GCC backend. Then the GCC/LLVM can be used for cross-compiling a C program for that CPU and the Turing machine program that simulates the RAM-machine, runs the RAM-machine simulation by having the simulated RAM-machine execute the GCC/LLVM output. The Turing machine implementation might be some very simple C code that fits to a small C file.</p>

<p>What regards to the RAM-machine, then there exists a demo project, where a 32bit CPU is simulated by an 8bit microcontroller and the simulated 32bit CPU boots Linux. Slow as hell, but <a href="http://dmitry.gr/index.php?r=05.Projects&amp;proj=07.%20Linux%20on%208bit" rel="nofollow">according to the author</a>, Dmitry Grinberg, it worked. Maybe the Zylin CPU <em>(GitHub user zylin)</em> might be a viable choice for the simulatable RAM-machine. Another RAМ-machine candidate might be the ProjectOberon dot com by <a href="https://www.youtube.com/watch?v=BJIqHIYSDrk" rel="nofollow">Niklaus Wirth</a>. </p>

<p><em>(The "dot" and "com" in my text are due to the fact that I just, 2015_10_21,  registered my account at the cstheory.stackexchange and the web-app does not allow more than 2 links for novice users, despite the fact that they can automatically see from my other stackexchange accounts that I might be stupid, but I'm not a troll.)</em></p>

CC BY-SA 3.0
2015-10-20T21:36:06.947Z
2015-10-20T21:36:06.947Z
Martin Vahi
<p>I am looking for a small language that helps 'convince' students that turing machines are a sufficiently general computing model. That is, a language that looks like the languages they are used to, but is also easy to simulate on a turing machine.</p>

<p>Papadimitriou uses RAM machines for this job, but I fear that comparing something strange (as a turing machine) to another strange thing (basically, an assembly language) would be too unconvincing for many students.</p>

<p>Any suggestions would be most welcome (specially if they came with some recommended literature) </p>

CC BY-SA 3.0
2013-08-19T15:47:31.013Z
There's a reason that computers were originally programmed in assembly language ... writing compilers or interpreters is [not trivial](http://amturing.acm.org/award_winners/backus_0703524.cfm). And writing compilers or interpreters for Turing machines is probably even harder.
Peter Shor 
CC BY-SA 3.0
2013-09-14T21:38:39.823Z
must disagree somewhat with PS, a TM compiler is not so much harder than eg converting factoring instances to SAT or other nearly-undergraduate exercises. see also [top turing machine simulators on the web](http://cs.stackexchange.com/questions/10379/top-turing-machine-simulators-on-the-web). here is an example of a [Turing machine compiler](http://vzn1.wordpress.com/code/turing-machine-compiler/) written in ruby with sample source code (for the high-level language). alas there do not seem to be more polished ones available. it would make a great open source project.
vzn
CC BY-SA 3.0
2015-10-22T06:16:01.173Z
@OmarShehab, An edit pumps up the question to the first page. Please don't edit old question when the edit does not significantly improve the question. Also editing a large number of question which are not on the first page is not good as it pushes new questions out of the first page. Thanks.
Kaveh
CC BY-SA 3.0
2015-10-22T06:17:43.457Z
@kaveh understood.
Omar Shehab
CC BY-SA 4.0
2022-06-25T22:42:38.717Z
A small (but very useful) subset of C maps to a small subset of the x86 language. This in turn maps to a RASP machine (stack operations must be implemented as subroutines). The last step is mapping this RASP machine to a TM. When implemented as software one has a C to RASP to TM compiler.
polcott
<turing-machines>
A small C-like language that turing machines can simulate
josinalvo
# A small C-like language that turing machines can simulate

(Asked by: username_0 on 2013-08-19)

I am looking for a small language that helps 'convince' students that turing machines are a sufficiently general computing model. That is, a language that looks like the languages they are used to, but is also easy to simulate on a turing machine.

Papadimitriou uses RAM machines for this job, but I fear that comparing something strange (as a turing machine) to another strange thing (basically, an assembly language) would be too unconvincing for many students.

Any suggestions would be most welcome (specially if they came with some recommended literature)

**Tags:** turing-machines
> **Comments:**
> **username_1**: There's a reason that computers were originally programmed in assembly language ... writing compilers or interpreters is [not trivial](http://amturing.acm.org/award_winners/backus_0703524.cfm). And writing compilers or interpreters for Turing machines is probably even harder.  
> **username_2**: must disagree somewhat with PS, a TM compiler is not so much harder than eg converting factoring instances to SAT or other nearly-undergraduate exercises. see also [top turing machine simulators on the web](http://cs.stackexchange.com/questions/10379/top-turing-machine-simulators-on-the-web). here is an example of a [Turing machine compiler](http://vzn1.wordpress.com/code/turing-machine-compiler/) written in ruby with sample source code (for the high-level language). alas there do not seem to be more polished ones available. it would make a great open source project.  
> **username_3**: @OmarShehab, An edit pumps up the question to the first page. Please don't edit old question when the edit does not significantly improve the question. Also editing a large number of question which are not on the first page is not good as it pushes new questions out of the first page. Thanks.  
> **username_4**: @kaveh understood.  
> **username_5**: A small (but very useful) subset of C maps to a small subset of the x86 language. This in turn maps to a RASP machine (stack operations must be implemented as subroutines). The last step is mapping this RASP machine to a TM. When implemented as software one has a C to RASP to TM compiler.  

---

## 6 answers

### Answer by username_6 on 2013-08-20. Score: 16

* If your students have done any functional programming, the nicest approach I know is to start with the untyped lambda calculus, and then use the [bracket abstraction theorem](http://www.cantab.net/users/antoni.diller/brackets/intro.html) to translate it into SKI combinators. Then, you can use the $smn$ and $utm$ theorems to show that Turing machines form a [*partial combinatory algebra*](http://ncatlab.org/nlab/show/partial+combinatory+algebra), and so can interpret the SKI combinators.

  I doubt this is the simplest possible approach, but I like how it rests on some of the most fundamental theorems in computability (which you may well wish to cover for other reasons).

  It appears that [Andrej Bauer answered a similar question on Mathoverflow](https://mathoverflow.net/questions/132800/a-proof-that-the-natural-numbers-form-a-pca) a few months back.
* If you are set on a C-like language, your path will be a lot rougher, since they have a rather complicated semantics -- you'll need to

  1. Show that Turing machines can simulate a stack and a heap at the same time, and
  2. Show how variables can be implemented with a stack, and
  3. Show that procedure calls can be implemented with a stack.

  This is much of the contents of a compilers class, honestly.

> **Comments:**
> **username_7**: Number 1 seems rather easy if you have the rest of the language down - a stack is simply an array used in a certain way. Basically you'd go to some sort of assembler before you go down to the Turing level. I'm still trying to understand this myself. Given how often the word Turing-complete is used, it's surprising that nobody REALLY checks whether C and a Turing machine are the same thing.  

---

### Answer by username_8 on 2013-09-14. Score: 8

My Theory of Comp professor in undergrad started by proving that a single-tape Turing machine can implement a multi-tape Turing machine. This handles variable declaration: if a program has six variable declarations, then it can be easily implemented on a seven-tape Turing machine (a tape for each variable, and a "register" tape to help perform tasks like arithmetic and equality-checking between tapes). He then showed how to implement basic FOR and WHILE loops, and at that point we had a basic Turing-complete C-like language. I found it satisfying, anyways.


---

### Answer by username_9 on 2015-05-17. Score: 6

I'm thinking right now about how to convince myself that Turing machines are a general model of computation. I agree that the standard treatment of the Church-Turing thesis in some standard textbooks, e.g. Sipser, is not very complete. Here is a sketch of how I might go from Turing machines to a more recognizable programming language.

Consider a block-structured programming language with `if` and `while` statements, with *non-recursive* defined functions and subroutines, with named *boolean* random variables and general boolean expressions, and with a single unbounded boolean array `tape[n]` with an integer array pointer `n` that can be incremented or decremented, `n++` or `n--`. The pointer `n` is initially zero and the array `tape` is initially all zero. So, this computer language can be C-like or Python-like, but it is very limited in its data types. In fact, they are so limited that we do not even have a way to use the pointer `n` in a boolean expression. Assuming that `tape` is only infinite to the right, we can declare a pointer underflow "system error" if `n` is ever negative. Also, our language has an `exit` statement with one argument, to output a boolean answer.

Then the first point is that this programming language is a good specification language for a Turing machine. You can easily see that, except for the tape array, the code only has finitely many possible states: The state of all of its declared variables, and the current line of execution, and its subroutine stack. The latter only has a finite amount of state because recursive functions are not allowed. You could imagine a "compiler" that creates an "actual" Turing machine from a code of this type, but the details of that are not important. The point is that we have a programming language with pretty good syntax, but very primitive data types.

The rest of the construction is to convert this to a more livable programming language with a finite list of library functions and precompilation stages. We can proceed as follows:

1. With a precompiler, we can expand the boolean data type to a larger but finite symbol alphabet such as ASCII. We can assume that `tape` takes values in this larger alphabet. We can leave a marker at the beginning of the tape to prevent pointer underflow, and a movable marker at the end of the tape to prevent the TM from skating to infinity on the tape accidentally. We can implement arbitrary binary operations between symbols, and conversions to boolean for `if` and `while` statements. (Actually `if` can be implemented with `while` as well, if it weren't available.)
2. We want an unbounded integer data type in order to implement both random access of the tape and (positive) integer arithmetic. To this end, we simulate a $k$-tape TM for some fixed $k$ with the one tape that we have. This construction is given as a theorem in Sipser. The idea is to interleave the emulated tapes on the low-level tape we have, with marker symbols representing the head positions. If the low-level tape pointer is at zero, it services the $i$th subtape by moving to position $i$ and then jumping $k$ steps at a time; after each read or write, the low-level tape pointer decrements back to zero. Just as in the previous stage, it is easier to implement this as a precompiler.
3. We designate one tape as symbol-valued "memory" and the others as unsigned, integer-valued "registers" or "variables". We store the integers in little-endian binary with termination markers. We first implement copy of a register and binary decrement of a register. Combining that with increment and decrement of the memory pointer, we can implement random access seek of the symbol memory. We can also write functions to calculate binary addition and multiplication of integers. It is not hard to write a binary addition function with bitwise operations, and a function to multiply by 2 with left shift. (Or really right shift, since it is little-endian.) With these primitives, we can write a function to multiply two registers using the long multiplication algorithm.
4. We can reorganize the memory tape from a one-dimensional symbol array `symbol[n]` to a two-dimensional symbol array `symbol[x,y]` using the formula `n = (x+y)*(x+y) + y`. We can now use each row of the memory to express an unsigned integer in binary with a termination symbol, to obtain a one-dimensional, random-access, integer-valued memory `memory[x]`. We can implement reading from the memory to an integer register, and writing from a register to the memory. Many features can now be implemented with functions: Signed and floating point arithmetic, symbol strings, etc.
5. Only one more basic facility strictly requires a precompiler, namely recursive functions. This can be done with a technique that is widely used to implement interpreted languages. We assign each high-level, recursive function a name string, and we organize the low-level code into one large `while` loop that maintains a call stack with the usual parameters: the calling point, the called function, and a list of arguments.

At this point, the construction has enough features of a high-level programming language that further functionality is more the topic of programming languages and compilers rather than CS theory. It is also already easy to write a Turing-machine simulator in this developed language. It is not exactly easy, but certainly standard, to write a self-compiler for the language. Of course you need an outer compiler to create the outer TM from a code in this C-like or Python-like language, but that can be done in any computer language.

Note that this sketched implementation not only supports the logicians' Church-Turing thesis for the recursive function class, but also the extended (i.e., polynomial) Church-Turing thesis as it applies to deterministic computation. In other words, it has polynomial overhead. In fact, if we are given a RAM machine or (my personal favorite) a tree-tape TM, this can be reduced to polylogarithmic overhead for serial computation with RAM memory.


---

### Answer by username_10 on 2013-09-16. Score: 5

The LLVM compiler allows one to fairly straightforwardly "plug in" a new architecture. They call this *writing a new back-end*, and give [detailed instructions and examples](http://llvm.org/docs/WritingAnLLVMBackend.html) for how to do it. I suspect that you will have to jump through some hoops with respect to random access memory, if you do not wish to target a RAM Turing machine, but this is definitely doable, as I've seen a number of projects that cause LLVM to generate VHDL or other very different machine languages.

This would have the interesting effect of having a state-of-the-art optimizing compiler (in many ways LLVM is more advanced than GCC) generating code for a Turing machine.


---

### Answer by username_11 on 2013-10-10. Score: 1

I am not in the cs theory but I have somethint which might be usefull. I have taken another approch. I designed a simple processor directly programmable with a small sub-set of C. There is NO assembly code, only C-like code. You could use use the same tool I used and modify this processor to design your Turing machine simulator. It took me 4 days to design, simulate and test this processor, well a few instructions! The Tools I used even enabled me to generate real VHDL synthetizable code. It is a true working processor.

Here is what a program looks like:
![Example of C-Like Assembly Program](https://i.sstatic.net/tBxBt.png)

Here is a picture of the processor using theses Tools.:
![Processor Circuit](https://i.sstatic.net/oM7Nv.png)

The Tools "Novakod Studio" uses a High Level Language Hardware Description Language. As an example, here is the code of the program counter:
![psC - Parallel and synchronous C - code sample](https://i.sstatic.net/rzTMz.png)
Enough talking, if anyone is interested, here is the public information to contact me:
<https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1>

Luc

> **Comments:**
> **username_2**: does the memory addressing use a fixed # of bits to locate addresses?  
> **username_11**: Yes, but it is simple to change memory size (int DataMemory[SIZE]. The language supports variable length integer (int:10). But, since it targets FPGA, array are static and dimension constant.  

---

### Answer by username_12 on 2015-10-20. Score: 1

How about taking the idea represented by user GMB here *(Turing machine with one tape can simulate a Turing machine with N tapes by interlacing the N tapes to a single tape and reading any one of those tapes by jumping N locations at a time, a Turing machine with N tapes can implement...)* and write a Turing machine program that implements a simplistic RAM-machine. The RAM-machine might actually be some simplistic, real, CPU with available LLVM or GCC backend. Then the GCC/LLVM can be used for cross-compiling a C program for that CPU and the Turing machine program that simulates the RAM-machine, runs the RAM-machine simulation by having the simulated RAM-machine execute the GCC/LLVM output. The Turing machine implementation might be some very simple C code that fits to a small C file.

What regards to the RAM-machine, then there exists a demo project, where a 32bit CPU is simulated by an 8bit microcontroller and the simulated 32bit CPU boots Linux. Slow as hell, but [according to the author](http://dmitry.gr/index.php?r=05.Projects&proj=07.%20Linux%20on%208bit), Dmitry Grinberg, it worked. Maybe the Zylin CPU *(GitHub user zylin)* might be a viable choice for the simulatable RAM-machine. Another RAМ-machine candidate might be the ProjectOberon dot com by [Niklaus Wirth](https://www.youtube.com/watch?v=BJIqHIYSDrk).

*(The "dot" and "com" in my text are due to the fact that I just, 2015\_10\_21, registered my account at the cstheory.stackexchange and the web-app does not allow more than 2 links for novice users, despite the fact that they can automatically see from my other stackexchange accounts that I might be stupid, but I'm not a troll.)*


---

