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