Turing, Alan

1912–1954

Computer Scientist, Mathematician

Alan M. Turing's work on the hypothetical Turing machine, a programmable mechanical device for solving mathematical problems, laid the groundwork for computer science, and his Turing Test endures as a fundamental concept in artificial intelligence (AI). During World War II, Turing contributed to breaking Germany's Enigma code, aiding the Allies in defeating the Nazis.

Alan Turing was born in London on June 23, 1912. He attended public school, where he developed interests in mathematics, physics, and chemistry. Despite his keen curiosity and affinity for mathematics, Turing struggled with the classically focused curriculum.

He won a scholarship to Cambridge in 1931, and in 1935, during a lecture by the mathematician M. H. A. Newman, he was introduced to the Entscheidungsproblem (decision-making problem) of David Hilbert. The problem asked three questions: First, is mathematics complete, in the sense that every statement is either provable or disprovable? Second, is mathematics consistent, such that an untrue statement could not be arrived at through valid methods? Third, is mathematics decidable, such that there is a method that could be applied to any problem that will either prove or disprove it? Hilbert believed the answer to all three questions to be yes.

Kurt Gödel's Incompleteness Theorem had answered the first two questions, proving that formal arithmetic was necessarily incomplete, because there are assertions that are neither provable nor disprovable. Gödel also showed that arithmetic could not be [Page 444]proved consistent within its own terms. This left the third question, posed to Turing by Newman, of whether there could be a mechanical process that, when applied to any mathematical statement, could determine whether it was provable or not.

Turing took up this question, focusing specifically on the mechanical nature of computation. In 1936, he published “On Computable Numbers, with an Application to the Entscheidungsproblem.” Recalling Babbage's Analytical Engine, Turing devised a hypothetical computer, which he called a Turing machine, that would perform a set of instructions without human aid. The machine consisted of an infinitely long tape and a scanning head that could read the contents of a frame and imprint symbols on the tape, like a typewriter. The head would follow a basic set of instructions based on what it read on each frame; these instructions included rewriting the contents of a frame and/or moving a certain number of frames in one direction or another. The head could also read the tape in different states, depending on its instructions, but given a complete set of instructions determining different states and the corresponding actions to be taken, the machine would work automatically. The specifics of the instruction sets and how the machine functioned are not so important as the implications of its functionality. Turing proved that a set of instructions could, theoretically, solve any solvable problem. Further, Turing theorized what he called a Universal Turing Machine, which encompassed all possible specific Turing machines. Its instruction sets were infinite, but its design and function were simple and proved adequate, hypothetically, to any logical problem that might be posed to it.

In essence, Turing created what would become the computer—a machine that, without human aid, can follow simple procedures to perform functions and solve problems. Using this theoretical machine, Turing answered the third part of the Entscheidungsproblem, proving that some problems were, in fact, undecidable; if a problem given to the machine results in an infinite computation, it cannot be proven that the machine will ever halt, therefore showing that the problem is not solvable.

...