一个不可判定的Bender

—Bender可以回答什么类型的问题？一个简单的问题表明了存在主义。: 日期：2019年1月16日 14:02, 星期三; 作者： Jesse Riggs

“我是弯腰，弯曲大梁，这就是我所做的一切。” —Bender

弗莱的问题

美国经典作家兼导演，辛普森一家和科幻恶搞，Futurama， David X. Cohen是我最喜欢的创意人才之一。科恩不仅是四次获得艾美奖的卡通创作者，而且他也非常聪明。1988年，科恩在哈佛大学获得物理学学士学位，然后进入加州大学伯克利分校，获得计算机科学硕士学位。他的喜剧经常散布着令人讨厌的数学，科学和哲学。通常，我发现自己把工作拉开了。但是，我的朋友告诉我，我正在深入研究幼稚的漫画

然而，今天，我正在分享一个问题，在Futurama的第一集中提出，这说明了关于知识极限的惊人事实。

被困在头部博物馆内的弗莱乞求班德执行一项简单的拯救生命的任务。

Fry：如果你只是弯曲吧，我们可以离开这里。

Bender：皮肤管上的梦想。我只是为了建筑目的而弯曲。我看起来怎么样？一个de-bender？

Fry：谁在乎你的编程。如果有人让你跳过桥，你呢？

Bender：我要检查我的程序......是的。

现在，我没有打开围绕自由意志和决定论的蠕虫，我想提请你注意弗莱问题的一个特点;一种异常，计算机科学的大师可以从中定义宇宙的边缘。

更具体地说，一个能够回答这个问题的弯曲者 - 事实证明 - 非常特别。这样的弯曲程序可以编程，为我们提供许多有用的答案，使我们能够理解不了解的问题。我们可以给这个弯曲器提供DNA链，然后他可以告诉我们它是不是病毒。我们可以给他两个不同的语法，然后他可以告诉我们他们之间是否没有共同的句子。他可以告诉我们，一个软件是否会成功地给我们一个答案，或者它是否会永远运行。

计算机科学家的工作是建立解决问题的机器。但是，有时候，科学家会遇到一个问题，或一组他们不确定如何构建解决方案的问题。此时，可能更容易证明任何可以解决此类问题的机器都不存在。所以，问题就变成了“能够回答弗莱问题的弯曲者甚至存在吗？”

机器如何解决问题？

机器（Bender）解决问题的方式很像你玩棋盘游戏的方式。他被赋予一套规则。然后他读取一些输入，比如骰子上的数字，或者甲板上的卡片。然后 - 根据游戏规则 - 他将一些数据（例如游戏块的位置）写入磁盘。他反复继续这个过程，直到他到达游戏结束的最后一个方格 - 然后返回一个输出：他是赢还是输了比赛;是或否。

可判定的问题

有无数的问题可以决定（回答）是或否，例如：“罐子里有10个豆形软糖吗？”，“10等于10？”或“Jellybean等于Fruit Loop？” ”。我们可以通过构建一组始终达到“ 是”或“ 否”的解决方案的步骤来证明这些问题是可判定的。例如，我们将在一个红色扑克筹码上叠加十个蓝色扑克筹码。对于罐子里的每个豆荚豆，我们会吃它然后丢掉一个扑克筹码。如果当Jellybeans全部被吃掉时，桌子上只有一个红色的扑克筹码，我们就知道罐子里有十个Jellybeans。这组步骤称为算法。

为了进一步拓宽我们对可判定问题集的视野，我们可以将可判定问题的参数更改为变量，例如X和Y ，以创建新的可判定问题。例子包括：“罐子里有X Jellybeans吗？”和“ X等于Y ？”。但是，并非所有问题都可以通过算法解决。

不可判定的问题

问题1。

这句话是错误的。

以上陈述是真的吗？

考虑问题1 ，这个陈述是真是假？当我们假设这个陈述是真的时 - 因为它说它是假的 - 它必须是这样的; 假…？但是，当我们假设它是假的 - 因为声明说它是假的 - 它必须是假的，它是假的。那么，一定是真的......？也许，在形而上学的意义上，这既是真实的，也是虚假的。但是，在物质世界中，任何事物都无法同时被判断为真假。这是一个矛盾↯ 。所以，我们不能建立一个能回答这个问题的机器。这个问题被称为不可判定的问题。

整个宇宙充满了不可判定的问题，就像这个问题一样。事实上，由于数学宇宙的残酷之美，无可比拟的问题存在无数次难以解决的问题。

问题2。

这句话是X.

以上陈述是真的吗？

现在考虑问题2 。如果X等于true，那么这个问题的答案显然是肯定的 。但是，由于X可能是假的，这个问题是不可判定的。这意味着我们无法设计算法来解决这一系列问题;即使X可能等于真。

本德可以解决任何可以解决的问题吗？

简单的答案是肯定的。Bender属于一类名为UTM（Universal Turing Machines）的机器。如果我们回到游戏示例，我可以更好地解释这意味着什么。简单地说，Bender非常精致，可以玩游戏规则来玩任何其他游戏的规则。

这个定义使我们得出一个令人惊讶的结论。如果我们要构建一个模拟Bender的游戏，那么Bender就可以玩它了。而且，他可以玩一种以各种可能的方式模拟自己的游戏。但是，这并不矛盾。事实上，这就是你所有的计算机所做的事情。您用来阅读此博客的Web浏览器是一台机器的模拟，它可以解决与运行它的机器相同的所有问题。

在这个游戏中，Bender是我们的主角，他可以玩一个游戏，他是主角。此外，Bender可以玩模拟自己玩模拟自己的游戏的游戏。这里仍然没有矛盾。但是，我们可以利用这一事实引导我们与我们的证据相矛盾。

弗莱的问题可判吗？

“当数学家考虑算法时，通常是从上帝的角度来看。他们有兴趣证明，例如，有一些算法有一些有趣的属性，或者没有这样的算法，并且为了证明这样你不需要实际找到你正在谈论的算法......“—Daniel Dennett¹

弗莱问Bender一个问题。但是，它是否可以判定？弯曲机是否可以编程来回答问题形式的问题“这个输入X的弯曲器是否说跳？”如果没有，那么就没有必要尝试构建这样的弯曲机。

但是，如果我们找不到它，很难证明算法不存在。因此，为了证明它不存在，我们必须首先假设有一个能够回答这个问题的弯曲者，然后找到一个表明他不存在的矛盾。

如果Bender可以回答Fry的问题，这个假想的弯曲者会说跳。让我们看看我们是否能像问题1那样找到矛盾。

Illustration 1

图1中显示的是Bender，他作为输入 - 弯曲（Bendito）和问题。如果Bendito输出跳跃作为他的第一个输出或在任何其他输出上咬我闪亮的金属屁股 ，Bender将输出是的。

但是，一个邪恶的软件开发人员决定稍微改变一下程序，以便当Bendito没有说跳跃作为他的第一个输出时，Bender会说跳。请记住，这个邪恶的开发人员不会对决策制定算法做出任何更改。他只是改变了该算法的两个可能输出之一。这款新的Bender Bender1如图2所示。

Illustration 2

现在，让我们想象一个超级邪恶的软件开发人员决定对该程序进行另一次更改，以便Bender只需要一个输入。这个新的单输入包含Bendito。然后，在弯曲机接受这个本迪托之后，他将Bendito作为输入馈送给自己。同样，决定算法没有变化。这款新型弯管机Bender2 如图3所示 。

Illustration 3

现在我们可以在这个程序的设计中找到我们的矛盾，从而表明这样的弯曲机不存在。让我们考虑Bender被喂入自己的场景，也就是我们假设Bendito 是 Bender。我们正在考虑这个问题，好像Bender问自己“如果我问自己'我是否问自己”如果我被编程为X，那么我会X吗？“然后我会回答跳？'然后我会回答跳？“如果Bender回答是，那么他表明他会跳。然而，如果他回答是的，那么他表明他喂入自己的本德尔不会跳。因为Bender是Bender，他会同时跳起而不跳。他不能跳，不能同时跳↯。因此，我们反驳了能够回答这个问题的弯曲者的存在。而且，更重要的是，这表明Bender1不存在，因此Bender也不存在。

如果这看起来有点混乱，让我们看一个类似的问题，我们正在编写Pinocchio而不是弯曲程序。如果我们要给匹诺曹编程说“我的鼻子会长大”，他的鼻子会长大吗？如果他的鼻子不长大，那么他就是说谎，他的鼻子会长大。如果他的鼻子长大了，他说实话，所以他的鼻子不会长大。他的鼻子会长大而不会同时生长↯ 。这是我们的矛盾。

大家好消息！班德不存在。好吧，至少一个可以解决这个问题的弯曲机不可能存在。这是一个好消息，因为我们不再需要尝试设计这样的弯曲机。我们知道他不可能存在。所以，f ***它。 :)

本文中描述的弯曲器完全类似于Hopcroft等人描述的Hello World程序。当程序员遇到她认为不可判定的问题时，她可以使用Hello World程序编写程序来做出决定。如果她能做到这一点，那么她就表明问题是不可判定的。