The Turing machine is the central theoretical construct in computer science. The Turing machine is an abstract mathematical model of computation. The use of Turing machines helps to explain what computation is by demarcating the so-called “computable functions.”
Alan Turing’s early research into logic focused on a famous unsolved problem known as the Entscheidungsproblem. The Entscheidungsproblem (roughly translated from German as the decision problem) was proposed by philosopher and mathematician David Hilbert in 1928. The problem asked whether there was an algorithm that would decide every statement in a formal language.
A formal language is a system of axioms and inference rules such as those in arithmetic or first-order logic. The axioms can be any symbols, and the inference rules can be any list of rules for manipulating those symbols. “Deciding every statement” meant either outputting whether the statement was true/false or outputting whether the statement was derivable/underivable. Kurt Godel’s completeness theorem proved that an algorithm deciding for validity is equivalent to an effective procedure deciding for derivability. Alan Turing’s 1936 paper “On Computable Numbers, with an Application to the Entscheidungsproblem”, proved a negative result, that it was impossible to algorithmically decide every statement in a formal system.
Alan Turing
To prove a negative result for the Entscheidungsproblem, Turing needed to formalize the notion of an algorithm. Turing’s formalization of an algorithm was a mathematical model of computing that later became known as the Turing machine. A Turing machine has a finite set of states that the machine can be in. The Turing machine has an infinitely long tape that is divided into squares. On every square in the tape, there is a symbol drawn from a finite set of symbols. At any moment in the computation, the Turing machine is reading the symbol on one square of the tape. The Turing machine can replace that symbol with another symbol and move to either the square to the right or the square to the left. The action the Turing machine takes is automatically determined by the state the machine is in. After the replacement symbol and move to a different square action has taken place, the Turing machine can transition to a different state. Each different state has a different set of rules about how to replace symbols and which direction to move.
A Rare Physical Implementation of the Turing Machine Design (without an infinite tape)
The canonical formulation of the Turing machine usually consists of a binary alphabet of exclusively 0s and 1s. This formulation matches the intuition of modern computer programmers, given that all modern computers use binary. In fact, Turing machines are neutral with respect to the size of the alphabet of symbols. A Turing machine can also use any symbol, whether numeral or drawn from any other type of alphabets such as pictorial symbols or the Latin alphabet. Any formulation of every possible finite alphabet is provably reducible to a binary Turing machine.
Turing machines assume that an infinite amount of memory is available. No real physically instantiated machines can meet this requirement of being a Turing machine. A Turing machine also assumes a potentially infinite amount of time can be spent computing the function. These assumptions were made to generate the most expansive class of possible functions for Turing’s definition of computable functions. Turing’s computable functions are any functions that can be computed by a Turing machine. Many of these computable functions might never be computable by any physically instantiated machine because they require too much time or memory.
The Church-Turing Thesis asserts the equivalence of computable functions and functions that can be computed by a Turing machine. This entails that all functions not computable by Turing machines cannot be computed by any other method. David Hilbert had expected a positive answer to the Entscheidungsproblem, which would mean that all problems are computable. Turing’s result has led to the discovery of many uncomputable problems.
The most famous uncomputable problem is the Halting Problem. The Halting Problem is the problem of creating an algorithm that can, in the general case, decide whether a computer program with its input will halt or go on forever. While there are specific cases where the Halting problem can be solved, it cannot be solved for every computer program with any input. This result has had important consequences for computer programming, as computer programmers need to be aware of the possibility of infinite loops and the impossibility of detecting all infinite loops ahead of running their programs.
Another implication of the Turing machine is the possibility of universal Turing machines. Implicit in Turing’s design is the concept of storing the program that modifies the data alongside the data it modifies. This suggested the possibility of general-purpose and reprogrammable computers. Modern computers are typically universal Turing machines in the sense that they can be programmed to run any algorithm. This eliminated the need for different hardware for each potential computer program and introduced the hardware/software distinction.
The Turing machine model directly led to the invention of computers, but it is not the same blueprint used to engineer modern computers. The von Neumann architecture used as a blueprint for modern computers uses the stored program concept implicit in the Turing machine model but is different from the rest of the Turing machine model in several important ways. The biggest differences are that the von Neumann architecture doesn’t use a read-write head and instead includes multiple registers, random access memory, data buses, a small set of basic machine instructions, and multiple bit processing capabilities. The von Neumann architecture also explicitly allows for specialized input and output devices such as keyboards and monitors.
The Turing machine model was the first mathematical model of computation. It led directly to the invention of physical computers. Physical computers have all the same capabilities that Turing machines have, assuming a limited memory and time constraints on actual computation. The Turing formulation still plays a central role in the study of computation. Computer scientists are still actively involved in researching whether specific functions are computable by Turing machines.
