गणनीय संख्याओं पर, निर्णय-समस्या (Entscheidungsproblem) के एक अनुप्रयोग के साथ

परिचय

Turing, a young fellow of King’s College, Cambridge, came to the problem through Max Newman’s lectures on the foundations of mathematics in 1935: Hilbert had asked whether there is a mechanical method for deciding of any formula of logic whether it is provable. The London Mathematical Society received the paper in May 1936, and it appeared in its Proceedings in 1936–37. Turing analyses what a person does when calculating by rule and reduces it to a machine with finitely many states that reads, writes and moves along an unbounded tape; “computable numbers” are the real numbers whose decimals such a machine can write out. He shows that a single universal machine can imitate any other if given its description, and that no machine can decide of every machine whether it will ever print a given symbol – from which the negative answer to Hilbert’s question follows. Alonzo Church had published the same answer shortly before, using his lambda calculus; in an appendix Turing proved the two notions of computability equivalent, and in the autumn of 1936 he went to Princeton, where he took his doctorate under Church in 1938.

संबंध

जिस पर आधारित

• प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णेय प्रस्तावों पर I1931 · कुर्ट गेडेल

जिसमें आगे बढ़ाया गया

• संगणक यंत्र और बुद्धि1950 · एलेन ट्यूरिंग

एलेन ट्यूरिंग की और कृतियाँ

• 1950संगणक यंत्र और बुद्धि