柳渝：关于图灵机与人工智能的关系的对话 - 奇点O论坛（转载）_图灵机_人工智能

2024-11-13 04:06:00 智能写作

http://blog.sciencenet.cn/blog-2322490-1238775.html

柳渝：关于图灵机与人工智能的关系的对话 - 奇点O论坛（转载）_图灵机_人工智能智能写作

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

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

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

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

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

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

以是在图灵机的意义下，“打算”与“剖断”是同等的。
换句话说，“剖断问题”实际上是指图灵机意义下“剖断成为问题”。
以是，这里的“问题”与普通意义下的“问题”比较，上升了一个“层级”。

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

这此意义上，我认为，“剖断问题”与“⼈工智能”存在着内在的联系。
或容许以说，如果说图灵机是办理“打算问题”，那么智能系统便是试图办理“剖断问题”，。
。
。

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

存在。
但详细联系办法须要仔细谈论。

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

由于“图灵机” 便是“打算” 的定义，以是不能说“图灵机的非打算”，而该当说“打算机的非打算”，或者“打算之外的办理问题办法”。
在我看来，打算、图灵机、算法、函数、映射等等大致是同一个观点（观点A，可重复解题办法），而打算机、过程、信息加工、办理问题等等是一个更大的观点（观点B，解题办法），个中也给学习和智能留有空间（观点C ，可变解题办法）。
这便是说A和C没有交集，而二者都是B的子集。
现在的普遍意见是A和B是同一个观点，而C是它们的子集。
我这篇文章（https://mp.weixin.***.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）那里分道扬镳，以是“剖断问题”是迁移转变点，非常主要！

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

启迪须要“人”的参与，如此开启了走向人工智能的道路，。
。
。

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

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

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

其结果便是你指出的：人工智能与打算理论在（1）和（2）那里分道扬镳；（3)-(5）都不再是故意义的问题，P是否即是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