证明每个程序都终止

主要观点:计算机科学中著名难题之一是停机问题,通常认为无法编写一个程序能对任意输入程序正确判断其是否终止,但通过引入“妻子总是对的”这一假设,用逻辑推理得出所有程序最终都会终止的结论,然而这是错误的,因为基于矛盾假设构建的系统会导致证明出任何事情,最后呼吁若想成为更有效的软件工程师可考虑其 coaching 服务。
关键信息:

  • 定义所有程序的集合为P,用h(p)表示程序p是否最终终止,先假设所有程序最终都终止即h(p)=true
  • 给出两个关于是否适合吹萨克斯风的事实,分别代表A!A
  • 依据“妻子总是对的”这一假设,得出A!A都为真,进而推出H(所有程序最终都会终止)为真。
    重要细节:
  • 提到将完整正式证明留到明年提交给某知名会议,且引用了一些参考文献说明相关内容。
  • 最后强调该逻辑推理只是个玩笑,真正的结论是因反证法可知妻子不总是对的,并推荐了 Hillel Wayne 的《Logic for Programmers》,同时宣传了自己的 coaching 服务。
阅读 11
0 条评论