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

博文

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

已有 2803 次阅读 2015-5-14 18:03 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 图灵机, 可计算性理论, 冯·诺意曼结构

1. 逻辑运算(真值表关系)与图灵机计算(可计算函数)具有不同的性质,但这两种不同的性质总是被混淆,它们的内涵更是被混乱。

2. 图灵机是普遍意义上的计算机模型,图灵机以抽象的物理结构表现了作为算法的“机械步骤”的结构和过程。图灵以图灵机的形式严格地表达了“不可判定问题”,这是图灵当时工作的主要目的,但此目的被忽视或被误导了,这是造成现有的NP问题理论严重困难的最根本性的原因。

3. 图灵机(算法)可以由具体的计算机实现,但图灵机不等于任何一台具体的计算机,这是“一般”和“特殊”的关系,丘奇论题(Church’s thesis)引伸的意义是,图灵机与具体的计算机在算法性质上一致但层次不同。

4. 图灵机的抽象物理结构表现了算法如何由机械步骤实现,冯·诺意曼结构是图灵机的抽象算法结构的物理化,现代计算机的物理过程是由电子逻辑实现的。

5. P与NP具有完全不同的性质,目前反映在博客上的我们的部份工作就是精确地分析出现有的P与NP概念中所发生的概念混淆和它们内涵上的混乱。我们通过图灵机可以理解,对于可计算函数(P)而言,计算和判断具有相同性质,现有的NDTM概念实质是DTM,所以是“可计算”的,也是“可判定”的。

计算模型表达了算法基本原理,任何“机器”如果没有内在的算法结构和过程就不能成为计算机,所以任何(经典物理意义上的)“机器”要具有算法性质必须具有图灵机或冯·诺意曼结构。人们可以按算法的基本原理设计具体的计算机,但不能设计基本算法结构上不同于图灵机或冯·诺意曼结构的计算机模型(或许经典物理本质上的革命性突破除外)。

计算机理论中的图灵机和数学理论中的可计算性理论是严格一致的科学理论,这是我们工作的基础,我们对现有NP问题的概念的质疑就是从这些严格的理论和概念出发的,欢迎广大网友参与我们的工作,由于时间和精力限制,对离开上述基本概念太远的问题,暂时不作详细的个案分析讨论,以保证目前讨论的焦点性。本篇文章中上述的5点内容是我们的NP理论研究中的最基本的观点的摘出,所涉及的深层次问题将在另外的论域中展开。  




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

上一篇:NP二个流行定义与“白马非马”
下一篇:点评《紐約客》文-流行的NP定义(1)

3 姜咏江 杨正瓴 icgwang

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

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

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

GMT+8, 2022-1-20 13:57

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部