|||
人机关系最后落实到算法层次上可以说就表现在人的“判断”与机器的“判定”关系上,希尔伯特第十问题与图灵的回答一起作为“判定问题(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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 08:57
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社