图灵的“停机问题”

资料来自：科普书《复杂》和知乎网站。

假设存在这么一个“停机程序”，不管它是怎么实现的，但是它能够回答“停机问题”：它接受一个“程序”和一个“输入”，然后判断这个“程序”在这个“输入”下是否能给出结果：

def is_halt(program, input) -> bool:
  # 返回 True  如果 program(input) 会返回
  # 返回 False 如果 program(input) 不返回

例如

from halt import is_halt

def loop():
  while(True):
      pass

# 如果输入是 0，返回，否则无限循环
def foo(input):
  if input == 0:
    return 
  else:
    loop()

is_halt(foo, 0)  # 返回 True
is_halt(foo, 1)  # 返回 False

如果这个“停机程序”真的存在，那么我就可以写出这么一个“hack 程序”：

from halt import is_halt

def loop():
  while(True):
      pass

def hack(program):
  if is_halt(program, program):
    loop()
  else:
    return

这个程序说，如果你（ is_halt ）对 （program) 判停了，我就无限循环；如果你判它不停，我就立刻返回。

那么，如果我们把“hack 程序”同时当做“程序”和“输入”喂给“停机程序”，会怎么样呢？

is_halt(hack, hack) 

你会发现，如果“停机程序”认为hack(hack) 会给出结果，即 is_halt(hack, hack) 返回 True ，那么实际上 hack(hack) 会进入无限循环。

而如果“停机程序”认为 hack(hack) 不会给出结果，即 is_halt(hack, hack) 返回 ，那么实际上 hack(hack) 会立刻返回结果……

自相矛盾

结论：不存在 is_halt 这样的停机程序。