Turing 机

语录

图灵机（Türing Machine）：1936 年，阿兰·图灵写了一篇关于计算机器的设计和局限性的论文，由此，它们被冠以了图灵的名字。这个变音ü 其实是不必要的，这只是大家推测，这么难以理解的东西一定是德国人写的。

——摘自Faster Than Thought: A Symposium on Digital Computing Machines（1953）

Hilbert第十问题

1900年，在巴黎举行的第二届国际数学家大会上，希尔伯特做了一次堪称数学史上影响最为深远的演讲。在演讲中，希尔伯特列举了23个他认为最具重要意义的数学问题。

希尔伯特第十问题又称“判定丢番图方程的可解性”对其具体的描述为“给定一个系数均为有理整数，包含任意个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数整数上是否可解。”当时大家对“过程”，“有限次计算”的含义还不清楚。

Turing 对这个问题进行回答，“过程”即是Turing机的执行过程，“有限次计算”是将Turing机执行的每一步作为一次计算，要求Turing机可以有限步内停止。

Turing可计算性

当有了Turing机之后，人们想知道哪些函数是Turing机可以计算的，哪些函数是Turing机不可以计算的。Turing机可以计算的函数称为Turing-可计算函数，形式化定义在定义5.6.

可以证明Turing-可计算的函数包括：

1. 本原函数（定理5.1）
2. 常数函数，前驱函数，加法函数（命题5.2）
3. 复合算子（定理5.13）
4. 原始迭代算子（定理5.14），原始递归算子（推论5.15）
5. 正则 $\mu$-算子（推论5.17）

因此，若$f$是一般递归函数，则 $f$ 是Turing-可计算的（定理5.18）。

可判定性

希尔伯特的判定问题是判断某个方程在有理数整数上是否有解。我们想用Turing机解决这个问题，当某个方程有解时，我们希望Turing机输出0，当没有解时，Turing机输出1。问题的关键在于我们如何把一个方程变成Turing机的输入。

哥德尔认为，数学中的符合串，比如一个方程，均可以用整数表示出来。这个整数称为数学符号串的哥德尔编码。有了哥德尔编码之后，我们可以将方程的哥德尔编码作为Turing机的输入。这样可判定性问题转换为：是否存在Turing机，对于某些输入，其输出是0，对于另外的某些输入，其输出是1。这时，对于输出是0的所有输入组成一个集合，我们称这个集合是可判定的。形式定义在定义5.9.

可判定性

设 $A$ 为 $\mathbb{N}$ 的子集， $A$ 是可判定的指 $A$ 的特征函数 $\chi_A$ 是 Turing-可计算的，即有机器 $M_A$，其对于输入 $\bar{x}$，若 $x\in A$，则输出 $\bar{0}$；否则，输出 $\bar{1}$。$A$ 是可判定的有时也称 $A$ 是Turing-可计算的。

Turing给出了著名结果，停机问题不可判定。

Church-Turing 论题

经过漫长的科学发展，人们对希尔伯特提出的判定问题有了深刻认识。然而，人们依然有这样的疑问：对于集合 $A$，若是Turing机不可计算的，是否存在更高级的计算机器使得 $A$ 是可计算的。Church,Turing和Markov等人宣称他们的模型所刻画的可计算函数类等同于非形式定义的直觉能行可计算函数类。即Turing宣称，所有人们觉得能计算的函数，Turing机都能计算。Church-Turing论题总结如下：

Church-Turing论题

直觉能行可计算（部分）函数类等同于Turing-可计算（部分）函数类。

这个论题可以看成一种“信仰”，有些人相信，有些人不相信。不相信的人希望找到一个反例，即找到一个函数，直觉上是可以计算的，然而Turing-机无法计算。迄今为止，还没有找到任何一个反例。