论可计算数及其在判定问题上的应用

简介

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计算机器与智能