释义 |
《论可计算数及其在判定问题上的应用》 On Computable Numbers, with an Application to the Entscheidungs Problem 英国图灵著。1937年发表。分11节。着重分析了计算一个数的过程,得出了理论的通常计算机(图灵机)的概念,认为这种机器能够在任一“可计算序列”(即任一0,1序列)上进行计算。并叙述了可计算数在判定问题上的应用。论文证明了希尔伯特提出的一阶逻辑的判定问题,对这种工具而言是不可解的。但文中给出的一些证明的技术细节有错误,以后作者和波斯特对此作了修订和补充。 |