原文：https://scottaaronson.blog/?p=8106
作者：Scott Aaronson
译者：Kurt Pan
在Michael Sipser的《计算理论导论》教科书中，他有一个柏拉图式完美的作业练习，如此完美，以至于我凭记忆就可以重构它，尽管我已经十多年没有打开这本书了。问题是这样的：
如果上帝存在，则令 为常数 1 函数，如果上帝不存在，则为常数 0 函数。问 可计算吗？ （提示：答案并不取决于你的宗教信仰。）
正确答案是，是的， 是可计算的。为什么？因为常数 1 函数是可计算的，常数 0 函数也是可计算的，所以如果 是其中之一，那么它是可计算的。
如果你仍然想狡辩，那么请考虑以下平行问题：
如果上帝存在，则 等于 3；如果上帝不存在，则 等于 5。 问 是质数吗？
答案同样是肯定的：尽管 还没有完全在数学上被确定，但已经足够让我们说它是质数（就像我们问“ 是集合 的一个元素）， 是质数吗？”一样）。类似地， 已经被确定得足以让我们说它是可计算的。
Sipser 试图传达的更深层次的点在于，可计算性的概念是适用于函数簇或无限序列，而不是单个的是否问题或单个的整数的。相关的，甚至更重要的是：可计算性是关于是否存在计算机程序以指定方式将输入映射到输出；它并没有说关于选择、找到或编写该程序可能有多困难。编写这个程序甚至可能需要解决上帝的存在问题，这个可计算性的所有定义都关心。
在过去的 25 年里，我无数次被问到关于以下问题的不同变体，每次我都带着一种即将被它的光彩所折服的神情：
P 与 NP 问题本身是否是 NP 难问题，因此无法解决？
每次我被问到这个，我都很难一一解开层层误解。但给初学者说一下：“NP难”的概念适用于函数簇或语言，例如 3SAT 或 独立集 或 团 （Clique） 等，所有这些都接受一个输入（一个布尔公式、图等）并产生相应的输出。 NP 难意味着，如果你有一个多项式时间算法将输入映射到输出，那么你就可以通过归约将其转换为 NP 类中任意语言或函数的多项式时间算法。
相比之下，P 与 NP 是一个单个的是否问题。它的答案（据我们所知）可能独立于集合论的 Zermelo-Fraenkel 公理，但问题本身不可能是不可计算的或 NP 难的，这是没有意义的。事实上，正确回答 P 与 NP 问题的快速程序是平凡地存在的：
如果 P=NP，则程序输出“P=NP”。
如果 P≠NP，则程序输出“P≠NP”。
在上周关于 Busy Beaver 5 突破性解决的帖子的评论中，我得到了以下问题的几种变体：
https://scottaaronson.blog/?p=8088
无法计算 BB(n) 值的最小 是多少？ BB(6) 是否已经不可计算了？
我再次解释了 Busy Beaver 函数是不可计算的，但可计算性的概念并不适用于像 BB(6) 这样的单个整数。事实上，无论 BB(6)最后等于哪个整数，程序“输出 ”显然都存在，它显然就是输出这个整数！
同样地，我们可以要求最小的 ，使得 BB(n) 的值在 ZF 集合论（或其他一些公理系统）中无法证明——这正是 Adam Yedidia 和我在 2016 年提出的问题（当前记录为，提高了我和 Adam 的 ）。但每个特定的整数都是“可计算的”；只是 BB 函数作为一个整体是不可计算的。
https://arxiv.org/abs/1605.04343
唉，作为解释这一点的“回报”，我得到了更多的阻力，甚至是嘲笑和谩骂，我选择将这些留在审核队列中。
因此，我开始将其视为理论计算机科学中的僵尸级误解：这种针对无限序列和函数簇设计的概念不断被误用到单个整数和开放问题。 （或者相关地：对停机问题的不可计算性与哥德尔不完备性的不断合并。虽然它们密切相关，但只有哥德尔允许你讨论单个陈述而不是无限的陈述簇，也只有图灵可计算性是绝对的，而不是相对于某个公理系统。）
不管怎样，我写这篇文章主要是为了下次这只教学僵尸从坟墓里爬出来，咕哝着“不可计算的整数……”时，我有一个链接可以给到。但同时我也要问我的读者：对于如何抑制这个僵尸，你有什么想法？
