第7章递归论的基本知识 第3节图灵机 (c)如果(x+1,y+1,2)∈S则存在一个自然数u使得(x+1,y,u)∈S且(x,u,x)∈S 注意:一个好的三元组集S具有如下性质:如果(x,y,2)∈S,则 (1)z=A(x,y) (2)S包含计算A(x,y)过程中所需的所有的“先前的”三元组(x,y,A(x,y) 接下来我们把三元组(x,y,2)编码成(x,y,x)=2+13y+15+1;并把一个三元组的编码 的有穷集{u…,wk}编码成{u1,u2,…,wk}。所以一个三元组的有穷集可以被编码成 个自然数 令S表示编码为υ的三元组集。则谓词“(x,y,z)∈S。”是原始递归的,因为它等价 于“玉<v()=(x,y,x)”。更进一步,“S是一个好的三元组的集合”也是一个原始 递归谓词(练习)。所以谓词 R(x,y,v):=“是一个好的三元组集的编码并且彐z<v(x,y,z)∈S) 也是原始递归的 于是函数f(x,y)=R(x,y,u)是部分递归的。所以A(x,y)=2(x,y,2)∈Srax)也 是部分递归的;并且f(x,y)和A(x,y)都是全函数。 第3节图灵机 英国数学家图灵是二十世纪最伟大的数理逻辑学家之一,也被人称为计算机科学和 人工智能之父。在他1936年的文章中1,他提出了图灵机的概念,并且证明了停机问题 是不可判定的,从而解决了希尔伯特提出的判定性问题。虽然哥德尔和丘奇等人也在更早 或差不多同时也给出了判定冋题的否定答案,但图灵提岀的被称为图灵机的计算模型可 以被视为纯机械的物理机器,因而比形式系统更能代表任何的机械装置,从而在不可判定 问题的解答上更为直观也更有说服力。 731图灵机的定义 我们先看图灵机的物理描述。图灵分析了一个“计算员( computor)”进行计算的过 程,得出了一台图灵机应该包括以下要素 On Computable Numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc第 7 章 递归论的基本知识 第 3 节 图灵机 (c) 如果 (x + 1, y + 1, z) ∈ S 则存在一个自然数 u 使得 (x + 1, y, u) ∈ S 且 (x, u, z) ∈ S。 注意：一个好的三元组集 S 具有如下性质：如果 (x, y, z) ∈ S，则 (1) z = A(x, y)。 (2) S 包含计算 A(x, y) 过程中所需的所有的“先前的”三元组 (x ′ , y′ , A(x ′ , y′ ))。 接下来我们把三元组 (x, y, z) 编码成 ⟨x, y, z⟩ = 2x+13 y+15 z+1；并把一个三元组的编码 的有穷集 {u1, · · · , uk} 编码成 ⟨u1, u2, · · · , uk⟩。所以一个三元组的有穷集可以被编码成一 个自然数 v。 令 Sv 表示编码为 v 的三元组集。则谓词“(x, y, z) ∈ Sv”是原始递归的，因为它等价 于“∃i < v((v)i = ⟨x, y, z⟩)”。更进一步，“Sv 是一个好的三元组的集合”也是一个原始 递归谓词（练习）。所以谓词 R(x, y, v) := “v 是一个好的三元组集的编码并且 ∃z < v ((x, y, z) ∈ Sv)” 也是原始递归的。 于是函数f(x, y) = µvR(x, y, v) 是部分递归的。所以A(x, y) = µz((x, y, z) ∈ Sf(x,y)) 也 是部分递归的；并且 f(x, y) 和 A(x, y) 都是全函数。 第 3 节 图灵机 英国数学家图灵是二十世纪最伟大的数理逻辑学家之一，也被人称为计算机科学和 人工智能之父。在他 1936 年的文章中 1，他提出了图灵机的概念，并且证明了停机问题 是不可判定的，从而解决了希尔伯特提出的判定性问题。虽然哥德尔和丘奇等人也在更早 或差不多同时也给出了判定问题的否定答案，但图灵提出的被称为图灵机的计算模型可 以被视为纯机械的物理机器，因而比形式系统更能代表任何的机械装置，从而在不可判定 问题的解答上更为直观也更有说服力。 7.3.1 图灵机的定义 我们先看图灵机的物理描述。图灵分析了一个“计算员（computor）”进行计算的过 程，得出了一台图灵机应该包括以下要素： 1On Computable Numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. 9