ACM通信

的观点

老实说

由纳德肖维茨
ACM通信，2021年5月，第64卷第5期，37-41页
10.1145 / 3431281
评论

我们在如何教授可计算性理论(ACM/IEEE计算机科学课程的核心组成部分)方面有一个严重的问题。

让我解释一下。在相当长的一段时间里，我教授了一门可计算性课程。按照标准课程(如Hopcroft和Ullman所描述的)¹⁴)，和我在该领域的同事们一致，我在无数个场合声称，一个计算模型比另一个更强大，或者两个模型具有相同的计算能力。在某些情况下，该论证诉诸于普通集包含，而在其他情况下，它涉及到通过编码模拟的概念。想象一下，当我意识到这两种比较方法实际上是不兼容的时候，我有多懊恼!

当两个模型使用相同的实体时，大家自然会使用形式语言或函数集的简单集合包含。我们教授有限状态自动机可以识别由正则表达式定义的相同语言，但严格意义上比下推自动机弱，我们引入回文或非方词作为肯定的证明。¹³类似地，我们断言原始递归(或等价地，通过有界的循环为仅循环)比一般递归(与而循环)，因为这两个模型，只有后者可以计算Ackermann函数。¹⁴

另一方面，当考虑的模型的领域不同时，在比较它们之前需要进行编码。例如，艾伦·图灵(Alan Turing)在他1936年那篇意义深远的论文的附录中指出，lambda可计算函数和使用他的图灵机可以计算的函数具有相同的计算能力。“标准的”机器描述(五元组列表)被转换成十进制数，然后用lambda微积分表示为Church数字。图灵还证明了他的机器和一般递归是等价的。²⁴为了表明图灵机可以计算所有一般的递归函数，数字通常(和浪费)表示为一元计数符号的序列。¹⁴

不幸的是，前面的两种比较方法，即包含和模拟，可能会产生相互排斥的结果。最简单的例子是计数器(又称明斯基机，算盘模型)。每个计数器都包含一个自然数，可以对其进行递增、递减和零测试(请参阅侧边栏)．由于只有两个计数器，该模型甚至还不够强大，无法对其输入进行平方计算^2,20.或者认识质数。¹⁵但是，如果我们同意代表一个数字n指数2ⁿ(一种比Gödel表达式编号更简单的编码)，然后，感谢已故的马文·明斯基的巧妙证明，^14,17我们发现两个计数器足以计算每个可计算函数。这就是为什么人们会遇到这样的语句:

• 众所周知，具有两个计数器的有限状态自动机是图灵完备的。⁹
• 明斯基证明了双计数器机器是通用的，因此存在不可确定的停止问题。¹⁶

如果一个人认同集合包含的意义，那么这种完整性或普遍性的主张将是明显错误的，而在模拟意义上，它们显然是正确的，这确实是明斯基所证明的。正如Rich Schroeppel所表达的那样:“任何计数器机器都可以被2CM模拟，只要一个模糊的(原文如此!)输入和输出都接受编码。”^20.因此，我不同意这样的说法:“关于计数器的令人惊讶的结果是，两个计数器足以模拟图灵机，因此可以接受每一种递归枚举语言。”¹³双计数器机器确实可以模拟图灵机，但它们并不“接受”通常“现状”、未编码意义上的所有可递归枚举语言，素数就是一个典型的例子。

问题的关键是，教师应该直截了当，乐于助人，并解决这种矛盾。我们不能继续忽视这样一个事实:通过我们在课堂上使用的一种比较方法，2计数器机器严格地弱于(完整的)3计数器机器，而通过我们也认可的第二种方法，两者被认为是等价的。

回到顶部

解决方案

谢天谢地，并不是一切都完了。只要我们付出额外的努力，我们可以吃到我们的谚语蛋糕，仍然拥有它。

首先，放弃模拟将是一场彻底的灾难，因为所有传统的无约束模型都具有相同的能力，尽管与不同的实体操作，这一观点是可计算性理论的核心，正如丘奇-图灵论文所神圣的那样。因此，尽管看起来很痛苦，但我们不得不放弃对计算函数的范式的包含概念，例如一般递归和原始递归——尽管不是对形式语言，我将在后面解释。

所谓“模拟”通常指的是(单射，1-1)编码c从仿真模型的领域米进入仿真模型的领域米的这样每个函数f前者的计算由函数镜像f '由模拟器计算米的这样f '（c（x₁),…c（X_n)) =c（f（X₁…,X_n))查询所有输入资料X₁、……X_n来自…领域的M。以下是教科书上的引文:

• 要证明两个模型是等价的，我们只需要证明我们可以用一个模型来模拟另一个……任何两个计算模型，只要满足一定的合理要求，就可以相互模拟，因此在能力上是等价的。²²
• 相对于编码的可计算性是比较计算模型能力的基本概念，因此，我们可以使用“相对于一些合适的编码的合并”的概念来比较计算模型的能力。²³

但是什么应该被认为是“合理的”或“合适的”，这取决于旁观者的看法。如果我们真的走这条模拟路线，我相信我们必须这样做，如果我们要有一个在数学上令人满意的计算理论，那么我们迫切需要一个允许编码的正式定义c。

哈特利·罗杰斯解释说:“选择编码是为了让它本身由不受限制的非正式算法给出。”¹⁹这一要求无论多么有效，同时也太不正式，可能太慷慨了。它是循环的，因为我们的目标是界定有效计算的界限。正如理查德•蒙塔古(Richard Montague)所抱怨的那样:“自然程序是将考虑限制在那些在某种意义上‘有效’的通信上……但有效性的概念仍有待分析，而且似乎确实与可计算性相一致。”¹⁸解决它的不正性的唯一方法是在跨领域(如Boker和Dershowitz)的“有效”算法上达成一致的统一的、正式的概念⁴)．尽管如此，一种“不受限制的”编码可以想象地扩大模拟模型可以计算的函数集，就像我们在计数器和有效的指数编码中看到的那样。

那么，应该对编码施加哪些其他限制呢?显然，我们需要一个相同的编码c为所有模拟函数工作f。如果要研究单个函数，那么很容易提出一种特定的“偏差编码”，使单个不可计算函数看起来是可计算的。另一方面，我们必须坚持相同的编码c两者都用作输入x_我以及输出f，否则一切都很容易破产(佩斯巴特菲尔德等人)。⁸)．理想情况下，这些限制将确保(与计数器或lambda演算不同)没有允许的编码可以扩展计算函数的类。具体地说，我们必须排除赋予图灵机或递归函数超能力(即所谓的“超计算”)。我们如何保证这一点?夏皮罗²¹提出，对于(柏拉图)数的编码是“可接受的”，编码的后续函数也应该是可计算的米”。换句话说,米的必须包含一个函数年代：c（n）c（n+ 1)模拟继任者。我同意。但是为什么继任者呢?

幸运的是，编码对于通常的用例来说不是问题。事实上，任何编码都不能打破图灵障碍。具体来说，人们可以证明没有(内射)编码允许模拟所有可计算函数加上一个不可计算函数，如暂停。^3.事实证明，有效地模拟后续函数是必要和充分的，以保证图灵机不能模拟(在单值编码下)任何意外的情况。⁴这就是我们要保持大局不变所需要的一切。

另一方面，只需稍加努力，就可以设计出一个递归函数(对Ackermann函数的修改)，无论编码如何，它都不能被原始递归模拟。^3.因此，原始递归严格地比递归弱仍然是正确的——在非常强烈的意义上，任何(内射)编码都不会赋予原始递归完全的图灵能力。如果单计数器机器不能模拟所有递归函数也不是同样可以证明的，像“结合这些模拟，我们看到双计数器机器和任意图灵机一样强大(单计数器机器严格来说不如图灵机强大)”这样的表述¹²是站不住脚的。

至于正式语言(一些字母上的单词集)，情况正好相反。编码是坏的;包容是好的。同态映射可能保留了大多数语言模型的相对功能(它们对字符串结构的纯局部影响)，但更一般的注入或双射则没有。事实上，任何(非单数)字母表的单词之间都存在着一种令人不安的双射现象，即所有的常规字母都具有这种令人不安的特性+所有与上下文无关的语言都可以通过有限状态自动机进行识别。这种情况实际上更加难以忍受:人们同时也可以通过这种恶作剧的双射来识别许多任意的不可定语言，这些语言具有普通的有限自动机。¹⁰

就语言而言，在比较语言模型的能力时，我们被迫坚持直接包含和禁止(甚至是可计算的)输入字符串映射。早些时候，当处理(所有)可计算函数时，我们确实可以通过映射进行模拟，但那是因为同样的映射也适用于所有可能的函数输出。⁵

回到顶部

相关的问题

编码还有另一种无处不在的用法，同样需要格外小心。通常，人们希望在字符串或数字以外的对象上计算函数，如图形、逻辑公式或计算机程序。为此目的，必须以某种方式用运算模型的输入/输出语言表示这些对象，通常是字符串或数字。引用:“应用我们在可计算性方面的工作的一个必要的先决条件……是用数字编码表达式....有许多合理的方法来编码有限序列，我们选择哪一种并不重要。”⁶

---

放弃模拟将是一场彻底的灾难，因为所有传统的无约束模型都具有相同的能力，尽管与不同的实体操作，这一观点是可计算性理论的核心，正如丘奇-图灵论文所神圣的那样。

---

然而，要做到“合理”，需要确保编码除了忠实地表示输入之外不做任何事情。

例如，编造一个图灵机的编码，把一个关于机器的无法确定的问题变成一个容易计算的问题，这是一件小事。让W₀,W₁是所有二进制字符串的枚举(在字母{0,1}上)，并且让米₀,米₁，…是所有图灵机的一些枚举(在输入字母上)。以下是四个典型的可决性问题:

• T（我,我):机米_我停止在输入W_j．
• H（我):机米_我停止在输入W₀．
• U（我):机米_我停止所有输入W₀,W₁.．.
• D（我):机米_我停止在输入W_我．

在单个特定输入(如空单词)上停止只是奇偶性问题，如果对标准机器枚举重新排序，那么奇数机器在该输入上停止，而偶数机器则不会。这种图灵机编码的障碍是，它也使普通任务无法计算。具体来说，不能修改给定机器的代码，使其以某种相关但不同的方式执行，因为需要确定修改后的机器的终止行为。所以是否问题H是否可决定实际上取决于机器是如何被编码的。

考虑如下断言:

• 图灵的一个重要见解是“停止问题”H(它接受一个整数n和输出H（n= 1当且仅当n= <P>是一个有效的[自包含]程序的编码P而且P终止)是不可判定的。⁷

对于通常的、直接的机器描述编码，这个问题确实是无法确定的，但对于任何数量的可选编码，它都是可以确定的。“通用停顿”问题也是如此U。

另一方面，更基本的停止问题，T（我,我)，询问的行为我^th机器上的j^th可能的输入，无论机器如何编码或输入如何枚举，都是不可确定的。然而，我们必须注意如何对<我,我>是为计算模型(例如普通的图灵机)编码的，这些计算模型只允许一个表示两者的单一输入我而且j。类似地，“对角线”语言D由当输入字符串在枚举中具有与机器在编码中具有相同的索引时停止的那些机器的索引组成，对于任何和所有机器编码和字符串枚举都是不可计算的。因此，“没有任何编码(将所有图灵机编码为数字)能够代表TM。米这样l（米)=l_d(对角线语言)，”正如霍普克罗夫特等人所说，¹³但对于不接受任何东西的机器的集合(l_e)．¹³遗憾的是，我所见过的教科书中没有任何一本阐明了哪些机器编码是有效的，用于什么目的以及为什么有效。例如，下面的注释并不排除表示包含关于被表示机器的有限数量的不可计算信息，例如它是否总是在特定输入时终止或停止:

• 图灵机的字符串表示方案的细节是无关紧要的[只要]:(1)我们可以将每个图灵机表示为字符串。(2)给定图灵机的字符串表示米和一个输入X，我们可以模拟米的输入执行X。¹

恶意字符串编码的标准部分将允许像往常一样模拟执行，而附加的附加部分可以允许算法决定关于它们的其他无法确定的问题。然而，过分热心的编码在将纯程序作为参数传递而不进行编码的编程语言中并不是一个问题。

最后，当谈到复杂性比较时，每个人都意识到表示是一个需要考虑的问题，但是需求仍然很模糊:“一个问题的难处本质上独立于特定的编码方案……用于确定时间复杂度……很难想象一个‘合理’的编码方案，它与标准的编码方案的差异超过多项式级……我们这里所说的‘合理’是无法形式化的……”¹¹

在我看来，标准的字符串和图像压缩方案是非常合理的编码，尽管在许多情况下会成倍地减小大小。无论如何，复杂性理论仍然严重缺乏“合理性”的正式的原则性定义。(但参见Boker和Dershowitz⁵一个提议。)

回到顶部

外卖

概括一下这里提出的问题的要点:

• 自动机或可计算性中的每一门课程都利用集合包含作为比较不同语言定义形式的计算能力的手段。
• 事实上，每一门这样的课程都声称有各种各样的计算模型的等价性，以支持丘奇-图灵的论点，这种等价性是建立在相互模拟的基础上的。
• 正如我们所见，这两个概念在逻辑上是不相容的。
• 我所遇到的教科书和教员都没有认识到这种根本的矛盾，更不用说解决了。

因此，我们至少必须对这门学科的传统教学方式作出以下改变:

• 应该只使用集合包含作为比较形式语言类的一种手段，例如在演示中，与上下文无关的语法是一种严格意义上比正则表达式更具包容性的形式主义。
• 我们永远不应该使用集合包含来比较基本递归和一般递归的能力，或者为循环程序而-循环机，或者有两个计数器的单计数器机器，而不提及它实际上已经证明，一个也不能模拟所有其他的。
• 教师应该强调必须始终小心对待编码，因为它们很容易改变计算能力，同时指出，对于通常的图灵级可计算性用例来说，已经证明这不是一个问题。
• 我们绝对应该避免使用空磁带暂停、空语言接受或类似的问题作为不可定性的基本例子，因为它们的可定性是依赖于编码的。相反，我们需要在将标准的双输入中断问题简化为其他问题时解释输入编码的微妙作用。
• 我们应该谨慎，永远不要说或暗示双计数器机器识别所有可递归枚举的语言(它们不)，也不要说它们计算(而不是模拟)所有的图灵可计算函数。
• 人们不应该选择lambda演算作为完全授权的计算模型的主要示例(因为它模拟更多的比计算)。

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.

---

没有发现记录