Effective computability

One of the starting points of recursion theory was the decision problem for first-order logic—i.e., the problem of finding an algorithm or repetitive procedure that would mechanically (i.e., effectively) decide whether a given formula of first-order logic is logically true. A positive solution to the problem would consist of a procedure that would enable one to list both all (and only) the formulas that are logically true and also all (and only) the formulas that are not logically true. (Gödel’s first incompleteness theorem implies that there is no mechanical procedure for listing all and only the true sentences of elementary arithmetic.)

Functions that are effectively computable are called “general recursive” functions. One might think that a numerical is effectively computable if and only if it is recursive in the traditional sense—that is, its value for a given number can be calculated by means of familiar arithmetical operations from its values for smaller numbers. This turns out to be too narrow, and functions definable in this way are now called “primitive recursive.”

Different characterizations of effective computability were given largely independently by several logicians, including Alonzo Church in 1933, Kurt Gödel in 1934 (though he credited the idea to Jacques Herbrand), Stephen Cole Kleene and Alan Turing in 1936, Emil Post in 1944 (though his work was completed long before its publication), and A.A. Markov in 1951. These apparently quite different definitions turned out to be equivalent, a fact that supported the claim put forward by Church (later called Church’s thesis) that all of them capture the pretheoretical notion of an effectively computable function.

The Turing machine

Gödel initially objected to Church’s thesis because it was not based on a thorough analysis of the notions of computation and computability. Such an analysis was presented by Turing, who formulated a definition of effective computability in terms of abstract automata that are now called Turing machines.

A Turing machine is an automaton with a two-way infinite tape that is divided into cells that the machine reads one at a time. The machine has a finite number of internal states (0, 1, 2, …, n-1), and each cell has two possible states, 1 (one) and 0 (blank). The machine can do five things: move the tape by one cell to the left; move the tape by one cell to the right; change the state of a cell from 1 to 0; change the state of a cell from 0 to 1; and change to a new internal state. What the machine does at any given step is uniquely determined by its internal state and the state (1 or 0) of the cell it is reading. A Turing machine therefore represents a function that maps a cell state (1 or 0) and an internal state (0, 1, 2, …, or n-1) to a new cell state and internal state and to a specification of which cell the machine reads next.

Such a Turing machine defines a partial function φ from natural numbers to natural numbers. In order to calculate φ(x), the machine is given an otherwise blank tape with x consecutive 1s, starting with the cell that the machine is reading, and set to motion. If it stops after a finite number of steps with y consecutive 1s (and nothing else) on its tape, y = φ(x). If the machine does not stop after a finite number of steps for a given value of x, then φ(x) is undefined for x. The Turing machine in question is said to compute a function φ if φ(x) is defined for all values of x. A function is computable if there is a Turing machine that computes it. This definition of computability was shown to be equivalent to the definitions of Church, Kleene, and Post.

The definition of Turing-machine computability can be varied and made more flexible in different ways. A different notion of computability, called computability in the limit, is obtained by letting the Turing machine go on forever in computing φ(x) but requiring that a unique number stays put on the tape starting at some finite number of steps. Turing-machine computability can be defined also for functions of more than one variable.

Church’s thesis is not a mathematical or logical theorem that can be definitively proved, for the pretheoretical idea of a computable or (effectively) mechanical function that it relies on is not sharp. It has no place in a fully formal development of recursive-function theory. Nevertheless Church’s thesis is relied on in actual mathematical argumentation. When a logician has to show that a certain function f is Turing-machine computable, it may be an overwhelming task to define such a machine and to show that it in fact computes f. It is often much easier to show that f can be computed in an intuitively obvious sense. Then the logician can appeal to Church’s thesis and conclude that there exists a Turing machine that can actually compute the function. Naturally, a logician using such arguments must be in a position to produce the machine if challenged.

Turing’s definition of the notion of effective computability was a major intellectual achievement. His ideas were adapted and developed further by John von Neumann and others and thereby came to play a major part in the development of the theory and applications of computers and computing. Strictly speaking, however, the notion of effective computability is rather far removed from real-time computability. One reason for this is that the potential infinity of the tape of a Turing machine allows its computations to continue much longer than would be practical in a real computer.