|||
图灵的“论可计算数及其在判定问题上的应用”(On Computable Numbers, With an Application to the Entscheidungsproblem)是1936年的工作,而他的博士论文“基于序数的逻辑系统”(Systems of Logic Based on Ordinals)是1938年完成的。前者可以说是计算机理论中的“圣经”,但后者却给理论和认知带来了很大的困惑,我们认为这种结果主要是由于对图灵论文的误解造成的。
图灵在这篇论文中提出了“神谕”这样一种假设,完全不是为了“证明”“超计算”这个概念,恰恰相反,图灵说:“假设我们拥有一种可以解决不可判定问题的一般方法,那么可以称这种方法为神谕。对于这个神谕,我们除了知道它肯定不是一台机器外,无法知道更多的了”(Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.)。
可能是为了突破“图灵机”的限制的缘故,大量的“超计算”等研究从各方面一直开展着,但是迄今为止,并没有真正的突破(相关的物理学和纯数学上研究的不在此例)。
“NP完全性”(NP-Completeness)是柯克(Cook)1971年开创性的工作(The Complexity of Theorem-Proving Procedures),在他以前虽有涉及此类性质的一些研究,但并不成为专门领域理论,更没有造成像“千禧年难题”(P versus NP)这样的影响;而且随着计算机、互联网、人工智能研究的高速发展,计算机的能力限度越来越成为迫切的问题,但目前为止所有概念和理论均没有给出现成的答案。
我们对NP理论研究工作基于经典的可计算机理论(包括图灵机),从目前存在的困难出发,追本溯源,寻求可计算性与不确定性的本质及其关系,由于学力有限,不可能涉及这个领域内方方面面,因此对所讨论的问题有论域的限制,但并不排斥网友们的广泛讨论。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-1 07:38
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社