A Turing machine is a theoretical model which was developed by Alan Turing in 1936. It consists of an infinite tape that is divided into squares on which symbols of a particular alphabet can be written. The tape acts as a storage and each square can either be empty or contain a symbol such as “1” or “0”. Furthermore, the Turing machine has a read/write head, which can move along the tape to read, write or change symbols.

The read/write head reads a symbol and executes an action based on the current state of the machine. The machine is always in a particular state, and for each state, there is a transition function that indicates what is supposed to happen when a particular symbol is being read by the read/write head. This transition function decides which symbol will be written, into which state the machine will transition and in which direction the read/write head is supposed to move (to the left or to the right).

The Turing machine is working step by step by initially considering the state and the read symbol and then executing an action in accordance with the transition function. The actions repeat until the machine comes to a standstill which shows that the computation is finished. In this state, the machine stops. Moreover, it is also possible that the machine never comes to a standstill.

What is special about the Turing machine is the fact that it offers a theoretical model for all computable processes. It shows that anything that can be computed by a Turing machine is considered algorithmically solvable. But also, that there are problems that no Turing machine can solve.

Overall, the Turing machine is a fundamental concept in informatics because it reflects the limits of computing and the principles of formulating algorithms in their simplest and most abstract form. It helps to understand what is considered “computable” in the first place and what isn’t.

• the finite set of states S,
• the finite input alphabet Σ,
• the tape alphabet П including П ⊃ Σ,
• the state transition function δ : S × П → S × П × {←, →},
• the start state s₀,
• the blank symbol ☐ ∈ П ∖ Σ,
• the set of final states Ε ⊆ S.

Hoffmann, D. W. (2022). Theoretische Informatik (5., aktualisierte Auflage). Carl Hanser Verlag München.

On this page, you will find a Turing machine simulator, which is meant to simply and intuitively showcase how a Turing machine works.

Before you can execute the simulator, you must fill in the following fields.

Here, you type in the initial word which is supposed to be on the tape initially.

Here, you type in the state which is to be used as the start state.

Here, you type in the states which lead to a positive end of the Turing machine.

Here, you type in all transition functions of the Turing machine.

Make sure to observe the following pattern:

[Current state] [Current symbol] [->] [New state] [New symbol] [Direction of movement L/R/N]

L = Movement to the left, R = Movement to the right, N = Neutral movement

Example: [q0] [1] [->] [q1] [0] [R]

There are six buttons for controlling the simulator:

Resets the machine to its original state.

Transfers the start tape to the internal storage and initializes the machine.

Pauses the execution of the current machine.

Executes a single step of computation in accordance with the transition function.

Runs the entire program with the speed of execution being adjustable.

Loads a predefined configuration and initializes the simulator with it.