一个流行的关于“停机问题”不可判定的证明是基于自指的反证法，即基于悖论的证明【1】。

该证明过程如下： 假设存在一个可计算的全函数halts(f)判定函数f是否停机，如果f停机，则返回true，否则返回false。现在考虑下面这个函数g：

def g():

    if halts(g):

        loop_forever()

如果halts(g)返回true，即g停机，那么g将调用loop_forever而g不停机，矛盾。如果halts(g)返回false，即g不停机，因为g不调用loop_forever而停机，也矛盾。因此，关于存在halts 是一个可计算的全函数的最初假设不成立。

函数g是一个典型的“判断性质的自指函数”，本质上与“说谎者悖论”相同。据文献记载，这个证明最初出现在英国计算机学者Christopher Strachey（1916-1975）在1965年写给The Computer Journal杂志的一封信中【2】。

***

To the Editor,

The Computer Journal

An impossible program

Sir,

A well-known piece of folk-lore among programmers holds that is impossible to write a program which can examine any other program and tell, in every case, if it will terminate or get into a closed loop when it is run. I have never actually seen a proof of this in print, and though Alan Turing once gave me a verbal proof (in a railway carriage on the way to a Conference at the NPL in 1953), I unfortunately and promptly forgot the details. This left me with an uneasy feeling that the proof must be long or complicated, but in fact it is so short ans simple that it may be of interest to casual readers. The version below uses CPL, but not in any essential way.

在程序员中，有一个著名的民间传说，认为不可能写出一个可以检查任何其他程序的程序，并且在每一种情况下都能知道它在运行时是否会终止或进入一个死循环。虽然艾伦-图灵曾经给过我一个口头证明（1953年在去NPL开会的火车上），但不幸的是，我很快就忘记了细节。这给我留下了一种不安的感觉，认为这个证明一定很冗长或复杂，但事实上，它是如此的简短和简单，以至于它可能会引起普通读者的兴趣。下面的版本使用了CPL，但不是以任何基本方式。

Suppose T[R] is a Boolean function taking a routine (or program) R with no formal or free variables as its argument and that for all R, T[R]=True if R terminates if run and that T[R]=False if R does not terminate.

假设T[R]是一个布尔函数，以一个没有形式变量或自由变量的例程（或程序）R为参数，对于所有的R，如果R运行终止，T[R]=True，如果R不终止，T[R]=False。

Consider the routine P defined as follows

考虑例行程序P，定义如下

rec routine P

       $L: if T[P] go to L            

               return $

If T[P]=True the routine P will loop, and it will only terminate if T[P]=False. In each case T[P]= has exactly the wrong value, and this contradiction shows that the function T cannot exist.

如果T[P]=True，例程P将循环，只有当T[P]=False时才会终止。在每种情况下，T[P]=的值都是错误的，这个矛盾表明函数T不可能存在。

Churchill College,

Cambridge                                

                                          Your faithfully,

                C. Strachey.

参考文献：

【1】https://en.wikipedia.org/wiki/Halting_problem

【2】https://academic.oup.com/comjnl/article/7/4/313/354243