Andreas Rozek
[ Imprint ]   [ Data Privacy Statement ]   [ Contact ]       [ deutsche Fassung ]   english version

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:

  1. 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.
  2. 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.
Fig. 1: User interface of the Turing simulator
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)
    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
    name: skip a single zero
    init: q0
    accept: q1

    q0,0
    q1,0,>
    Fig. 2: Zustandsdiagramm
    Fig. 2: Zustandsdiagramm
  • Skip all subsequent "0 "s
    name: skip all zeros
    init: q0
    accept: q0

    q0,0
    q0,0,>
    Fig. 3: Zustandsdiagramm
    Fig. 3: Zustandsdiagramm
  • Skipping a single Bit
    . A "bit" here is a field on the memory tape with the content "0" or "1".
    name: skip a single bit
    init: q0
    accept: q1

    q0,0
    q1,0,>

    q0,1
    q1,1,>
    Fig. 4: Zustandsdiagramm
    Fig. 4: Zustandsdiagramm
  • Skip all subsequent Bits
    name: skip all bits
    init: q0
    accept: q0

    q0,0
    q0,0,>

    q0,1
    q0,1,>
    Fig. 5: Zustandsdiagramm
    Fig. 5: Zustandsdiagramm
  • Invert a single Bit
    name: invert a single bit
    init: q0
    accept: q1

    q0,0
    q1,1,>

    q0,1
    q1,0,>
    Fig. 6: Zustandsdiagramm
    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.
    name: invert all bits
    init: q0
    accept: q0

    q0,0
    q0,1,>

    q0,1
    q0,0,>
    Fig. 7: Zustandsdiagramm
    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.
    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
    name: shift a single bit to the right
    init: q0
    accept: q3

    q0,0
    q1,_,>

    q1,_
    q3,0,>

    q0,1
    q2,_,>

    q2,_
    q3,1,>
    Fig. 8: Zustandsdiagramm
    Fig. 8: Zustandsdiagramm
  • Right-shifting all subsequent Bits
    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,>
    Fig. 9: Zustandsdiagramm
    Fig. 9: Zustandsdiagramm
  • Left-shifting a single Bit
    name: shift a single bit to the left
    init: q0
    accept: q3

    q0,0
    q1,_,<

    q1,_
    q3,0,<

    q0,1
    q2,_,<

    q2,_
    q3,1,<
    Fig. 10: Zustandsdiagramm
    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.
    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,>
    Fig. 11: Zustandsdiagramm
    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.
    name: increment a single bit
    init: q0
    accept: q1

    q0,0
    q1,1,<

    q0,1
    q2,0,<

    q2,_
    q1,1,<
    Fig. 12: Zustandsdiagramm
    Fig. 12: Zustandsdiagramm
  • Incrementing a multi-Digit binary Number
    This program increments any binary number written to the memory tape.
    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,_,-
    Fig. 13: Zustandsdiagramm
    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.
    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,<
    Fig. 14: Zustandsdiagramm
    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.
    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,.,>
    Fig. 15: Zustandsdiagramm
    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.
    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,.,>
    Fig. 16: Zustandsdiagramm
    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.
    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,<
    Fig. 17: Zustandsdiagramm
    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.
      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
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
    name: busy beaver with one state
    init: q0
    accept: q1

    q0,_
    q1,1,>
  • "Busy Beaver" with two states
    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
    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
    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
    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
    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.