不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

关于NP讨论中的论域问题(2)

已有 3323 次阅读 2015-10-16 23:21 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 图灵, 神谕, NP完全性

图灵的“论可计算数及其在判定问题上的应用”(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理论研究工作基于经典的可计算机理论(包括图灵机),从目前存在的困难出发,追本溯源,寻求可计算性与不确定性的本质及其关系,由于学力有限,不可能涉及这个领域内方方面面,因此对所讨论的问题有论域的限制,但并不排斥网友们的广泛讨论。




https://wap.sciencenet.cn/blog-2322490-928685.html

上一篇:解读“我在说谎”悖论(3)
下一篇:索罗斯的“NP”观
收藏 IP: 82.246.87.*| 热度|

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-1 07:38

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部