No basic lecture in computer science can do without a mention of the Turing machine.
Martín Ugarte has written a very nice programmable simulator for Turing machines that gives students a very practical approach to this otherwise rather theoretical topic.
If you are listening to the lecture "Fundamentals of Computer Science" at the HFT Stuttgart, you will find here, in addition to the examples already explained there, further programs to deepen the topic and for your own experiments.
A guide explains how to use the pages in this website, their behaviour may be adjusted in the settings.
A program for the Turing simulator consists of a preamble and a series of definitions for the state transitions of the Turing machine.
The prefix defines the program name as well as the names of the initial state and the "acceptable" final states. If the Turing machine is in one of the named final states at the end of a program (i.e. when no more suitable state transitions can be found), the program is considered "accepted" (i.e. it has run through without errors) - otherwise an error has occurred.
name: program name
init: name of the initial state
accept: name of a final state, ..., possibly further names
The definition of a state transition consists of two lines each:
name of current state,symbol to be read (or _ for an empty cell)
name of target state,symbol to be written,movement of read/write head
The read/write head can make the following movements
<
- one field to the left>
- one field to the right-
- stay on the same fieldLines beginning with a double slash are considered comment lines and are ignored. Blank lines are also skipped:
// comment line
In the simplest case, the program source text is typed into the input field of the Turing simulator (or copied into it) and translated by clicking on the green "Compile" button.
After a successful translation, the simulator's user interface appears above the input field - otherwise the first translation error found is displayed there.
The user interface can be used to preset the memory band (with one character per field, as entered to the left of "Load") and to control the simulator.
At first, the examples are still trivial, but become successively more complicated. Later examples usually build on previous (simpler) ones.
name: just an (almost) empty program
init: qInit
accept: qAccept
qInit,_
qAccept,_,-
name: skip a single zero
init: q0
accept: q1
q0,0
q1,0,>
name: skip all zeros
init: q0
accept: q0
q0,0
q0,0,>
name: skip a single bit
init: q0
accept: q1
q0,0
q1,0,>
q0,1
q1,1,>
name: skip all bits
init: q0
accept: q0
q0,0
q0,0,>
q0,1
q0,1,>
name: invert a single bit
init: q0
accept: q1
q0,0
q1,1,>
q0,1
q1,0,>
name: invert all bits
init: q0
accept: q0
q0,0
q0,1,>
q0,1
q0,0,>
name: Parity Bit Generator
init: qEvenParity
accept: qAccept
qEvenParity,0
qEvenParity,0,>
qEvenParity,1
qOddParity,1,>
qEvenParity,_
qAccept,0,-
qOddParity,0
qOddParity,0,>
qOddParity,1
qEvenParity,1,>
qOddParity,_
qAccept,1,-
name: shift a single bit to the right
init: q0
accept: q3
q0,0
q1,_,>
q1,_
q3,0,>
q0,1
q2,_,>
q2,_
q3,1,>
name: shift all bits to the right
init: q0
accept: q3
q0,0
q1,_,>
q0,1
q2,_,>
q1,0
q1,0,>
q1,1
q2,0,>
q1,_
q3,0,>
q2,0
q1,1,>
q2,1
q2,1,>
q2,_
q3,1,>
name: shift a single bit to the left
init: q0
accept: q3
q0,0
q1,_,<
q1,_
q3,0,<
q0,1
q2,_,<
q2,_
q3,1,<
name: shift all bits to the left
init: q0
accept: q0
q0,0
q1,_,<
q0,1
q3,_,<
q1,_
q2,0,>
q2,_
q0,_,>
q3,_
q2,1,>
name: increment a single bit
init: q0
accept: q1
q0,0
q1,1,<
q0,1
q2,0,<
q2,_
q1,1,<
name: increment a binary number
init: q0
accept: q3
q0,0
q0,0,>
q0,1
q0,1,>
q0,_
q1,_,<
q1,0
q2,1,<
q1,1
q1,0,<
q1,_
q3,1,<
q2,0
q2,0,<
q2,1
q2,1,<
q2,_
q3,_,-
name: compute 2th complement
init: q0
accept: q1,q2
q0,0
q0,1,>
q0,1
q0,0,>
q0,_
q1,_,<
q1,0
q2,1,<
q1,1
q1,0,<
q2,0
q2,0,<
q2,1
q2,1,<
name: compute conjunction of two bit sequences
init: q0
accept: q0
q0,0
q1,.,>
q0,1
q5,.,>
q1,0
q1,0,>
q1,1
q1,1,>
q1,_
q2,_,>
q2,.
q2,.,>
q2,0
q3,.,>
q2,1
q3,.,>
q3,0
q3,0,>
q3,1
q3,1,>
q3,_
q4,_,>
q4,0
q4,0,>
q4,1
q4,1,>
q4,_
q9,0,<
q5,0
q5,0,>
q5,1
q5,1,>
q5,_
q6,_,>
q6,.
q6,.,>
q6,0
q3,.,>
q6,1
q7,.,>
q7,0
q7,0,>
q7,1
q7,1,>
q7,_
q8,_,>
q8,0
q8,0,>
q8,1
q8,1,>
q8,_
q9,1,<
q9,0
q9,0,<
q9,1
q9,1,<
q9,_
q10,_,<
q10,0
q10,0,<
q10,1
q10,1,<
q10,.
q10,.,<
q10,_
q11,_,<
q11,0
q11,0,<
q11,1
q11,1,<
q11,.
q0,.,>
name: compute disjunction of two bit sequences
init: q0
accept: q0
q0,1
q1,.,>
q0,0
q5,.,>
q1,0
q1,0,>
q1,1
q1,1,>
q1,_
q2,_,>
q2,.
q2,.,>
q2,0
q3,.,>
q2,1
q3,.,>
q3,0
q3,0,>
q3,1
q3,1,>
q3,_
q4,_,>
q4,0
q4,0,>
q4,1
q4,1,>
q4,_
q9,1,<
q5,0
q5,0,>
q5,1
q5,1,>
q5,_
q6,_,>
q6,.
q6,.,>
q6,1
q3,.,>
q6,0
q7,.,>
q7,0
q7,0,>
q7,1
q7,1,>
q7,_
q8,_,>
q8,0
q8,0,>
q8,1
q8,1,>
q8,_
q9,0,<
q9,0
q9,0,<
q9,1
q9,1,<
q9,_
q10,_,<
q10,0
q10,0,<
q10,1
q10,1,<
q10,.
q10,.,<
q10,_
q11,_,<
q11,0
q11,0,<
q11,1
q11,1,<
q11,.
q0,.,>
name: compute the sum of two binary numbers
init: q0
accept: q0
q0,0
q1,.,>
q0,1
q8,.,>
q1,0
q1,0,>
q1,1
q1,1,>
q1,_
q2,_,>
q2,.
q2,.,>
q2,0
q3,.,>
q2,1
q10,.,>
q3,0
q3,0,>
q3,1
q3,1,>
q3,_
q4,_,>
q4,0
q4,0,>
q4,1
q4,1,>
q4,_
q5,0,<
q5,0
q5,0,<
q5,1
q5,1,<
q5,_
q6,_,<
q6,0
q6,0,<
q6,1
q6,1,<
q6,.
q6,.,<
q6,_
q7,_,<
q7,0
q7,0,<
q7,1
q7,1,<
q7,.
q0,.,>
q8,0
q8,0,>
q8,1
q8,1,>
q8,_
q9,_,>
q9,.
q9,.,>
q9,0
q10,.,>
q9,1
q12,.,>
q10,0
q10,0,>
q10,1
q10,1,>
q10,_
q11,_,>
q11,0
q11,0,>
q11,1
q11,1,>
q11,_
q5,1,<
q12,0
q12,0,>
q12,1
q12,1,>
q12,_
q13,_,>
q13,0
q13,0,>
q13,1
q13,1,>
q13,_
q14,0,<
q14,0
q5,1,<
q14,1
q14,0,<
Addition of two unsigned binary Numbers (according to Coors)
If you are listening to my lecture "Fundamentals of Computer Science", you will find another Turing program for the addition of binary numbers in the slides of Prof. Coors.
convert the state diagram from Prof. Coors' slides into a program for the simulator
qPre,0
qPre,0,>
qPre,1
qPre,1,>
qPre,_
q1,_,>
q0
, but qPre
.name: compute the sum of two binary numbers
init: qPre
accept: q8
qPre,0
qPre,0,>
qPre,1
qPre,1,>
qPre,_
q1,_,>
q0,_
q1,_,>
q1,0
q1,0,>
q1,1
q2,1,>
q1,_
q3,_,<
q2,0
q2,0,>
q2,1
q2,1,>
q2,_
q4,_,<
q3,0
q3,_,<
q3,_
q8,_,<
q4,0
q4,1,<
q4,1
q5,0,<
q5,0
q5,0,<
q5,1
q5,1,<
q5,_
q6,_,<
q6,0
q7,1,>
q6,1
q6,0,<
q6,_
q7,1,>
q7,0
q7,0,>
q7,1
q7,1,>
q7,_
q1,_,>
Test the program by entering "1001_100"
(how does the program perform the addition?)
Turing machines are mainly used for theoretical considerations - in practice they have no meaning at all.
A well-known question is: how many "1 "s can a Turing machine with n states write to a memory tape initially filled with "0 "s and then stop(!)?
Turing programs that fulfil this condition are called "busy beavers".
The solution for a Turing program with only one state is obvious:
Below are examples of "busy beavers" with up to six states. The last two programs are only considered "candidates" for a "busy beaver" because they can no longer be tested practically due to their immense running time.
However, the first four examples can still be tried out well in the simulator.
name: busy beaver with one state
init: q0
accept: q1
q0,_
q1,1,>
name: busy beaver with two states
init: q0
accept: q2
q0,_
q1,1,>
q0,1
q1,1,<
q1,_
q0,1,<
q1,1
q2,1,>
name: busy beaver with three states
init: q0
accept: q3
q0,_
q1,1,>
q0,1
q3,1,>
q1,_
q2,_,>
q1,1
q1,1,>
q2,_
q2,1,<
q2,1
q0,1,<
name: busy beaver with four states
init: q0
accept: q4
q0,_
q1,1,>
q0,1
q1,1,<
q1,_
q0,1,<
q1,1
q2,_,<
q2,_
q4,1,>
q2,1
q3,1,<
q3,_
q3,1,>
q3,1
q0,_,>
name: busy beaver with five states
init: q0
accept: q5
q0,_
q1,1,>
q0,1
q2,1,<
q1,_
q2,1,>
q1,1
q1,1,>
q2,_
q3,1,>
q2,1
q4,_,<
q3,_
q0,1,<
q3,1
q3,1,<
q4,_
q5,1,>
q4,1
q0,_,<
name: busy beaver with six states
init: q0
accept: q6
q0,_
q1,1,>
q0,1
q4,1,<
q1,_
q2,1,>
q1,1
q5,1,>
q2,_
q3,1,<
q2,1
q1,_,>
q3,_
q4,1,>
q3,1
q2,_,<
q4,_
q0,1,<
q4,1
q3,_,>
q5,_
q6,1,<
q5,1
q2,1,>
A "universal Turing machine" is a Turing machine that can simulate another Turing machine.
While in a simple Turing machine the "program" (more precisely: the set of all states and state transitions) is fixed and not accessible for the machine itself, in a universal Turing machine both the data (i.e. the contents of the memory tape) and the state machine of the Turing machine to be simulated are stored on the memory tape - only the ability of the universal Turing machine to simulate is fixed.
A universal Turing machine is thus a simple model for a universal computer.
There are now a number of examples of universal Turing machines, the best known of which is probably the binary data machine developed by Marvin Minsky in 1967.
For the sake of clarity, Marvin Minsky greatly simplified the shown state diagram: he assumed that his universal Turing machine should simply skip symbols not explicitly mentioned in the diagram in each state (a detail that will concern us below).
name: Universal Turing Machine (by Marvin Minsky)
// see https://github.com/intrinsic-propensity/turing-machine
init: p0
accept: q0
p0,0
p0,0,>
p0,1
p0,1,>
p0,A
p0,A,>
p0,B
p0,B,>
p0,M
p0,M,>
p0,S
p0,S,>
p0,Y
p0,Y,>
p0,X
p0,X,>
p0,_
p1,_,<
p1,0
p1,0,<
p1,Y
p2,Y,<
p2,0
p2,0,<
p2,1
p2,1,<
p2,X
p2,X,<
p2,Y
p3,Y,>
p3,0
p3,0,>
p3,1
p3,1,>
p3,X
q6,X,<
// transitions mentioned in the diagram
q1,0
q3,A,<
q1,1
q4,B,>
q2,A
q1,0,>
q2,B
q5,1,>
q2,X
q7,X,>
q3,Y
q2,Y,>
q4,X
q6,X,<
q4,Y
q0,Y,-
q5,0
q4,A,>
q5,1
q3,B,<
q6,0
q6,A,<
q6,1
q6,B,<
q6,Y
q2,Y,>
q7,0
q9,A,<
q7,1
q8,B,<
q8,Y
q10,Y,>
q9,Y
q11,Y,>
q10,0
q12,B,>
q10,1
q12,B,>
q10,X
q13,X,<
q11,0
q12,A,>
q11,1
q12,A,>
q11,X
q14,X,<
q12,X
q7,X,>
q13,M
q15,B,>
q14,M
q15,A,>
q15,A
q15,0,>
q15,B
q15,1,>
q15,X
q16,X,>
q16,0
q17,0,<
q16,1
q17,1,<
q17,0
q22,S,<
q17,1
q23,S,<
q17,A
q17,0,<
q17,B
q17,1,<
q18,S
q6,A,<
q19,S
q6,B,<
q20,0
q18,M,>
q20,1
q19,M,>
q21,0
q18,M,>
q21,1
q19,M,>
q22,A
q21,0,<
q22,B
q20,1,>
q23,A
q21,1,<
q23,B
q20,1,>
// important transitions not mentioned in the diagram but implicitly being
// part of Marvin Minsky's implementation
q1,A
q1,A,>
q1,B
q1,B,>
q1,X
q1,X,>
q2,0
q2,0,>
q2,1
q2,1,>
q3,0
q3,0,<
q3,1
q3,1,<
q3,A
q3,A,<
q3,B
q3,B,<
q3,X
q3,X,<
q4,0
q4,0,>
q4,1
q4,1,>
q5,A
q5,A,>
q5,B
q5,B,>
q5,X
q5,X,>
q6,A
q6,A,<
q6,B
q6,B,<
q6,X
q6,X,<
q7,A
q7,A,>
q7,B
q7,B,>
q7,X
q7,X,>
q8,0
q8,0,<
q8,1
q8,1,<
q8,A
q8,A,<
q8,B
q8,B,<
q8,X
q8,X,<
q9,0
q9,0,<
q9,1
q9,1,<
q9,A
q9,A,<
q9,B
q9,B,<
q9,X
q9,X,<
q10,A
q10,A,>
q10,B
q10,B,>
q11,A
q11,A,>
q11,B
q11,B,>
q12,0
q12,0,>
q12,1
q12,1,>
q13,0
q13,0,<
q13,1
q13,1,<
q13,A
q13,A,<
q13,B
q13,B,<
q13,Y
q13,Y,<
q14,0
q14,0,<
q14,1
q14,1,<
q14,A
q14,A,<
q14,B
q14,B,<
q14,Y
q14,Y,<
q15,0
q15,0,>
q15,1
q15,1,>
q15,Y
q15,Y,>
q16,A
q16,A,>
q16,B
q16,B,>
q16,X
q16,X,>
q16,Y
q16,Y,>
q17,X
q17,X,<
q17,Y
q17,Y,<
q18,0
q18,0,>
q18,1
q18,1,>
q18,Y
q18,Y,>
q19,0
q19,0,>
q19,1
q19,1,>
q19,Y
q19,Y,>
q22,0
q22,0,<
q22,1
q22,1,<
q22,Y
q22,Y,<
q23,0
q23,0,<
q23,1
q23,1,<
q23,Y
q23,Y,<
// dangerous transitions not mentioned in the diagram but implicitly being
// part of Marvin Minsky's implementation
q2,M
q2,M,>
q3,M
q3,M,<
q6,M
q6,M,<
q7,Y
q7,Y,>
q8,S
q8,S,<
q9,M
q9,M,<
q9,S
q9,S,<
q10,S
q10,S,>
q11,M
q11,M,>
q11,S
q11,S,>
q12,S
q12,S,>
q13,X
q13,X,<
q13,S
q13,S,<
q14,X
q14,X,<
q14,S
q14,S,<
q16,S
q16,S,>
q17,S
q17,S,<
q18,A
q18,A,>
q18,B
q18,B,>
q18,X
q18,X,>
q19,A
q19,A,>
q19,B
q19,B,>
q19,X
q19,X,>
q20,A
q20,A,>
q20,B
q20,B,>
q20,S
q20,S,>
q20,X
q20,X,>
q20,Y
q20,Y,>
q21,A
q21,A,<
q21,S
q21,S,<
q21,B
q21,B,<
q21,X
q21,X,<
q21,Y
q21,Y,<
To simulate a Turing machine, a description of its state machine must be written to the memory tape of the universal Turing machine along with its initial state.
The states of the machine to be simulated are numbered consecutively for this purpose. Since the data must be available in binary form, the state numbers are specified as binary numbers of fixed length - the minimum number of required digits (bits) results from the total number of states used (e.g. 3 for up to 8 states 0...7). As we will see, more digits may be used (at the expense of simulation speed), but the minimum number must not be fallen short of.
The content is composed as follows (from left to right):
A concrete target state cannot be specified. Instead, the universal Turing machine (in most cases) simply stops as soon as it can no longer find a suitable state transition for the current state of the simulated machine.
Loading can be easily demonstrated with a simple example.
A Turing machine is to be simulated which repeatedly converts a "0" read from the memory tape into a "1" and then moves the read/write head to the right - until it encounters a "1" on the tape.
In the notation of the simulator used here, the corresponding state machine is:
q0,0
q0,1,>
If the simulated memory tape is to initially contain two "0"s and one "1" and the simulated read/write head is to be located on the first "0", the tape of the universal Turing machine must be loaded as follows:
M
to mark the simulated head position.01
for the second "0" and the following "1"Y
0
because the initial state has the number 00
because the M
on the simulated memory tape covers the first "0"X
0
to define a transition from state number 00
because a "0" is expected on the tape0
because the destination state is also state 01
because a "1" is to be written1
because the head is to be moved to the rightY0
because this is the end of the definition,resulting in M01Y00X00011Y0
Program the Turing machine simulator with the source code for the universal Turing machine shown above (don't forget to Compile!) and load the memory tape with the string M01Y00X00011Y0
.
If you now press the start button, the Turing simulator will start simulating a universal Turing machine, which in turn simulates a simple Turing machine.
An article by Pontus Johnson has shown that even systems as simple as universal Turing machines are not immune to outside attacks.
In the specific case, the universal Turing machine was cleverly loaded in such a way that it does not simulate the actual Turing machine described, but executes code that is actually hidden in the "data" (i.e. on the simulated memory tape).
The reason for this vulnerability lies in Marvin Minsky's "simplification" or assumption that any state in the diagram should skip symbols after reading, which were not explicitly mentioned in the diagram.
The concrete example of such an attack is based on a binary counter being the Turing machine that is actually to be simulated.
In the notation of the simulator used here, the state machine for this binary counter is:
name: binary counter
init: q0
accept: q2
q0,0
q0,0,>
q0,1
q1,1,<
q1,0
q0,1,>
q1,1
q1,0,<
name: binary counter
init: q0
accept: q2
q0,0
q0,0,>
q0,1
q1,1,<
q1,0
q0,1,>
q1,1
q1,0,<
To run this counter, the memory tape must be loaded with a sequence of "0"s and a "1" at the end. The number of leading "0"s determines the number of bits available to the counter - the Turing machine terminates as soon as the counter generates an overflow, i.e. the number of available bits is no longer sufficient.
It is therefore expedient to limit testing in the simulator to two "0"s, i.e. to load the memory tape with 001
.
Thus, from the initial value for the memory band, the initial state q0, and the list of state transitions, the following content for the memory band of the universal Turing machine shown above is obtained:
M01
Y
00
X
00
00
1
X
01
11
0
X
10
01
1
X
11
10
0
Y0
or in summary M01Y00X00001X01110X10011X11100Y0
.
In the Turing simulator, let the universal Turing machine simulate the binary counter (at maximum speed) and at the end (after 1333 execution steps) check the contents of the simulated memory tape using "show output".
For simplicity, the goal of the attack is to erase the simulated memory tape (instead of counter execution).
This can be done with a simple program
q0,0
q0,0,<
q0,1
q0,0,<
or written in the notation of the universal Turing machine:
X00000X01000
According to the instructions described in the above-mentioned publication, the attack thus has the form
1111YBAXAAAAAXABAAAS
For the attack to work, the initial state for the binary numerator must be chosen such that
Also, the read/write tape for the counter must not be too short (and should be at least 4 cells wide)
All together results in:
1111YBAXAAAAAXABAAASM000Y01X00001X01110X10011X11100Y0
With the initial allocation just constructed for the memory tape of the universal Turing machine
1111YBAXAAAAAXABAAASM000Y01X00001X01110X10011X11100Y0
the attack can be carried out in the simulator.
As soon as you start execution, the Turing machine is attacked and instead of the binary counter the injected code runs which overwrites the left side of the memory tape (within 1413 steps) with zeros.
The cause for the vulnerability of the universal Turing machine is a number of state transitions that are not explicitly mentioned, but implicitly assumed - many of which are mandatory for the correct functioning of the universal Turing machine. Other implicit state transitions, on the other hand, cause the Turing machine to simply skip over actually erroneous data on the memory tape - even though aborting the simulation would be the only correct behavior.
In the source code of the universal Turing machine for the Turing machine simulator used here, you will find these state transitions in the section "dangerous transitions".
If these transitions are removed, the Turing machine remains fully functional, but is no longer attackable.
Thus, the version of the universal Turing machine published by Marvin Minsky assumes that the input data is correct and "for intended use" only and, for simplicity, omits any verification (implicit or explicit).
Comparable problems are also faced by most of today's software: out of laziness or to keep the source code short, many programmers do not validate input data - and this despite the fact that exploiting such loopholes accounts for a large part of actual attacks in the real world.
Conversely, however, this also means that software can be "hardened" in a fairly simple manner by (possibly subsequently) adding input validations.
At this point, the author would like to explicitly thank Pontus Johnson (the discoverer of the described vulnerability) for his assistance in porting Marvin Minsky's universal Turing machine and performing the demonstrated attack.
This web page uses the following third-party libraries, assets or StackOverflow answers:
The author would like to thank the developers and authors of the above-mentioned contributions for their effort and willingness to make their works available to the general public.