A Turing machine is an abstract model of computation built from an extremely small set of components: an unbounded tape divided into cells, a read-write head and a finite set of internal states.

At each step, the machine reads the current tape symbol and, according to its transition rule, writes a symbol, moves the head left or right and changes state.

Simple rules, general computation

The model is deliberately primitive. Its importance is that any ordinary algorithmic computation can be represented by a suitable Turing machine.

A universal Turing machine can receive an encoding of another Turing machine together with its input and simulate that machine. This captures the idea of a general-purpose programmable computer at an abstract level.

Decidable problems

A decision problem is decidable when there is an algorithm that always terminates and gives the correct yes-or-no answer for every valid input.

Some precisely stated problems are not decidable at all.

The halting problem

Suppose an algorithm could always determine whether any given program eventually stops on a given input. By constructing a program that behaves contrary to its own predicted result, a contradiction can be produced.

Therefore no algorithm can solve the halting problem for every possible program and input.

Computability theory shows that the limits of computation are not only practical limits of memory or speed: some problems have no general algorithmic solution even with unlimited resources.