Science.net |图灵机与人工智能之间关系的对话|奇点O论坛（2020/6/6）|

“决定问题”（Entscheidungsproblem）由希尔伯特（Hilbert）在1900年提出. 问: 是否存在解决任何数学问题的通用过程（或系统方法，图灵机，算法）？后来，学术界用“停机时间问题”代替了“决策问题”，这是一个复杂的学术问题，我们将在后面讨论.

Turing在1936年的论文中对“决策问题”做出了否定的回答: 决策问题无法确定，这证明“没有通用过程可以确定计算给定函数K的公式”，其中“函数演算“ K”是指一阶谓词. 该证明基于图灵的“图灵机”来表达希尔伯特的“一般过程”.

由于图灵机的“计算”无法解决某些问题，因此采用了图灵机的“非计算”，因此图灵提出了“机器智能”并在“学习”的基础上开设了第一个“人工智能” ”机制. .

由于“图灵机”是“计算”的定义，因此不能说“非计算图灵机”，而应该说“非计算计算机”或“解决计算以外的问题的方法”. 在我看来，计算，图灵机，算法，功能，映射等大致上是相同的概念（概念A，可重复的问题解决方法），而计算机，流程，信息处理，问题解决等则是更大的概念（概念B，解决问题的方法），这也为学习和智力留下了空间（概念C，可变问题的解决方法）. 这意味着A和C没有交集，并且两者都是B的子集. 普遍的观点是A和B是相同的概念，而C是它们的子集. 我的文章（）指出了这个问题.

从这个意义上说，我认为“决策问题”和“工人智慧”之间存在内在联系. 也许可以说，如果图灵机要解决“计算问题”，那么智能系统正试图解决“决策问题”. .

如果将输出用作输入的“判断”，则可以这样说. 但是即使这样，从这个意义上说，“判断”还是与传统的判断根本不同. 其中之一是，对解决问题过程的“最终状态”没有严格的定义. 在日常生活中，但是当我们找到问题的解决方案时，我们是否会接受还是持续改进，不仅取决于该问题和答案，还取决于此时是否需要解决其他问题. 严格来说，从逻辑上讲，我们接受或报告的解决方案通常不是最终解决方案. 以这封电子邮件为例，如果我再花一周的时间来写，肯定会质量更高，但是由于我还有很多工作要做，所以我不得不在这里停止写，但是之后我仍然会闲着发送. 我下来时就谈到了这个话题. 这是“决定”还是“停机时间”？

刘宇: 学术界用“停机时间问题”代替了“决策问题”（Entscheidungs问题），并认为图灵在1936年的论文中证明了“停机时间问题”. 实际上，图灵并未提出“停机时间”一词，该术语可能源自马林·戴维斯.

Turing在论文中提出了“决策问题”的基本问题:

-是否有图灵功能可以确定任何图灵机都是“可计算的”？

看看“停机时间问题”:

-是否有图灵机可以判断任何图灵机“停止”？

也就是说，“停机时间问题”的实质是用“停机时间”代替预期结果的“可计算性”.

那么，“停机时间”可以代替“可计算性”吗？ “停机时间问题”可以代替“决策问题”吗？

如果您问: 以这封电子邮件为例，如果我再花一周的时间写它，它的质量将会更高，但是由于我还有很多工作要做，所以我不得不在这里停止写，但是发送出去. 空闲时我仍然会想到这个话题. 这是“决定”还是“停机时间”？

在本文中，图灵将图灵机分为两类: 无圆机和圆机. 无圈机器是指可以在有限的步骤中打印结果从而定义“可计算性”的图灵机. 圆形机器是指不能在有限的步骤中打印结果的图灵机. 图灵引用的两个无圈机器示例为“不间断”: 打印序列010101 ...，打印序列01011011101111 ...

我认为“停机时间问题”不仅是一个复杂的学术问题，而且对认知和实践产生了严重影响.

也许进一步，您可能会问: 由于绑架“宕机问题”，人们很难理解计算机与人工智能之间的关系吗？

王沛: 让我们看一下相关概念:

（1）“问题”定义了从输入集到输出集的“映射”或“功能”.

（2）“算法”或“计算”是可重复的，可执行的，有保证的终止过程，可将问题的每个输入转换为相应的输出，

（3）``决策问题''是只有两个输出值``是/否''的问题. 原则上，每个问题都可以转换为等效的决策问题.

（4）当且仅当存在能够解决相应决策问题的图灵机时，问题才是“可计算的”.

（5）如果图灵机关闭了所有合法输入，则可以根据关闭时是否处于最终状态来确定输出，从而可以确定问题所在.

因此，“可计算”，“可确定”和“停机”确实是不同的概念，但是它们是等效的，也就是说，对于其中一个，“是/否”的回答是对另一个. 答案.

就人工智能而言，在（1）和（2）中与计算理论是有区别的: 问题的解决方案与情况和历史有关，因此它是不可重复的，而且“解决方案”都不是. 也不是“非解决方案”的明确界限. 在这种情况下，（3）-（5）不再是有意义的问题. 因此，传统的计算理论确实限制了人工智能的发展. 停机问题，决策问题和可计算问题与人工智能没有直接关系. 当然，智能系统需要做出“判断”，但这与传统的“判断”无关. 原因之一是“判断”不是二进制的“是/否”，但必须具有一定程度，而且还受可用处理时间限制. 计算复杂性理论也不与人工智能直接相关. 如果对某种类型问题的处理没有遵循任何算法，而是在特定情况下进行了分析，那么就没有什么计算复杂性可言. 这就是为什么P等于NP并且与人工智能无关的原因. 更不用说多项式算法了，即使恒定的时间开销也不一定足够快.

刘宇: 很高兴您经历了几个相关的概念！

人工智能和计算理论在（1）和（2）中分道扬so，因此“决策问题”是一个转折点，非常重要！

形式上，``决策问题''是只有两个输出值``是/否''的问题;但是从内容的角度来看，它具有复杂的含义，例如“决定一个难题（例如15个难题）是否达到预期的模式”与“确定拼图是否可以达到预期的模式”完全不同. ”: 前者是“是/否”的“不确定性问题”，而后者是不知道“是/否”的“不确定性问题”的“确定性问题”，也就是说，不存在算法确定的问题确定谜题是否有解决方案，这是计算机理论的真正“决策问题（Entscheidungsproblem）”，与图灵计算能力的局限性有关，而启示需要“人为”，这种干预开启了通往人工智能的道路. .

如果将“决策问题”定义为“只有两个输出值为“是/否”的问题”，则实际的“决策问题（Entscheidungsproblem）”的“不确定性”消失，结果您所指出的是: 人工智能和计算理论在（1）和（2）中分道扬;； （3）-（5）不再是有意义的问题. P是否等于NP与人工智能无关. .

因此，我认为“一个“决策问题”是只有两个输出值是/不是”的问题”，需要对此定义进行研究，因为它不仅影响对人工智能本质的理解，而且人机关系，并直接影响对P vs NP与人工智能之间关系的理解.

我们一直专注于P vs NP停机问题 半可判定，并认为这是解决P vs NP问题的关键. .

王培: 人工智能和计算理论在（1）和（2）中是分道扬，的，因此“决策问题”是一个转折点，非常重要！

形式上，``决策问题''是只有两个输出值``是/否''的问题;但是从内容的角度来看，它具有复杂的含义，例如“决定一个难题（例如15个难题）是否达到预期的模式”与“确定拼图是否可以达到预期的模式”完全不同. ”: 前者是“是/否”的“不确定性问题”，而后者是不知道“是/否”“不确定性问题”的“确定性问题”，也就是说，没有算法来确定是否一个难题有一个解决方案，这是计算机理论中真正的“决策问题（Entscheidungsproblem）”，与图灵计算能力的局限性有关.

我认为这里的区别主要是问题实例（元素，元素）和问题类型（类型，集合）之间的区别. 确定问题与后者有关，也就是说，是否存在统一的方式来处理问题类中的所有实例. 这里的否定结论还说: “没有统一的方法来解决所有这些问题”停机问题 半可判定，不是每个实例都无法解决，也不是“解决方案”的标准不确定.

启蒙运动需要“人”的介入，从而为人工智能开辟了道路. .

这是一个见解. 我认为智能（无论是人类还是机器）在“计算”方面都没有比图灵机更强大，但是可以跳出计算领域.

如果将“决策问题”定义为“只有两个输出值是/不是”的问题”，那么实际“决策问题（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的汉密尔顿路径的存在是确定性的（是/否），但是不确定该存在的确定，即，当算法给出“是”时，可以得出结论: 从s到t的哈密顿路径；但是当算法回答为否时，不能得出结论，从s到t没有哈密顿路径.

从这个意义上说，计算和判断不匹配，判断成为一个“问题”. 因此，我说: “这是计算机理论中真正的“决策问题（Entscheidungs问题），反映了图灵计算能力针对此类问题的局限性. ”

可以看出，如果将``决策问题''定义为``仅具有两个输出值的''是/否''的问题，则问题A和问题B之间的界限将变得模糊，导致您上述批评，但这不应该是一种计算. 理论是错误的，但是人们误解了图灵在Entscheidungsproblem问题上的工作，...

王沛: 看来问题确实在于对Entscheidungs问题的理解. 我的理解基本上与所说的相似. 根据这种理解，您的A和B问题都是可判定的问题，不同之处在于，只有一个已知的多项式算法，而另一个仅知道指数算法. 但是可判定性（和可计算性）仅涉及算法的存在与否，而不涉及算法的复杂性.

刘宇: 是的，问题的确是在理解Entscheidungs问题（决策问题）

在讨论开始时，我问: 您如何看待“决策问题”与“工人智慧”之间的关系？目的是初步探讨“判断问题”在从图灵机到人类智能的过渡中的作用.

我说明了这种观点:

关于Entscheidungs问题和“停机时间问题”之间的关系，需要进一步深入. 它可能会触及多年的计算机理论隐患，这直接影响了计算复杂性理论与人工智能之间的关系. P是否等于NP和人工智能之间的关系？了解关系. 如果您有兴趣，我们可以一个接一个地讨论.

参考:

【1】王培，计算机不仅是“计算机”，而且图灵机也不是“计算机”:

【2】上午图灵，关于可计算数字及其在Entscheidungsproblem中的应用，1936年: 〜robins / Turing_Paper_1936.pdf

【3】上午图灵，计算机和智能，Mind，59，433-460，1950年.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-282444-1.html