图灵的“停机问题”

五月 25, 2019

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

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

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 这样的停机程序。

posted in IT, Science by billzt

Follow comments via the RSS Feed | Leave a comment | Trackback URL

说点什么

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

  Subscribe  
提醒
 

Copyright © 2010-2019 | Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org