Question

到目前为止我们已经看到图灵机有非常多的能力和灵活性：它们可以执行编码成数据的任意程序，执行我们能想出来的任意算法，运行无限长时间，对它们自身的描述进行计算。尽管它们很简单，可这些小的假想的机器都已经被证明能表示一般的通用系统。

如果它们这么强大而灵活，那是否存在图灵机乃至真实世界的计算机和编程语言不能做的事情呢？

在回答这个问题之前，需要让这个问题更明确一些。我们可以让一台图灵机做什么样的事情呢？怎么识别它已经干完了呢？需要研究每一种可能的问题吗？或者只考虑其中一部分问题是否足够呢？我们只是在寻找解法超越自己当前理解的问题，还是在寻找已经知道永远不能解决的问题呢？

我们可以通过集中在判定性问题上以缩小问题范围。判定性问题的答案为是或者否，就像“2 比 3 小吗？”或者“正则表达式 (a(|b))*与字符串 'abaab' 匹配吗？”功能性问题的答案是一个数或者某个非布尔值，如“18 和 12 的最大公约数是多少？”判定性问题比处理功能性问题要容易一些，但它们仍然很有趣，值得我们研究。

如果存在一个算法，对任何可能的输入都能保证在有限时间内解决一个判定性问题，那么这个问题就是可判定的（或者叫可计算的）。邱奇－图灵论题认为每一个算法都能由图灵机执行，所以对于一个可判定性的问题，我们需要设计一台总是产生正确答案的图灵机，并且如果运行足够长的时间，它总是能停机。把一台图灵机的最终配置解释成“是”或者“否”的答案是很简单的：例如可以检查在当前纸带的位置上是否写有 Y 或者 N，或者完全忽略纸带内容，而只是检查它的最终状态是接受状态（“是”）还是非接受状态（“否”）。

前几章的所有判定问题都是可判定的。如“有限状态自动机能接受这个字符串吗？”和“这个正则表达式匹配这个字符串吗？”不证自明是可判定的，因为我们已经写了 Ruby 程序以便通过直接模拟有限自动机解决它们。给我们足够的时间和精力，那些程序可以费力地转换成图灵机，而且因为它们的执行包含有限的步骤——DFA 模拟的每一步会消耗输入的一个字符，而输入的是有限数目的字符——它们能保证总是停机给出是或者否的答案来，因此原来的问题都满足可判定的条件。

其他问题有些微妙。“这个下推自动机能接受这个字符串吗？”可能看起来不是可判定的，因为我们已经看到用 Ruby 对一台下推自动机的直接模拟有可能永远循环，也不会给你答案。但是，恰好存在一种方式可以准确地计算出一台特定的下推自动机为了接受和拒绝一个给定长度的输入字符串要经过多少模拟步骤，11 因此问题终究是可判定的：我们只是计算所需要的步数，对那些步骤运行模拟，然后检查输入是否已经被接受了。

11简言之就是：每一台下推自动机都有一个上下文无关文法，反之亦然；任何上下文法都可以用乔姆斯基范式重写；这种范式下的任何上下文无关文法为了生成长度为 n 的字符串一定要经历 2n-1 步。因此我们可以把原始的 PDA 转成一个上下文无关文法，把上下文无关文法重写成乔姆斯基范式，然后把这个上下文无关文法转换回 PDA。由此产生的下推自动机与原来的机器能识别同样的语言，但现在我们准确地知道完成它需要多少步了。

那每次都能这么做吗？总是存在一种聪明的方式接近一个问题然后找到一种方法实现一台机器，或者一个程序，让它保证能在有限时间内解决这个问题吗？

好吧，不行，不幸的是不行。有许——无限多——多判定性问题而且大量的问题是不可判定的：没有保证能停机的算法能解决它们。这些问题中每一个都是不可判定的，不是因为我们还没有找到合适的算法，而是因为问题本身从本质上就对某些输入不可能解决，而我们可以证明永远也不会找到合适的算法。