SEP：可计算性与复杂性（一） (5-3)

特别地，由于公理很好辨别并且推理规则也很简单，我们就将会有一个机械化程序可以列出所有的证明。注意，在证明中，每一行，要么是公理，要么是经由其中一个推理规则从前面的行中所推出的。对于任何给定的字符串，我们都可以辨别其是否是一个证明。这样，我们便可系统性地列出所有长度为1，2，3等等的符号串，然后检查它们是否是一个证明。如果是，那么我们就可以将证明中的最后一列加入到，定理的列表中。这样，我们便可列出所有证明，即，通过一个简单的机械化程序，能准确地列出所有一阶逻辑的有效式。更精确地说，有效式的集，就是可计算函数(computable function)的值域。用当代的术语来说就是，一阶逻辑有效式的集是，递归可枚举的(recursively enumerable(r.e.))

然而，哥德尔完全性定理对于给出一个判定问题的明确解答来说并不充分。给定一个式子，φ，如果φ是有效的，那么上述程序最终将会列出它，并且给出“是，φ是有效的”这样一个答案。然而，如果φ不是有效的，我们可能终究都不会得到这个事实。现在缺少的就是一个程序，去列出所有非有效式，或者等价地去列出所有可满足的式子。

一年后，也就是1931年，哥德尔提出了他的不完备性定理(Incompleteness Theorem)震惊了整个数学界：我们没有完全的且可计算的，关于自然数的一阶理论的公理化。这意味着，没有这样一个合理的列表，我们可以从中准确地证明出所有数论中的真命题(Gödel 1931).。

几年之后，丘奇与图灵独立证明了判定问题是不可解的。丘奇通过运用哥德尔不完备性定理中的手段，展示了，一阶逻辑的可满足的公式集不是递归可枚举的，即，它们不可被系统化地，经lambda演算的可计算函数列出。图灵引入了他的机器，并证明了许多我们将在下一节中会讨论到的有趣定理。特别地，他证明了停机问题(halting problem)是不可解的。同时作为推论，他也得到了判定问题同样也是不可解的。

希尔伯特非常失望，因为他的计划，关于所有数学判定程序，被证明为是不可能的。然而，如我们将要看到的那样，我们将会学到大量关于计算的基础性质的知识。

1. Turing Machines

在图灵1936年的论文(On Computable Numbers, with an Application to the Entscheidungsproblem)中，他引入了这个机器，并奠定了它们的基本性质。

他清晰而理论性地给出了什么是，机器执行计算任务，的意义。图灵如下定义了他的机器：

• 一个有限的可能状态集Q，因为任何设备都必须处在，有限的可能状态的其中一个之下。

• 一个潜无穷的磁带，其由单元格σ₁，σ₂，σ₃组成，它们来自于某个有限字母表Σ；(Σ可以是包含至少两个符号的任意有限集。出于方便，可以固定Σ＝{0，1，b} ，即该字母表包含二进制字母再加上空白单元符。我们通常假设磁带的有限初始段包含二进制符号，而余下部分则为空白。)

• 一个磁带读写探头，h ≥ 1，扫描磁带的单元格σₕ；以及最后，

• 一个转换函数，δ：Q × Σ → Q × Σ × {–1，0，1}。(这个转换函数的意思是，从任意给定状态q，以及读取到的任意给定的符号，σₕ，δ告诉我们机器应该进入的新状态，应被记在当前方格中的新符号，以及下一个探头位置，h'＝h＋d，其中d ∈ {–1，0，1}是由δ给出的位移。)

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。