# A small C-like language that turing machines can simulate

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)

• There's a reason that computers were originally programmed in assembly language ... writing compilers or interpreters is not trivial. And writing compilers or interpreters for Turing machines is probably even harder. – Peter Shor Aug 19 '13 at 15:47
• 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. here is an example of a 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 Sep 14 '13 at 21:38
• @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 Oct 22 '15 at 6:16
• @kaveh understood. – Omar Shehab Oct 22 '15 at 6:17

• 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 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, 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 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.

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.

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.

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

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:

Here is a picture of the processor using theses Tools.:

The Tools "Novakod Studio" uses a High Level Language Hardware Description Language. As an example, here is the code of the program counter: 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

• does the memory addressing use a fixed # of bits to locate addresses? – vzn Oct 10 '13 at 18:31
• 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 Oct 10 '13 at 21:05

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, 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.

(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.)