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

博文

NP理论(4):判断如何成为算法

已有 3313 次阅读 2016-9-21 17:22 |个人分类:NP理论|系统分类:科研笔记| 判断, 判定, Entscheidungsproblem

人机关系最后落实到算法层次上可以说就表现在人的“判断”与机器的“判定”关系上,希尔伯特第十问题与图灵的回答一起作为“判定问题(Entscheidungsproblem)”,揭示了人的判断与机器的判定之间的不确定性关系,寻找这种不确定性关系的解决就可表达为“判断如何成为算法”。

一,丢番图问题[1]

丢番图问题:给定一个系数均为整数,包含任意个未知数的丢番图方程,设计一个过程,判定该方程是否存在整数解。

10. Determination of the solvability of a diophantine equation

Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.

二,希尔伯特第十问题与图灵的回答[2]

希尔伯特第十问题要求(人)发明或设计(to devise )一种程式(a process)去判定(determine)任意一个丢番图方程是否有解(暗含一般代数方程是否有代数解),这里实际上存在两个层次上的一致性 —— 对一般性问题能否给予一种具体性的判断,这对一个数学家的工作来说是自然的,数学证明具有这种性质,但现在这个问题更一般,就是在一般性问题与解决方法之间给予一种能行性的判定。图灵不是用“停机问题”基于悖论的证明方式,而是以(人)无法构造出这种能行性(circle-free)的“程式”(process),表达了对希尔伯特第十问题的拒绝——the Hilbert’s Entscheidungsproblem cannot have solution,就是说无法对希尔伯特第十问题回答Yes or No,图灵的“拒绝”不同于对这个问题的解答,图灵也不是回答对一般性问题有(Yes)或没有(No)能行性的判定方法,而是说,这类问题的判断是无法以问题求解的算法方式解决的,这就是著名的“不可判定问题”——作为一般问题是否存在确定性算法,是不可判定的,也就是机器无能的,图灵的意思可以理解为:the Hilbert’s Entscheidungsproblem is a problem for which any machine cannot solve。因此,图灵既不是否定一般性问题,也不是否定具体的方法,而是否定了一般性问题与能行方法之间的具有确定性的关系,“‘判定问题’不可判定”就是,对一般性(判断)问题不存在具体的能行性(判定)方法 —— 这就是我们所强调的希尔伯特第十问题和图灵的拒绝一起作为这个Entscheidungsproblem的本质。在这种理解的基础上,我们可以简要地理解,Entscheidungsproblem (“‘判定问题’不可判定”)就是“人的判断不能等同于机器的判定”。

由此看出,人的判断与机器的判定是二个层次上的问题,Entscheidungsproblem 表明这两种之间的没有确定性的关系,Entscheidungsproblem 并没有否定人的判断与机器的判定,实质上暗示了人的判断与机器的判定之间的不确定性关系,寻找这种不确定性的关系的解决就是“判断如何成为算法”。

三,判断如何成为算法

人们常说,具体的问题总是可以具体地解决的,这首先就要将一般认知性的,通常以自然语言表达的解决问题的方法具体化、形式化,这就是我们所说的“判断如何成为算法”,因此我们说,对于没有确定性算法解决的问题(NP),人可以去寻找最优近似算法(NP-算法,NP-algorithm),比如对“旅行商问题”,可以找到很多的算法(最小生成树、动态规划法、分支界限法、贪心算法……),NP-算法不是对NP的确定性算法,而是以启发式的算法对NP的最优近似表达和求解(“启发式算法”这个术语可用NP-算法表达)。

用某种算法表达出了问题求解,就是解决了”判断如何成为算法”,——数学家们认为马提亚谢维奇(Y. Matijacevic)等解决了希尔伯特第十问题,实际上是指找到了表达求解丢番图方程的一般办法(斐波纳奇数列),由此得出丢番图方程不可判定。

参考资料:

[1] Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[2] David Hilbert: Mathematical Problems, http://aleph0.clarku.edu/~djoyce/hilbert/problems.html




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

上一篇:前驻法国大使吴建民引用“郑和下西洋”反驳“中国威胁说”
下一篇:矛盾与悖论
收藏 IP: 58.19.17.*| 热度|

1 杨正瓴

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

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

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

GMT+8, 2023-2-4 03:25

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部