Charles Petzold

Today is the 95^th birthday of English mathematician Alan Turing (1912-1954), whose 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" demonstrated that there can be no general finite process to determine the provability of arbitrary statements in first-order predicate logic.

In doing so, Turing originated the field of computation theory and invented a handy tool that soon came to be known as the Turing Machine. The Turing Machine essentially formalizes the concept of the algorithm; today we think of algorithms as finite processes that can be carried out by Turing Machines. Some would even say that Turing invented the concept of the general-purpose digital computer.

In this original paper, Turing's machines compute numbers, and the very first Turing Machine computes the binary equivalent of 1/3 (although Turing doesn't explicitly say this), which is 0.01010101... Here's the machine, a bit simplified and with the syntax clarified:

The machine works with a "tape" of some sort divided into cells. The machine is always in a particular "configuration" or "state." This particular machine has two states, called First and Second. The machine examines what symbol is in the current cell (in this case there will be no symbol) and performs operations depending on the state and symbol. In this case, the operations are to print a number and then move one cell to the right. (Printing and moving are the only types of operations allowed). The machine then goes into another configuration, symbolized by the "goto" in the final column. The result: A series of alternating 0's and 1's. It's an infinite process represented by a finite machine.

From this humble beginning, Turing next shows a machine that prints an irrational number that is probably also transcendental. Turing demonstrates that his machines can compute rational numbers (trivially), algebraic numbers (the reader becomes convinced), and some transcendental numbers (π is conceivable). However, most real numbers are not calculable by Turing Machines, and that's a limitation of mathematical algorithms that becomes apparent early in Turing's paper.

The term "halting problem" is often used in connection with Turing Machines, but that term does not appear in Turing's original paper. The term was probably invented by mathematician Martin Davis in lectures he gave in 1952, and then appeared in his 1958 book Computability and Unsolvability.

The word Entscheidungsproblem (decision problem) is associated with David Hilbert and was popularized in his 120-page book (coauthored by William Ackermann) Grundzüge der Theoretischen Logik (Berlin, 1928). However, Berkeley philosophy professor Paolo Mancosu discovered an earlier use of the word in an unpublished 1921 lecture given by Hilbert's assistant Heinrich Behmann (1891-1970) to the Göttingen Mathematical Society entitled "Entscheidungsproblem and the Algebra of Logic." Mancosu discussed Behmann's role in his paper "Between Russell and Hilbert: Behmann on the Foundations of Mathematics" (Bulletin of Symbolic Logic, Vol. 5, No. 3, Sept. 1999, 321). Here's Behmann on the type of process they were seeking for determining the solvability of statements in first-order logic. Italics are in the original German:

It is of fundamental importance for the character of this problem that only mechanical calculations according to given instructions, without any thought activity in the stricter sense, are admitted as tools for the proof. One could, if one wanted to, speak of mechanical or machinelike thought. (Perhaps one could later let the procedure be carried out by a machine.)

Turing was sure thinking along these same lines 15 years later when he developed his imaginary machine for carrying out mathematical algorithms.