Jong Luo
EN
← 回到时间线

· 写作 · 待整理

哥德尔三部曲

三个小程序,各自演示不完全性定理背后的一个事实。

要说明第一不完全性定理,三个事实就够了1:

  1. 程序能拿到自己的源码,不需要外部帮助。
  2. 图灵机可以被编码成一个一阶逻辑句子。
  3. 一阶逻辑的证明可以被搜索,也就是说证明是可识别的。

2023 年春天,我给每个事实写了一个小程序。

一 · self-lifter

它把你给的任意脚本改写成一个能打印自己源码的新脚本。下面是最短的那种:一个返回自己的 JavaScript 表达式。点一下运行,看看输出是不是和源码一字不差。

(function q(){return '('+q+')()'})()

二 · Python2FOL

把一段 Python 程序编译成只用加法和乘法的一阶逻辑句子2。这个句子为真,当且仅当原程序会停机。

三 · lk-proof-machine

基于 Gentzen 的相继式演算(LK)自动搜索一阶逻辑证明。只要证明存在,它总能找到。

三块拼在一起,就是那个经典的自指论证:一个程序拿到自己的源码,把「我不会停机」写成算术句子,再去搜索这个句子的证明。

  1. 1这三个事实的说法来自仓库 README。 self-lifter,Python2FOL,lk-proof-machine.
  2. 2只用加法和乘法就够了,这正是算术强到足以谈论程序的地方。