奇点O论坛（2020/6/6）后（图灵机的“非计算”思考 - 图灵机与人工智能的关系（奇点O论坛，2020/6/6）），我和王培老师关于图灵机与人工智能的关系展开了对话。

柳渝：怎么看“判定问题”与“⼈工智能”的关系？

王培：智能系统每时每刻都在做“判断”，但这和计算意义下的“判定”有根本不同（当然仍有很多相似性）。我有一篇旧文（https://cis.temple.edu/~pwang/Writing/computation.pdf）讨论过此事。简单说来，后者是根据一个计算问题将“答案”和“非答案”分成截然不同的两类，而且和解题系统的历史、状态无关；前者是在历史和现实的约束下找最好的，所以没有停机问题。

柳渝：从形式上看，计算意义下的“判定”与智能系统的“判断”确实不同，我是想问：二者是否还存在内在的联系？

“判定问题”（Entscheidungsproblem）由希尔伯特1900年提出，是问：是否存在解决任何数学问题的通用过程（或者说，系统方法，图灵机，算法）？后来学术界用“停机问题”取代了“判定问题”，这是一个复杂的学术问题，我们稍后再说。

图灵在1936年的论文中对“判定问题”予以了否定的回答：判定问题不可判定，即证明了“不存在通用过程可以判定给定的函数演算K的公式”，这里的“函数演算K”指一阶谓词。此证明基于图灵提出的“图灵机”，用以表达希尔伯特所说的“通用过程”。

所以在图灵机的意义下，“计算”与“判定”是一致的。换句话说，“判定问题”实际上是指图灵机意义下“判定成为问题”。所以，这里的“问题”与普通意义下的“问题”相比，上升了一个“层级”。

既然图灵机的“计算”无法解决一些问题，那么就采取图灵机的“非计算”，于是图灵提出“机器智能”，开启了基于“学习”机制的“人工智能”先河，。。。

这此意义上，我认为，“判定问题”与“⼈工智能”存在着内在的联系。或许可以说，如果说图灵机是解决“计算问题”，那么智能系统就是试图解决“判定问题”，。。。

王培：从形式上看，计算意义下的“判定”与智能系统的“判断”确实不同，我是想问：二者是否存在内在的联系？

存在。但具体联系方式需要仔细讨论。

“判定问题”（Entscheidungsproblem）由希尔伯特1900年提出，问：是否存在解决任何数学问题的通用过程（或者说，系统方法，图灵机，算法）？后来学术界用“停机问题”取代了“判定问题”，这是一个复杂的学术问题，我们稍后再说。

图灵在1936年的论文中对“判定问题”予以了否定的回答：判定问题不可判定，即证明了“不存在通用过程可以判定给定的函数演算K的公式”，这里的“函数演算K”指一阶谓词。此证明基于图灵提出的“图灵机”，用以表达希尔伯特所说的“通用过程”。

既然图灵机的“计算”无法解决一些问题，那么就采取图灵机的“非计算”，于是图灵提出“机器智能”，开启了基于“学习”机制的“人工智能”先河，。。。

由于“图灵机” 就是“计算” 的定义，所以不能说“图灵机的非计算”，而应该说“计算机的非计算”，或者“计算之外的解决问题方式”。在我看来，计算、图灵机、算法、函数、映射等等大致是同一个概念（概念A，可重复解题方式），而计算机、过程、信息加工、解决问题等等是一个更大的概念（概念B，解题方式），其中也给学习和智能留有空间（概念C ，可变解题方式）。这就是说A和C没有交集，而二者都是B的子集。现在的普遍看法是A和B是同一个概念，而C是它们的子集。我这篇文章（https://mp.weixin.qq.com/s/JQbYrKjqtmpBIoFQkHtThQ）就是要指出这个问题。

这此意义上，我认为，“判定问题”与“⼈工智能”存在着内在的联系。或许可以说，如果说图灵机是解决“计算问题”，那么智能系统就是试图解决“判定问题”，。。。

如果把输出当作对输入的“判断”，那么的确可以这么说。但即使如此，这个意义下的“判定”也和传统意义有若干根本不同，其中之一就是对解题过程的“终态” 没有严格定义。在日常生活中，但我们某问题找到一个解之后，是见好就收还是精益求精，往往不仅取决于此问题和此答案，更取决于此时我们是否还有其它问题需要处理。严格说来，我们接受或报告的解一般都不是逻辑意义下的最终解。以这封邮件为例，如果我再花上一个星期来写，一定会质量更高，但由于我还有一堆事要做，只好在此停笔了，但发出去后我一定还会在闲下来时想到这个话题。这算是“判定”或“停机”了吗？

柳渝：学术界用“停机问题”取代了“判定问题”（Entscheidungsproblem），并认为图灵在1936年的论文中证明的是“停机问题”。事实上，图灵并没有提出“停机”这个术语，此术语可能来源于戴维斯（Marin Davis）。

图灵在论文中提出“判定问题”的基础问题：

- 是否存在一个图灵机能判定任何图灵机具有“可计算性”？

再看“停机问题”：

- 是否存在一个图灵机能判定任何图灵机“停机”？

也就是说，“停机问题”的本质是用“停机”替代计算出预期结果的“可计算性”。 

那么，“停机”能替代“可计算性”吗？“停机问题”能取代“判定问题”吗？

如你问：以这封邮件为例，如果我再花上一个星期来写，一定会质量更高，但由于我还有一堆事要做，只好在此停笔了，但发出去后我一定还会在闲下来时想到这个话题。这算是“判定”或“停机”了吗？

在论文中，图灵将图灵机分为二类：circle-free machine，circular machine。circle-free machine指能在有限步骤打印出来结果的图灵机，由此定义“可计算性”；而circular machine指不能在有限步骤打印出来结果的图灵机。图灵举的二个circle-free machine例子，都是“不停机”的：一个打印序列010101…，一个打印序列01011011101111…。

我认为，关于“停机问题”，不仅是一个复杂的学术问题，更对认知和实践有严重的影响。

或许进一步，可以问：是否因为“停机问题”的绑架，让人们对计算机与人工智能的关系的理解产生了极大的困难？

王培：让我们过一遍相关概念：

（1）一个“问题” 定义了一个从输入集合到输出集合的“映射” 或者说« 函数"。

（2）一个“算法” 或者说“计算” 是个将该问题的每个输入转化成相应输出的一个可重复、可执行、保证终止的过程，

（3）一个“判定问题” 是一个只有“是/否” 两个输出值的问题。原则上每个问题都可以转换成一个等价的判定问题。

（4）一个问题是“可计算”的，当且仅当有一台图灵机可以解决相应的判定问题。

（5）如果一台图灵机对每个合法输入都停机，则可根据停机时是否在终态决定输出，因此该问题就可判定。

因此，“可计算”，“可判定”，“可停机” 的确都是不同的概念，但它们是等价的，即对其中一个的“是/否” 答案也就是对相应的其它问题的答案。

对人工智能而言，在（1）和（2）那里就和计算理论分道扬镳了：问题的解和情境、历史相关，因此不是可重复的，“解” 和“非解” 也没有明确界限。在这种情况下，（3)-(5）都不再是有意义的问题。因此，囿于传统的计算理论的确制约了人工智能的发展。停机问题、判定问题、可计算问题都和人工智能没有直接关系。智能系统当然需要做“判断”，但这已经和传统的“ 判定” 没多大关系了。原因之一就是“判断” 不是二值的“是/否”，而必须有个程度在其中，同时还要受可用的处理时间的约束。计算复杂性理论同样和人工智能没有直接关系。如果对某类问题的处理不遵循任一算法，而是具体情况具体分析的，那就没有确定的计算复杂性可说。这就是为什么P是否等于NP和人工智能无关的原因。不要说多项式算法，即便是常数的时间开销都不一定是足够快的。

柳渝：你把几个相关概念过一遍很好！

人工智能与计算理论在（1）和（2）那里分道扬镳，所以“判定问题”是转折点，非常重要！

从形式上看，“判定问题” 是一个只有“是/否” 两个输出值的问题；但从内容上看，却有复杂的内涵，比如“判定一个拼图（比如15-Puzzle）是否达到了预期的格局”与“判定一个拼图是否能达到预期的格局”，性质完全不同：前者是“是/否” 的“确定性问题”，而后者是不知道“是/否”的“不确定性问题”，即不存在算法确定性判定一个拼图是否有解的问题，这才是计算机理论真正的“判定问题（Entscheidungsproblem）”，关系到图灵计算能力的局限，启示需要“人”的介入，如此开启了走向人工智能的道路，。。。

如果将“判定问题” 定义为“一个只有“是/否” 两个输出值的问题”，那么真正的“判定问题（Entscheidungsproblem）”的“不确定性”就消失了，其结果就是你指出的：人工智能与计算理论在（1）和（2）那里分道扬镳；（3)-(5）都不再是有意义的问题，P是否等于NP和人工智能无关，。。。

所以，我认为，“一个“判定问题” 是一个只有“是/否” 两个输出值的问题”，这个定义需要追究，因为这不仅影响对人工智能的本质及人机关系的理解，而且直接影响对P vs NP问题与人工智能关系的理解。

我们一直专注于P vs NP，认为这是解决P vs NP问题的关键，。。。

王培：人工智能与计算理论在（1）和（2）那里分道扬镳，所以“判定问题”是转折点，非常重要！

从形式上看，“判定问题” 是一个只有“是/否” 两个输出值的问题；但从内容上看，却有复杂的内涵，比如“判定一个拼图（比如15-Puzzle）是否达到了预期的格局”与“判定一个拼图是否能达到预期的格局”，性质完全不同：前者是“是/否” 的“确定性问题”，而后者是不知道“是/否”的“不确定性问题”，即不存在算法确定性判定一个拼图是否有解的问题，这才是计算机理论真正的“判定问题（Entscheidungsproblem）”，关系到图灵计算能力的局限。

我觉得这里的差别主要是问题实例（instance，element）和问题类型（type，set）的差别。判定问题关注的是后者，即是否有一个统一的办法可以处理一个问题类中的所有实例。这里的否定性结论说的也是“没有统一的方法可以解决所有这类问题”，而不是说其中每个实例都不可解，或者说“解”的标准不确定。

启示需要“人”的介入，如此开启了走向人工智能的道路，。。。

这就是见仁见智了。我不认为智能（不管是人的还是机器）比图灵机的“计算” 能力更强，而是可以跳出计算的圈子。

如果将“判定问题” 定义为“一个只有“是/否” 两个输出值的问题”，那么真正的“判定问题（Entscheidungsproblem）”的“不确定性”就消失了。

并没有。对每个实例而言，的确只有两个输出。不确定性是相对于整个问题类而言的。不严格地说，这就好比是我们对A、B、C三个问题分别有办法，但没有一个统一的办法对它们同时有效。

其结果就是你指出的：人工智能与计算理论在（1）和（2）那里分道扬镳；（3)-(5）都不再是有意义的问题，P是否等于NP和人工智能无关，。。。

所以，我认为，“一个“判定问题” 是一个只有“是/否” 两个输出值的问题”，这个定义需要追究，因为这不仅影响对人工智能的本质及人机关系的理解，而且直接影响对P vs NP问题与人工智能关系的理解。

我们一直专注于P vs NP，认为这是解决P vs NP问题的关键，。。。

我们在这里的看法仍有不同。我在人工智能语境中反对二值判断，但我并不认为传统的计算理论（包括对判定问题的处理）有错。在那个问题设定下，判定结果的确应该是二值的，尽管没有统一的方法可以保证得到这种结果。我对计算理论的不满在于它没有对它的适用范围进行足够清晰的界定，以至于使大多数人以为它是使用计算机的唯一正确方式。这就像是我反对一个川菜厨师，不是因为他川菜做得不好，而是因为他有意无意地给人“所有的菜都要用川菜的标准衡量” 的印象。当然别人仍然可以说他的川菜做得有问题，但那不是我的关注点。

柳渝：我们的观点有同有异，你说 “我对计算理论的不满在于它没有对它的适用范围进行足够清晰的界定，以至于使大多数人以为它是使用计算机的唯一正确方式”，这我同意，但我认为，这与对“判定问题”的解读相关，所以我建议借助二个熟悉的例子的说明，再在这个概念上停留一下。

A：普通路径问题：判定一个有向图是否包含连接两个指定结点s和t的路径。

B：哈密尔顿路径问题：判定一个有向图是否包含连接两个指定结点的哈密尔顿路径。

对于问题A，存在多项式时间算法（图周游）寻找从s到t的普通路径，也就判定了从s到t普通路径的存在性。在此意义下，计算与判定一致，所以没有必要提出“判定问题”。

对于问题B，不存在多项式时间算法寻找从s到t的哈密尔顿路径，常见的算法多是元启发式算法，机器学习算法。在这种情况下，虽然从s到t的哈密尔顿路径的存在性是确定的（yes/no），但是对此存在性的判定却是不确定的，也就是说，当一个算法给出yes的回答时，可以得出存在从s到t的哈密尔顿路径的结论；但是当算法回答no时，并不能得出不存在从s到t的哈密尔顿路径的结论。

在此意义下，计算与判定不一致，判定成为“问题”。所以，我说“这才是计算机理论真正的’判定问题（Entscheidungsproblem’，反映出图灵计算对这类问题能力的局限。”

可见，若将“判定问题” 定义为“一个只有“是/否” 两个输出值的问题，就模糊了问题A和问题B的界限，导致你上述批评，但这不应该是计算理论的错，而是人们对图灵关于Entscheidungsproblem的工作存在误读，。。。

王培：看来问题确实是在对Entscheidungsproblem 的理解了。我的理解基本类似于https://en.wikipedia.org/wiki/Entscheidungsproblem所说的。按这个理解，你的A和B问题同为可判定问题，其区别仅仅是一个有已知的多项式算法，而另一个只知道指数算法。但可判定性（以及可计算性）只涉及算法的存在与否，而与算法复杂性无关。

柳渝：是的，问题确实是在对Entscheidungsproblem（判定问题）的理解上。

我讨论之初问：怎么看“判定问题”与“⼈工智能”的关系？目的是想初步探讨“判定问题”在从图灵机到⼈工智能过渡中所起的作用。

我图示这一观点：

至于Entscheidungsproblem与“停机问题”关系议题，还需要进一步深入，可能会触及到计算机理论中多年的隐患，直接影响对计算复杂性理论与人工智能的关系，P是否等于NP与人工智能的关系的理解。如果你感兴趣，我们可以陆续讨论。

参考文献：

【1】王培，计算机不是只会 “计算”，图灵机也不是一台“机器”：https://www.thepaper.cn/newsDetail_forward_7683950

【2】A.M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

【3】A.M. Turing, Computing machinery and intelligence, Mind,59, 433- 460，1950. https://www.csee.umbc.edu/courses/471/papers/turing.pdf