“停机问题”存在着二个版本的流行证明：一个是基于“说谎者悖论”的反证法；另一个是基于cantor的对角线法。学术界宣称“停机问题”及这二个证明源于图灵1936年论文，这是值得大大质疑的，。。。

罗杰·彭罗斯在《皇帝新脑》中对基于cantor对角线法的“停机问题”证明做了通俗易懂的介绍，我部分翻译如下：

Hilbert问题无解（57-64）

我们如何判定任何给定的图灵机（当给定输入）是否停机？ 。。。是否有算法可以完全自动地回答这个停机问题？ 图灵回答：没有。

图灵的论证基本上是这样的：首先假设有这样一种算法，那么一定有图灵机H“判定”图灵机Tn在作用于数m时是否停机：如果Tn不停机，H就输出0；如果Tn停机，就输出1：

H(n;m) = 0 if Tn(m) = □; 1 if Tn(m) stops.

现在让我们设想一个无限的数组列出了所有可能的图灵机作用于所有可能的输入，并给出所有的输出。 阵列的第n行显示第n台图灵机的输出，适用于输入 0,1,2,3,4,……： 

在上表中，我做了点小手脚，没有列出图灵机的实际编号。。。只是随机地编造了这个表，目的是给出一个总体印象。

我并不要求真的计算出这个数组，比如通过某种算法。 (事实上，并没有这样的算法，我们马上就会看到），我们只是要想象，真正的列表已经以某种方式摆在我们面前，也许是由上帝摆出来的！ 如果我们试图计算这个数组，□的出现会造成困难，因为我们可能不知道什么时候该把□放在某个位置，因为这些计算永远都在进行！

然而，如果我们被允许使用我们假定的H，就可以提供一个生成表的计算程序，因为H会告诉□实际出现的位置。 这可以通过在计算H(n; m)之前让Tn对m采取行动来实现；然后我们只允许Tn在H(n; m)=1的情况下对m采取行动（即只有在计算Tn(m)实际给出答案的情况下），如果H(n; m)=0（即如果Tn(m)=□）则简单写成0。 我们可以把我们的新程序（即通过H(n; m)的作用在Tn(m)之前得到的程序）写为

Tn (m) X H(n; m).

(这里我使用了一个关于数学运算排序的常见数学惯例：右边的运算要先进行。请注意，从符号上看，我们有□ x 0 = 0）。

现在的表是这样的： 

注意，假设H存在，这个表格的行由可计算序列组成。 (我所说的可计算序列是指一个无限的序列，其连续的值可以由一个算法产生；也就是说，有一些图灵机，当它应用于自然数m=0, 1, 2, 3, 4, 5时，会产生序列的连续的成员) 。现在，我们注意到关于这个表的两个事实。首先，每一个可计算的自然数序列都必须在其行中的某个地方出现（也许是多次出现）。 这个属性在有□的原始表格中已经是真的了，我们只是增加了一些行来替代“哑巴”图灵机(即那些至少产生一个□的机器)。

其次，假设图灵机H实际存在，表已被可计算地生成（即由某种明确的算法生成），即由程序Tn(m) X H(n; m)生成。 也就是说，存在一些图灵机Q，当它作用于一对数（n，m）时，会在表中产生适当的条目。 为此，我们可以在Q的磁带上以与H相同的方式对n和m进行编码，我们有

Q(n; m) = Tn(m) X H(n; m).

我们现在应用一个巧妙而强大的装置的变体，即Georg Cantor的对角线法。考虑对角线上的元素、 现在用粗体字标记：

这些元素提供了一些序列0,0,1,2,1,0,3,7,1,......，现在我们在其中的每项上加1：

1,1,2,3,2,1,4,8,2,… 

这显然是一个可计算的过程，鉴于我们的表是可计算生成的，它为我们提供了一些新的可计算序列，事实上是序列1+Q(n; n)，即

1+Tn(n)xH(n;n)

(因为对角线是通过使m等于n而给出的)。但是我们的表包含了每一个可计算的序列，所以我们的新序列一定是在列表的某个地方。 然而，这不可能是这样的！因为我们的新序列与第一列中的第一行不同，与第二列中的第二行不同，与第三列中的第三行不同，以此类推，这显然是一个矛盾。正是这个矛盾确立了我们一直试图证明的东西，即图灵机H事实上并不存在!  没有通用的算法来判定图灵机是否会停机。

这个论证的另一种表述方式是注意到，在假设H存在的情况下，有一些图灵机数，例如k，用于算法（对角线过程！）1+Q(n; n)，所以我们有

1+Tn(n)xH(n;n)=Tk(n).  

但如果我们把n=k代入这个关系中，得到：

1 + Tk(k) x H(k; k) = Tk(k).

这是一个矛盾，因为如果Tk(k)停止，我们得到不可能的关系：

1 + Tk(k) = Tk(k) 

(因为H(k; k)=1)，而如果Tk(k)没有停机(所以H(k; k)=0)，我们有同样不一致的：

1 + 0 = □.

一个特定的图灵机是否停机的问题是一个完全明确的数学问题（而且我们已经看到，反过来说，各种重要的数学问题可以被表述为图灵机的停机问题）。 因此，通过指出不存在判定图灵机停机问题的算法，图灵指出不可能有判定数学问题的一般算法。 希尔伯特的Entscheidungsproblem无解!

参考资料：

https://en.wikipedia.org/wiki/Roger_Penrose

https://www.anobii.com/zh-Hans/books/huang-di-xin-nao/9787535715814/00252a11170822ddfb