Skip to main content

__debug's Home There is no remedy for love but to love more

Recursion theorem explained in Python

试着用 Python 来解释计算理论中的 Recursion theorem:

D = (lambda m: '%s(%r)' % (m, m))
f = D('(lambda m: D(m))')
assert f == eval(f)

f == eval(f)?

先来看一份神奇的代码:

D = (lambda m: '%s(%r)' % (m, m))
f = D('(lambda m: D(m))')
print(f)
print(eval(f))

这份代码的输出是

(lambda m: D(m))('(lambda m: D(m))')
(lambda m: D(m))('(lambda m: D(m))')

也就是说, f 是一个字符串, 对这个字符串求值得到的结果仍然是 F 自己.

再来看另一份代码:

D = (lambda m: 'eval(%s(%r))' % (m, m))
T = repr
v = "(lambda m: T(D(m)))"
f = D(v)
print(eval(f))
print(eval(T(f)))

输出是:

eval((lambda m: T(D(m)))('(lambda m: T(D(m)))'))
eval((lambda m: T(D(m)))('(lambda m: T(D(m)))'))

这两份代码本质上是一样的, 因为在 Python 中 eval(repr(x)) == x. 它们背后的原理其实就是计算理论中的 Recursion theorem.

Recursion theorem

由于所有图灵机组成的集合是可数的, 我们可以给任意一个图灵机 \(M\) 一个自然数编号 \(\langle M \rangle\).

定理: 令 \(t: \mathbb{N} \to \mathbb{N}\) 是一个递归函数(可以理解为"可计算函数"), 存在一个图灵机 \(F\) 满足 \(t(\langle F \rangle)\) 是某个与 \(F\) 等价的图灵机的编号.

我们用 Python 解释一下这个定理.

为了方便叙述, 我们将这里的"图灵机 \(F\)"简化为"没有输入的图灵机 \(F\)", 于是 \(F\) 可以被看作是一个 Python 表达式. 有没有输入对原定理的证明并没有太大的影响.

由于我们不方便给每个 Python 表达式一个自然数编号, 可以用这个表达式的字符串作为它的编号, 也就是 repr(x). Python 版的 Recursion theorem 如下:

定理:T(m) 为一个函数, 参数 m 为一个包含表达式的字符串, 其返回值 T(m) 也是一个包含表达式的字符串. 存在一个表达式 F 使得

F == eval(T(repr(F)))

证明: (大写字母表示函数或表达式, 小写字母表示对应的字符串)

D = (lambda m: 'eval(%s(%r))' % (m, m))
T = (lambda m: repr(expression_of_m))
v = "(lambda m: T(D(m)))"
f = D(v)
assert eval(f) == eval(T(f))

对于任意一个 expression_of_m, 都有 eval(f) == eval(T(f)), 因为:

  eval(f)
= eval(D(v))
= eval(V(v))
= eval(T(D(v)))
= eval(T(f))

其实这个证明本质上就是 Diagonalization: (引用自段老师的课件) nil

其它

用这个思路还可以构造出一些有意思的 Python 表达式/函数, 大家可以自己玩一玩.

比如说实现经典的 Quine; 再比如说实现一个能产生自己的函数, 也就是说 F() 等价于 F()() 等价于 F()()()

本文的内容用 Lisp 来叙述感觉会更合适, 可惜我自己也不太会 Lisp.

Comments

Comments powered by Disqus