A Turing machine (TM) is a model of computation. You can think of it as a kind of computer.

It takes an input, does some computation, and generates an output. It might also simply give a yes/no answer. (It might also be the case that you get no answer at all – when you have an infinite loop! Then the TM does the same things again and again without halting.)

Of the models out there, it is among the most powerful ones and can calculate everything that any computer program can calculate.

More precisely, the Church-Turing thesis conjectures that the effectively computable functions on natural numbers are exactly those that Turing machines can calculate.

Maybe you have heard that something is Turing-complete. This means it can simulate a Turing machine and therefore do all computations that are possible. This applies for example to programming languages (with only a handful of exceptions), but also to surprising things like Magic: The Gathering.

What parts does it have?

Alphabet of symbols: This is a finite set of symbols that are used to write on a tape. The input and output strings consist of these symbols. There is a special blank symbol _ that says that a position is empty.

Read/write tape: This is an infinitely long tape consisting of cells that can each hold a single symbol of the alphabet.
Read/write head: This points to a cell of the tape that is currently processed. It can move one cell per computation step.
State: There is a finite set of possible states. A (deterministic) TM is in exactly one state at a time. It determines how the TM will act next, according to the transition function. A subset of states is final (here the TM will halt and accept) and one state is initial (here it will start).
Transition function: The transition function defines what the TM will do in different situations. Depending on the current state and the symbol at the position of the read/write head, the TM will change to a new state, (optionally) write a new symbol at the current tape position, and then (optionally) move one position to the left or right.

Another important term is the configuration of the TM. This is roughly speaking the situation you find in the TM at a given moment, consisting of the current state, position of the head, and string on the tape.

How does it work?

I will describe deterministic TMs here, where the transition functions can change from a configuration into a single target configuration. Nondeterministic TMs, where there are possibly several target configurations, can compute the same functions as deterministic ones.

In the beginning, the input string is written on the read/write tape. The head points to the first symbol and all other cells of the tape are blank. The state is the initial state.

The following is repeated until the TM halts:

The TM looks at the symbol under the head and the current state, then looks up what the transition function says it should do. It changes its configuration accordingly.

There are two ways how it can halt:

The TM accepts (= yes-answer) when it goes into a final state. The output string is what is written on the tape at that time.
The TM rejects (= no-answer) when the transition function does not give any target configuration. It is undefined for the current configuration.

Let's look at a simple example!

Alphabet A = { a, b, c, d }
States Q = { q, p, f }
Transition function t:
t(q, a) = (q, c, ->)
t(q, b) = (p, d, ->)
t(p, d) = (p, d, ->)
t(q, _) = (f, _, -)
t(p, _) = (f, _, -)

This TM reads a string consisting of a (possibly empty) sequence of a's followed by a (possibly empty) sequence of b's from left to right. It replaces the a's by c's and the b's by d's, then accepts.

For example: aabbb is converted to ccddd.

The sequence of configurations looks as follows. Let's write the state before the tape cell it points at.

q aabbb
c q abbb
cc q bbb
ccd p bb
ccdd p b
ccddd p _
ccddd f _

I hope this has given you some idea what a Turing machine does! This is a very fundamental concept of computer science that is useful to know.

What is a Turing Machine?

Learn how this fundamental concept of computer science works!

The all-in-one writing platform.

Write, publish everywhere, see what works, and become a better writer - all in one place.