[ Imprint ] [ Data Privacy Statement ] [ Contact ] [

]

Turing Machine

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.

Programming

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:

the first line defines the name of the state and the symbol that must be read from the memory tape so that the state transition just to be defined can take place.
the second line defines the name of the target state, specifies the symbol to be written into the current cell of the memory tape and defines in which direction the read/write head is to be moved afterwards.

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 field

Lines beginning with a double slash are considered comment lines and are ignored. Blank lines are also skipped:

// comment line

Work Flow

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.

Nota bene: you must still click "Load" even if you do not want to preallocate the memory band, but leave it empty.

and this is what it looks like.

Fig. 1: User interface of the Turing simulator

A few examples of Turing programs

At first, the examples are still trivial, but become successively more complicated. Later examples usually build on previous (simpler) ones.

An (almost) empty Program (to test translator and simulator)

Source Code

name: just an (almost) empty program
init: qInit
accept: qAccept

qInit,_
qAccept,_,-

Skipping a single "0"
Skipping fields on the memory tape is one of the most common actions in Turing programs
Source Code
```
name: skip a single zero
init: q0
accept: q1

q0,0
q1,0,>
```
State Diagram

Fig. 2: Zustandsdiagramm

Skip all subsequent "0 "s
Source Code
```
name: skip all zeros
init: q0
accept: q0

q0,0
q0,0,>
```
State Diagram

Fig. 3: Zustandsdiagramm

Skipping a single Bit
. A "bit" here is a field on the memory tape with the content "0" or "1".
Source Code
```
name: skip a single bit
init: q0
accept: q1

q0,0
q1,0,>

q0,1
q1,1,>
```
State Diagram

Fig. 4: Zustandsdiagramm

Skip all subsequent Bits
Source Code
```
name: skip all bits
init: q0
accept: q0

q0,0
q0,0,>

q0,1
q0,1,>
```
State Diagram

Fig. 5: Zustandsdiagramm

Invert a single Bit
Source Code
```
name: invert a single bit
init: q0
accept: q1

q0,0
q1,1,>

q0,1
q1,0,>
```
State Diagram

Fig. 6: Zustandsdiagramm

Invert all the subsequent Bits
Load the memory tape with a sequence of bits (i.e. a sequence of "0" and "1") and watch the Turing machine invert them bit by bit.
Source Code
```
name: invert all bits
init: q0
accept: q0

q0,0
q0,1,>

q0,1
q0,0,>
```
State Diagram

Fig. 7: Zustandsdiagramm

Writing a parity Bit
This is the example from the lecture: load the memory tape with a bit sequence (i.e. a sequence of "0" and "1") and watch the Turing machine add a parity bit.

Source Code

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

Right-shifting a single Bit

Source Code

name: shift a single bit to the right
init: q0
accept: q3

q0,0
q1,_,>

q1,_
q3,0,>

q0,1
q2,_,>

q2,_
q3,1,>

State Diagram

Fig. 8: Zustandsdiagramm

Right-shifting all subsequent Bits

Source Code

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

State Diagram

Fig. 9: Zustandsdiagramm

Left-shifting a single Bit

Source Code

name: shift a single bit to the left
init: q0
accept: q3

q0,0
q1,_,<

q1,_
q3,0,<

q0,1
q2,_,<

q2,_
q3,1,<

State Diagram

Fig. 10: Zustandsdiagramm

Left-shifting of all subsequent Bits
This example is not a mirror-image copy of the program for shifting several bits to the right, but also works through the bit sequence from left to right.
Source Code
```
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,>
```
State Diagram

Fig. 11: Zustandsdiagramm

Increment a single-Digit binary Number
Load the memory tape with a single "0" or "1", the program will increment this binary number by 1.
Source Code
```
name: increment a single bit
init: q0
accept: q1

q0,0
q1,1,<

q0,1
q2,0,<

q2,_
q1,1,<
```
State Diagram

Fig. 12: Zustandsdiagramm

Incrementing a multi-Digit binary Number
This program increments any binary number written to the memory tape.
Source Code
```
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,_,-
```
State Diagram

Fig. 13: Zustandsdiagramm

Form the 2's complement for a given binary Number
Load the memory tape with an arbitrary binary number and follow how the Turing machine forms the 2's complement of this number.
Source Code
```
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,<
```
State Diagram

Fig. 14: Zustandsdiagramm

Bitwise conjunction of two Bit Sequences
Load the memory tape with two arbitrary (but equally long) bit sequences and leave exactly one field free between them - in the Turing simulator you achieve this by an underscore ("_"), a space is not accepted as input. The Turing machine will write a bitwise conjunctive combination of your inputs on the tape after the second bit sequence.

Source Code

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

State Diagram

Fig. 15: Zustandsdiagramm

Bitwise disjunction of two Bit Sequences
Load the memory tape with two arbitrary (but equally long) bit sequences and leave exactly one field free between them - in the Turing simulator you achieve this by an underscore ("_"), a space is not accepted as input. The Turing machine will write a bitwise disjunctive combination of your inputs on the tape after the second bit sequence.

Source Code

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

State Diagram

Fig. 16: Zustandsdiagramm

Addition of two unsigned binary Numbers
Load the memory tape with any two unsigned binary numbers (but of equal length) and leave exactly one space between them - in the Turing simulator you achieve this by an underscore ("_"), a space is not accepted as input. The Turing machine will write the sum of your input behind the second number on the tape - if the number of bits you have specified is sufficient for this.
The program proceeds somewhat differently than you are used to from the lecture: the two numbers are added up bit by bit from left to right and any digit carryovers are entered immediately - in this way, a final overflow can possibly be detected quite early during the calculation.
Source Code
```
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,<
```
State Diagram

Fig. 17: Zustandsdiagramm

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.
1. convert the state diagram from Prof. Coors' slides into a program for the simulator
  Nota bene: Prof. Coors' program starts the addition in the middle of the memory tape (which is generally perfectly acceptable). However, in order for the simulator to do something with it, the read/write head must first be moved to this position by the following initial lines:
```
qPre,0
qPre,0,>

qPre,1
qPre,1,>

qPre,_
q1,_,>
```
  The new initial state is therefore no longer q0, but qPre.
  Source Code (for Verification)
```
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,_,>
```
2. Test the program by entering "1001_100"
  (how does the program perform the addition?)

Busy beavers

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:

Fig. 18: State Diagram for a "busy Beaver" with one State

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.

"Busy Beaver" with a single State

Source Code

name: busy beaver with one state
init: q0
accept: q1

q0,_
q1,1,>

"Busy Beaver" with two states

Source Code

name: busy beaver with two states
init: q0
accept: q2

q0,_
q1,1,>

q0,1
q1,1,<

q1,_
q0,1,<

q1,1
q2,1,>

"Busy Beaver" with three states

Source Code

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

"Busy Beaver" with four states

Source Code

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

Candidate for a "Busy Beaver" with five States

Source Code

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

Candidate for a "Busy Beaver" with six States

Source Code

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

Universal Turing Machine

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.

Nota bene: all materials needed to perform the experiments in this and in the following chapter can be found on this web page as well as on Github.

Universal Turing Machine by Marvin Minsky

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.

Fig. 19: Simplified State Diagram for the Universal Turing Machine by Marvin Minsky

(Quelle: Minsky, M.L. Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice-Hall, 1967, p. 142.)

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

Source Code for the Turing Machine Simulator

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

Nota bene: Due to the behavior of the Turing simulator used here (the read/write head is always placed on the left end of the memory tape), the universal Turing machine shown in the diagram must be preceded by a "preamble" that moves the read/write head to where Marvin Minsky's implementation initially expects it to be.

Loading the Universal Turing Machine

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

the content of the memory tape to be simulated, where the location of the simulated read/write head is marked by an "M",
a "Y"
the number of the starting state of the simulated Turing machine, followed by the value of the simulated memory tape at the position of the simulated read/write head (as this cell has been overwritten with an "M" before)
next are the state transitions of the simulated machine in any order. Each transition is coded as follows:
- an "X"
- followed by the number of the initial state and the expected value at the location of the simulated read/write head
- followed by the number of the target state and the value to be written to the simulated memory tape
- followed by the desired movement direction of the simulated read/write head ("0" stands for left, "1" for right)
the end of this list is followed by another "Y0".

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.

A simple Example

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 0
0 because the M on the simulated memory tape covers the first "0"
X
0 to define a transition from state number 0
0 because a "0" is expected on the tape
0 because the destination state is also state 0
1 because a "1" is to be written
1 because the head is to be moved to the right
Y0 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.

Nota bene: Unfortunately, you cannot move the display of the memory tape in the Turing machine simulator. Since the universal Turing machine often stops in such a way that the simulated memory tape cannot be viewed in its entirety, it is recommended to click on "show output" at the top right of "rejected" at the end. This opens a display that shows the complete content of the memory tape in text form.

Vulnerability of Universal Turing Machines

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.

Actually to be simulated: a Binary Counter

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

Source Code

name: binary counter
init: q0
accept: q2

q0,0
q0,0,>

q0,1
q1,1,<

q1,0
q0,1,>

q1,1
q1,0,<

Binary Counter for the Universal Turing Machine

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

Actually executed: an Eraser Program

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

the read/write head of the machine being simulated is at the left end of its memory tape and sees a "1", and
in conjunction with the initial state is pointed to a state transition (of the binary counter) that writes a "1" and moves the read/write head to the left.

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

The Attack

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.

Reasoning and Hardening

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.

Nota bene: in the sense of the IPO model, the term "input" is not limited to user input in the strict sense. Rather, "input" refers to all types of data that are fed to a program from the outside.

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.

Credits

This web page uses the following third-party libraries, assets or StackOverflow answers:

Font Awesome Free 4.7.0
License: SIL Open Font License (OFL)
answer to StackOverflow question How to get the global object in JavaScript?
contributed by Christian C. Salvadó
License: CC BY-SA 2.5
jQuery - jQuery JavaScript Library
Copyright OpenJS Foundation and other contributors, https://openjsf.org/
License: MIT License

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.

https://www.rozek.de/Turing-Machine/index_en.html

05/24/2021