| |
KF5JRV > TECH 16.07.16 12:22l 71 Lines 4537 Bytes #999 (0) @ WW
BID : 6137_KF5JRV
Read: GUEST
Subj: Post-Turing Machine
Path: IZ3LSV<IV3ONZ<IW8PGT<CX2SA<XE1FH<JE7YGF<N9PMO<N0KFQ<KF5JRV
Sent: 160716/1118Z 6137@KF5JRV.#NWAR.AR.USA.NA BPQK1.4.65
Alan Turing Publishes "On Computable Numbers," Describing What Came to be
Called the "Turing Machine"
In issues dated November 30 and December 23, 1936 of the Proceedings of the
London Mathematical Society English mathematician Alan Turing published "On
Computable Numbers", a mathematical description of what he called a universal
machine — an astraction that could, in principle, solve any mathematical
problem that could be presented to it in symbolic form. Turing modeled the
universal machine processes after the functional processes of a human carrying
out mathematical computation. In the following issue of the same journal
Turing published a two page correction to his paper.
Undoubtedly the most famous theoretical paper in the history of computing,
"On Computable Numbers" is a mathematical description an imaginary computing
device designed to replicate the mathematical "states of mind" and
symbol-manipulating abilities of a human computer. Turing conceived of the
universal machine as a means of answering the last of the three questions
about mathematics posed by David Hilbert in 1928: (1) is mathematics
complete; (2) is mathematics consistent; and (3) is mathematics decidable.
Hilbert's final question, known as the Entscheidungsproblem, concerns whether
there exists a defiinite method—or, in the suggestive words of Turing's
teacher Max Newman, a "mechanical process"—that can be applied to any
mathematical assertion, and which is guaranteed to produce a correct decision
as to whether that assertion is true. The Czech logician Kurt Gödel had
already shown that arithmetic (and by extension mathematics) was both
inconsistent and incomplete. Turing showed, by means of his universal machine,
that mathematics was also undecidable.
To demonstrate this, Turing came up with the concept of "computable numbers,"
which are numbers defined by some definite rule, and thus calculable on the
universal machine. These computable numbers, "would include every number that
could be arrived at through arithmetical operations, finding roots of
equations, and using mathematical functions like sines and logarithms—every
number that could possibly arise in computational mathematics" (Hodges, Alan
Turing: The Enigma [1983] 100). Turing then showed that these computable
numbers could give rise to uncomputable ones—ones that could not be calculated
using a definite rule—and that therefore there could be no "mechanical
process" for solving all mathematical questions, since an uncomputable number
was an example of an unsolvable problem.
From 1936 to 1938 Mathematician Alan Turing spent more than a year at
Princeton University studying mathematical logic with Alonzo Church, who was
pursuing research in recursion theory. In August 1936 Church gave Turing's
idea of a "universal machine" the name "Turing machine." Church coined the
term in his relatively brief review of "On Computable Numbers." With regard
to Turing's proof of the unsolvability of Hilbert's Entscheidungsproblem,
Church acknowledged that "computability by a Turing machine. . . has the
advantage of making the identification with effectiveness in the ordinary
(not explicitly defined) sense evident immediately—i.e. without the necessity
of proving elementary theorems." Church working independently of Turing, had
arrived at his own answer to the Entscheidungsproblem a few months earlier.
Independently of Alan Turing, mathematician and logician Emil Post of the City
College of New York developed, and published in October 1936, a mathematical
model of computation that was essentially equivalent to the Turing machine.
Intending this as the first of a series of models of equivalent power but
increasing complexity, he titled his paper Formulation 1. This model is
sometime's called "Post's machine" or a Post-Turing machine.
In 1937 Turing and John von Neumann had their first discussions about
computing and what would later be called “artificial intelligenceö (AI).
Always interested in practical applications of computing as well as theory,
also while at Princeton, in 1937, believing that war with Germany was
inevitable, Turing built in an experimental electromechanical cryptanalysis
machine capable of binary multiplication in a university machine shop. After
returning to England, on September 4, 1939, the day after Britain and France
declared war on Germany, Turing reported to the Government Code and Cypher
School, Bletchley Park, in the town of Bletchley, England.
Read previous mail | Read next mail
| |
