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