9. Turing Machine in Python

By Bernd Klein. Last modified: 21 Feb 2025.

Just to let you know straight-away: The Turing machine is not a machine. It is a mathematical model, which was formulated by the English mathematician Alan Turing in 1936. It's a very simple model of a computer, yet it has the complete computing capability of a general purpose computer. The Turing machine (TM) serves two needs in theoretical computer science:

1. The class of languages defined by a TM, i.e. structured or recursively enumerable languages
2. The class of functions a TM is capable to compute, i.e. the partial recursive functions

A Turing machine consists only of a few components: A tape on which data can be sequentially stored. The tape consists of fields, which are sequentially arranged. Each field can contain a character of a finite alphabet. This tape has no limits, it goes on infinitely in both directions. In a real machine, the tape would have to be large enough to contain all the data for the algorithm. A TM also contains a head moving in both directions over the tape. This head can read and write one character from the field over which the head resides. The Turing machine is at every moment in a certain state, one of a finite number of states. A Turing program is a list of transitions, which determine for a given state and character ("under" the head) a new state, a character which has to be written into the field under the head and a movement direction for the head, i.e. either left, right or static (motionless).

Formal Definition of a Turing machine

A deterministic Turing machine can be defined as a 7-tuple

M = (Q, Σ, Γ, δ, b, q₀, q_f)

with

• Q is a finite, non-empty set of states
• Γ is a finite, non-empty set of the tape alphabet
• Σ is the set of input symbols with Σ ⊂ Γ
• δ is a partially defined function, the transition function:
  δ : (Q \ {q_f}) x Γ → Q x Γ x {L,N,R}
• b ∈ &Gamma \ Σ is the blank symbol
• q₀ ∈ Q is the initial state
• q_f ∈ Q is the set of accepting or final states

Live Python training

Enjoying this page? We offer live Python training courses covering the content of this site.

See our Python training courses

See our Machine Learning with Python training courses

Example: Binary Complement function

Let's define a Turing machine, which complements a binary input on the tape, i.e. an input "1100111" e.g. will be turned into "0011000".
Σ = {0, 1}
Q = {init, final}
q₀ = init
q_f = final