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

如果我们将图灵机M开始于含有n的磁带上，而它最终停机时，磁带含有m，则我们说M在输入n时计算出m。M(n)＝m 如果我们将M开始于输入n，而它或者不能停机，或者停机时，不含有一个自然数，比如它含有0或是中间有空白符，那么我们便说M(n)是未定义的(undefined)，用符号表达为： M(n)＝↗。如此，我们便可为每个图灵机M关联一个部分函数，M：N → N∪{↗} 。我们说这个函数M是全函数，当，对于所有n ∈ N M(n) ∈ N，即M(n)总是被定义的时。

现在我们便可形式化地定义，再之前非形式化描述过的，递归可枚举。若S ⊆ N，而S是递归可枚举的，当且仅当，我们有某个图灵机M，其使得S是经由M计算的函数的像，符号地，S＝{M(n)│n ∈ N；M(n) ≠ ↗}

这样，S是递归可枚举的，仅当，它可以被某个图灵机列出。若S是递归可枚举的，且其元素可由图灵机M像上面那样列举出来。这样，我们就可以描述另一个图灵机P，其在输入n时，以循环的方式运行图灵机M与其所有可能的输入，直到最终输出n。如果这发生了，那么P停机，并输出“1”，即，P(n)＝1，如果n ∉ S，那么，M将永远不会输出n所以P(n)也永远不会停机，即P(n)＝↗。

设P(n)↓意味着，图灵机P在输入n时，最终能够停机。对于一个图灵机P，定义L(P)，即P所接受的集合为，那些当输入进P而P能最终停机的，L(P)＝{n│P(n)↓}

上述论证表明，如果一个集合S是递归可枚举的，那么其可以被图灵机P接受，即S＝L(P)。这个式子的逆同样也成立。这样，S是递归可枚举的，当且仅当，它能被某个图灵机P所接受。

我们说一个集合S是可判定的，当且仅当，有一个全图灵机M，其可以判定，对于所有的n ∈ N，是否有n ∈ S，把值“1”作为是，“0”则为不是。对于所有n ∈ N，如果n ∈ S，则M(n)＝1，即，M在输入n上最终停机，并输出“是”，而如果n ∉ S，则M(n)＝0，即M在输入n上最终停机，并输出“否”。关于可判定的同义词是，可计算的，可解的，递归的。

对于S ⊆ N，S的补便是N – S，即，所有不在S中的自然数的集。我们说集合S是共递归可枚举的(co-r.e.)，当且仅当，其补是递归可枚举的且共递归可枚举的，然后我们可以在第一列中列出所有它的元素，而在第二列中列出所有它的非元素。通过这样的方式，我们可以判定，给定元素n，是否属于S，这只需要浏览一下这两行然后等着n出现就行了。如果其出现在第一行，那么n ∈ S，反之出现在第二行，就是n ∉ S。事实上，一个集合是递归的，当且仅当，它是递归可枚举的且共递归可枚举的。

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