哥德尔三部曲
三个小程序,各自演示不完全性定理背后的一个事实。
要说明第一不完全性定理,三个事实就够了1:
- 程序能拿到自己的源码,不需要外部帮助。
- 图灵机可以被编码成一个一阶逻辑句子。
- 一阶逻辑的证明可以被搜索,也就是说证明是可识别的。
2023 年春天,我给每个事实写了一个小程序。
一 · self-lifter
它把你给的任意脚本改写成一个能打印自己源码的新脚本。下面是最短的那种:一个返回自己的 JavaScript 表达式。点一下运行,看看输出是不是和源码一字不差。
(function q(){return '('+q+')()'})()二 · Python2FOL
把一段 Python 程序编译成只用加法和乘法的一阶逻辑句子2。这个句子为真,当且仅当原程序会停机。
三 · lk-proof-machine
基于 Gentzen 的相继式演算(LK)自动搜索一阶逻辑证明。只要证明存在,它总能找到。
三块拼在一起,就是那个经典的自指论证:一个程序拿到自己的源码,把「我不会停机」写成算术句子,再去搜索这个句子的证明。
- 1这三个事实的说法来自仓库 README。 self-lifter,Python2FOL,lk-proof-machine.
- 2只用加法和乘法就够了,这正是算术强到足以谈论程序的地方。