头发长了。11 月后疫情反复，许诺已久的自得园管控放松计划不出意外地泡汤，只好再找到鑫鑫这位好邻居帮我理个发。得知他也为自己理发，和他开玩笑说自古以来的理发师悖论在他这里终结。

今天在看《信息简史》时恰好翻到哥德尔、图灵和停机问题。回想起以前学习这块内容都把理发师悖论当作引子，突然意识到自己一直以来对停机问题的理解非但不深，甚至还对理发师悖论的认识有严重误区。

围绕理发师悖论，把自己对停机问题的回顾和再理解记录下来。

停机问题诞生之前

既然打算更深入理解停机问题，自然要扒一扒问题产生的源头。翻看了研一运筹学课胡旭东老师的讲义，发现其实里面有几十张 slides 都在讲停机问题形成背后的计算理论。至于为何自己印象不深，应该是当时受课时限制老师没在课上细讲，自己课后又没认真学习理解。

（也不知道 5 年后自己哪来的动力，还有心思给自己补这一课……）

停机问题由图灵于 1936 年提出并证明。该问题起源于图灵对“机器能否思考”的探索，最终他用一台自己构想出的机器实现论证。论证得以顺利开展的关键在于图灵对 “计算” 概念的把握。在那个年代，人仍然是从事各类运算工作的主体，除了大量纸上作业，更多时候靠的只是灵光一闪。总之，当时人们对于什么是 “计算” 其实没有一个清晰的概念——这也使基于机器的自动计算乃至思考难以成行。对此，图灵指出，计算应该是一个机械的过程，或是一种算法，其本质是人在实际求解问题时所要经历的步骤。鉴于图灵对计算、算法的界定贡献，后人将图灵的停机提问与探索作为计算 / 算法理论开端。

图灵受到的影响可以从源头、直接这两个角度来观察。

影响图灵探索之源头可上溯至在他一个世纪之前由巴比奇发明的差分机，以及那之后逻辑学、信息学领域的研究进展。值得一提的是，图灵对于用机器实现思考的想法与巴比奇“将蒸汽应用到思考和算数上（数可代表万事万物）”的想法不谋而合，他们都致力于用机器实现数学计算。然而，图灵并未和巴比奇一样将思考付诸工程实践，仅将自己心中所想、被后人称为 “图灵机” 的机器构造进行了描述，其中停机是该机器可实现的基本运行操作之一——停机问题之 “停机” 即来源于此。

图灵所受直接影响来自于希尔伯特 1928 年提出的判定问题（Entscheidungs problem）：

是否存在一种有效的程序，以预先确定某个结论能不能从一组给定的假设用逻辑推演出来。

希尔伯特提出这一问题的目的是希望为全部数学奠定一个坚实的逻辑基础。这位整理出 “新世纪数学家应当努力解决的 23 个数学问题” 的数学家当时在纠结：数学真理是否无论时间早晚都能够被证实？他曾宣称：在数学里没有 “我们将来也不知道”。换言之，若希尔伯特提出的判定问题为真，则人们可以通过一套严格、分步的算法，用一种演绎推理的形式语言表示有效的推理过程，实现对（数学）问题的自动化证明。

希尔伯特的提问并非空穴来风。早在他之前，便已经有数学家为构筑牢固的数学体系根基而努力，期望以形式化符号语言证得每一个数学命题的真伪，比如《数学原理》的作者之一罗素。在这本由他和怀海特共同于 1910 至 1913 年间完成的巨著前言，罗素提到在打造完美数学的过程中，他为处理一些矛盾和悖论耗费了大量精力，理发师悖论便是其中之一。

理发师悖论与哥德尔不完备

以下引用部分来自知乎回答——

一座小城里有位理发师，有一天他做出一项规定：

他给并且只给那些不给自己理发的人理发。

理发师的这个规定似乎很有道理：既然有人自己给自己理发了，那么我就不用“多此一举”，我再给这个人理发。

最初，这个规定并没什么问题后来，随着这个理发师自己的头发越来越长，他发现他陷入了一个两难的境地：他该不该给自己理发？

  • 如果他为自己理发，那么他就成为了他规定中那个“自己给自己理发的人”，那么他就不应该为自己理发；
  • 如果他不为自己理发，那么他就规定中那个”不给自己理发的人“，那么他就应该为自己理发。

综合以上两种情况，”他为自己理发当且仅当他不为自己理发“，这成为了一个悖论。

简言之，理发师悖论并不是说简单说理发师因为一些技术原因（比如看不到自己脑后）不给自己理发，而是因为理发师自己先立了个 flag——“给且只给那些不给自己理发的人理发”，正是这个套娃 flag 使得其纠结于到底该不该给自己理发。

（之前自己的确错用、滥用这一经典悖论了，今后可得注意，呵呵）

需要指出的是，包括埃庇米尼德斯悖论（克里特人说克里特人都说谎，那么克里特人到底说没说谎？——“这句话是假话”）在内，从古至今与理发师悖论类似的悖论还流传着很多。这些悖论平日里大多只停留于纸面，毕竟这个世界根本做不到始终如一、是非清白（克里特人不可能真的全部撒谎，而且就算是骗子嘴里也不可能全是假话；理发师也不会永远纠结于给不给自己理发，该理理就完了）。但对于一些人而言，这些悖论成了挡在其追求学术真理路上的一堵墙，因为他们企图构建的正是一个严丝合缝的逻辑体系，代表人物便是罗素——他尝试构建的符号主义力求借助完美严谨的符号与规则以实现精确表达，最终机械地为每一个数学事实作出证明。因此，不难理解为何此类悖论令他“如鲠在喉”——还被后人一并归作“罗素悖论”。

围绕罗素悖论，哥德尔最终证明了一个自洽（一致、相容，即不存在前后矛盾）的形式体系必定是不完全（不完备，即存在难辨是非之处）的，亦即不可能存在完全且自洽的形式体系。哥德尔于 1931 年公开了他这项被后人称为“哥德尔不完备定理”的研究，世人从此明白数学是无法既完备又一致的。然而，即便是知道了对某个特定、封闭的形式逻辑体系（比如罗素心目中的数学体系）而言，其中必有一些命题无法从该体系内部得到证实或证伪，那么这些命题能否通过体系外的逻辑或规则得到判定？这便是希尔伯特关心的判定问题，亦成为了图灵思考停机问题的切入点。

脱胎于图灵机的停机问题

图灵在判定问题的基础上，提出了一个更具体的问题：“所有的数都是可计算的吗？”他的思考是：也许有些数虽可被命名和定义，但不可被计算。图灵进一步提出：如果一个数的小数表达式可以被机器写出来，它就是可计算的，比如$\frac{a}{b}$（有理数/代数数）、$\sqrt{2}$（无理数/代数数）、$\pi$（超越数）。因此，对于那些不可被计算的数，意味着无法在有限步骤内用机器得出其小数表达式。不过，这样一台机器长什么样？运行方式如何？当时并无实例可供参考。图灵脑洞大开，认为一台能写出小数表达式的机器——这就是传说中的“图灵机”——基本组成应包括纸带、符号和状态，可实现停机、移动、打印、擦除等基本操作，并可由此实现更复杂的过程。

图灵最终证明了凡是人可计算的工作，图灵机也一样能做，且一台图灵机可连同输入其中的数据一起被代码化。在此基础上，图灵进一步在大脑中构思出一台名为“通用图灵机”的机器，简称$U$。$U$不仅能接受一般意义上的图灵机所能接受的寻常数据作为输入，还能接受任何被编码的机器作为输入，即对机器的代码化描述。这意味着，倘若一个问题可以被一台机器解决，那么该问题也可以拿到$U$上通过模拟该机器（的运行）而得到解决。

图灵进一步延伸其思考：既然$U$能够同时接受一组数据$I$和一台模拟出来的图灵机$P$作为输入，那么它能不能判断$P$在以$I$为输入的情况下是否经有限步停机并输出“停机”，或是本身为死循环并输出为“死循环”？这便是所谓的“停机问题”。

以下对于停机问题的精炼描述引用自知乎回答——

「停机问题」研究的是：是否存在一个「程序」，能够判断另外一个「程序」在特定的「输入」下，是会给出结果（停机），还是会无限执行下去（不停机）。

（该回答的作者还以伪代码的形式清晰阐述了停机问题，这里不做复制，但接下来会被我拿来参考，用于写我对于停机问题和理发师悖论的理解）

能够实现停机判断的机器是不存在的。图灵运用反证法得出了这一结论：

  • STEP 1：假设存在这样一个图灵机$TM(P,I)$，能判断$P$输入$I$时停机并输出“停机”，反之输出“死循环”。考虑到图灵机能够被代码化，这样的机器本身其实也可被视作程序$P_{TM}$，亦可作为输入$I_{TM}$，因此$TM$同样可以判断将$I_{TM}$输入$P_{TM}$时$P_{TM}$是否停机。

  • STEP 2：比照$TM$可以设计出另一个图灵机$\overline{TM}(P,I)$，它的运行逻辑是先调用$TM(P,I)$并获取其结果，后据此输出一个相反的结果。

  • STEP 3：考虑将$I_{\overline{TM}}$和$P_{\overline{TM}}$作为$TM(P,I)$的输入：若$TM(P_{\overline{TM}},I_{\overline{TM}})$输出为“停机”，则依据$TM(P,I)$的运行规则，$I_{\overline{TM}}$在作为$P_{\overline{TM}}$的输入时后者输出为“停机”；然而根据$\overline{TM}(P,I)$的运行规则，既然$\overline{TM}$输出为“停机”，此时被它调用的$TM$应该是“死循环”的输出结果才对，这显然和$TM$真正的输出结果相矛盾。类似的，当$TM(P_{\overline{TM}},I_{\overline{TM}})$输出为“死循环”，则一样会出现“$TM$理论上应该是‘停机’却实际输出‘死循环’”的矛盾场景。

所以说，一个能够判断“任一图灵机程序在给定输入下停机与否”的$U$并不存在，即判定问题的答案是否定的。

很显然，上述这样的矛盾场景再现了“罗素悖论”，它存在那种能让罗素血压飙升的循环自指。鉴于哥德尔已经给出了“一致与完备无法兼得”的论证，图灵的研究成果似乎是对哥德尔工作的重复，不过他更进一步指出当数被拿来编码机器的行为时，悖论就会现身——任何形式体系中都必然存在不可判定的命题。这样看来，图灵的工作最终证明了：数学是不可判定的，其不完全性源于其不可计算性。

用停机问题伪代码写理发师悖论

就用 Python 格式的伪代码写吧——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 判断程序：一个人头发长了，理发师该不该去干活（是否停机）【停机判定程序】
def toufa_gai_li_le(lifashi, changmaoguai)
  result = lifashi(changmaoguai)
  if result ！= None:  # 理发师有活干，也就是没停机
    lifa = True # （得知）ta不自我理发，判断理发师有活干，也就是没停机
  else:
    lifa = False # （得知）ta自我理发，判断理发师没活干，也就是停机
  return lifa


# 理发（行动）程序：一个人给不给自己理发【本质是一个循环函数、循环机】
# 在预设前提下（给自己理发的人）对应True，即程序会一直运行下去
def self_can_lifa():
  while(True):
    pass  # 既然这个人给自己理发，那就一直让ta自个理去吧（不断循环……）


# 理发师（工作）程序：开工or收工？【本质是一个测试机】
# 函数输入变量changmaoguai即长毛怪，是我对需要理发者的定义，哈哈
# changmaoguai取值按照是否为0作区分，其中0代表不给自己理发，反之给自己理发。
def lifashi(changmaoguai):
  if changmaoguai == 0:
    result = '理发师去给这个人理发！'
  else:
    self_can_lifa() # 不管ta，让其自个回去理（自我循环）
  return result


if __name__ == '__main__':
  # 在自得园里，鑫鑫练就了理发的手艺，即可以触发理发师程序
  toufa_gai_li_le(lifashi, 0)  # -> True，比如当我去找鑫鑫
  toufa_gai_li_le(lifashi, 1)  # -> False，比如当北院来的理发师去找鑫鑫（虽然不可能）
  #（当然，以鑫鑫的性格，搞不好也会去给师傅理，呵呵）
  #（话说，北院理发师一次收费30但其技术受到同学们诸多差评，好奇这手艺何以伺候北院大领导们……）

  # 当鑫鑫也头发也便长了，即changmaoguai=lifashi……
  toufa_gai_li_le(lifashi, lifashi) # =======悖论出现=======
  # 鑫鑫：作为长毛怪，我到底是（该说）我给自己理发呢，还是不给自己理发呢……

（完）

photo by cottonbro studio