Turing Machine: What It Is and How It Works

A Turing machine is not something you can hold. It is a model drawn on paper to answer one precise question: what does it actually mean to compute? Alan Turing answered in 1936 by describing a minimal machine, made of a tape, a head, and states, and showing that these few ingredients can reproduce anything a person would call a calculation (a few years later, Turing put these same ideas to work breaking the Nazi Enigma code: the Recap on Alan Turing and the Enigma Machine tells that story).

The parts of the model

The tape is divided into squares, each able to hold one symbol. It is infinite in one direction, so the machine always finds an empty square ahead of it. A head sits on one square at a time, reads the symbol there, and, if needed, replaces it with another.

The machine is always in one of a finite number of states (Turing called them “m-configurations”). A handful of states, combined with the right rules, is enough to represent fairly complicated procedures.

Linking states and symbols is the transition function: starting from where the machine stands and what it reads, it fixes three outcomes, the symbol to leave on the tape, the direction the head takes next, and the state the machine moves into. Compared with the von Neumann architecture, which describes how real computers are organized, the Turing machine is the theoretical ancestor: a model conceived before a single microprocessor existed, still used today to understand the limits of the ones still to come.

How a single step works

Every step a Turing machine takes is three elementary actions: write a symbol, move the head one square, change state. The order matters, but the logic stays the same: the action depends only on the current state and symbol.

Practical example: to represent the number 3, a Turing machine working in unary notation writes a block of four consecutive “1” symbols on the tape (the number n takes n+1 symbols). One repeated symbol, with the right rules for counting it, is already enough to do arithmetic.

The same principle, minimal rules applied step by step, shows up in a different example: a machine that increments a number written in binary code scans the digits from right to left, changes “1”s to “0” until it finds a “0”, and flips that one to “1”. It is the same carry used when adding by hand in columns, translated into a language with only two digits.

Anyone looking for a broader definition of what a sequence of rules like this actually is can read the Recap on the algorithm: a Turing machine is one of its strictest formalizations, specified down to the smallest detail.

The halting problem

A procedure of this kind can come to a stop, or it can run forever without ever halting. The halting problem asks whether a general method exists, a machine that works for every other machine and every input, able to say in advance which of the two will happen.

The answer is no. The proof works by contradiction: assume a machine exists that can decide whether every other machine halts, then build a specific case that turns that same machine against itself, reaching a logical contradiction. The technique is called a diagonal construction, and it is due to Turing.

It is a proven impossibility, holding for any machine, slow or extremely fast: more time or more computing power do not change the result.

The Church-Turing thesis

In the mid-1930s, Alonzo Church and Alan Turing arrived, independently, at the same idea: anything computable by an effective method, an algorithm in the everyday sense of the word, can be computed by a Turing machine.

It is a thesis: no formal mathematical proof exists, but the fact that computation models developed independently in those same years, Turing machines, Church’s recursive functions, other formalisms, converge on one single class of computable functions has made the thesis more credible over time. Kurt Gödel, for his part, judged the Turing machine the first precise and, in his view, correct account of what a mechanical procedure intuitively means; it is one logician’s opinion, carrying real authority but no formal proof behind it.

The practical consequence touches every computer that exists or ever will: the limits of the theoretical model hold for real machines too, whatever technology builds them. The Church-Turing thesis carries the halting problem into every real machine, a boundary that has nothing to do with any particular programming language, as the Recap on the history of computers also shows. A second consequence concerns numbers instead of programs: the real numbers form a larger infinity than the possible Turing-machine programs, which, by contrast, can be counted one by one, listed in an imaginary catalog. It follows that real numbers necessarily exist that no Turing machine will ever be able to compute: there are simply more of them than there are programs available to compute them, however much time the machine is given to work.

A machine that simulates others

The name “universal Turing machine” describes the idea of a single machine able to simulate any other Turing machine. It is a direct extension of the model described so far, but the exact mechanism falls outside what is covered here: it is only named, because the name comes up often alongside the rest of computability theory.