用 Kleene 遞歸定理構造輸出自己的 Python 程序

嗯我們來看一下這個定理吧，在 Introduction to Metamathematics 第 352 - 353 頁（順便說一下，這裡貼的圖片是網上下的電子書，如果有版權問題請來找我，我抄一遍再貼。。。），原來的定理是用遞歸函數的語言來講的，為了方便我還是用 Python 的語言來講吧。n > 0，對任何一個 Python 函數 psi(z, x1, ..., xn)，那麼可以找到一個字元串 e Pythonic-地定義 psi，即使得 eval(e)(x1, ..., xn) 和 psi(e, x1, ..., xn) 是等價的。（即對於相同的輸入 x1, ..., xn，如果一邊死循環另外一邊也死循環，如果一邊能算出來結果，那麼另外一邊會算出來相同的結果，如果一邊出錯，另一邊會出相同的錯）

呃我解釋一下我所謂的 Pythonic-地定義。講計算理論的話我們得有計算模型，計算模型裡面自然會有程序，程序自然要處理數據。為了讓世界更有趣，我們需要讓程序也可以處理程序（前幾年很火的 metaprogramming？），這樣就需要把程序表示成為數據。比如說我們用 Python 的時候，Python 是個計算模型啊，裡面可以寫 Python 程序，為了讓程序可以處理程序，我們需要把程序表示成數據，嗯因為前人已經做了大量工作（CPU，Python 解釋器什麼的）我們這個表示非常容易：把 Python 程序表示成它的代碼就好了。當然還有其它的表示方法，比如 AST 什麼的。。。當然有些計算模型用字元串來表示程序並不是最方便的，比如 Lisp，Lisp 裡面明明是用 list 表示程序更容易嘛，car cdr 什麼的改起程序來還是比字元串處理容易得多的，儘管你要是想手寫字元串處理也沒人攔著。當年 Kleene 研究計算的時候人們還沒有什麼計算機呀語言啊之類的東西呢，人們用的計算模型是圖靈機啊，lambda 演算啊，遞歸函數啊這些東西，這些計算模型要討論自我指涉的問題都需要表示模型里的程序。圖靈機的程序就是圖靈機的程序，表示方法是構造一個通用圖靈機出來然後用通用圖靈機的輸入來表示；lambda 演算和遞歸函數裡面的程序是 lambda 函數和部分遞歸函數，它們都用 G?del 配數來表示它們的程序。Kleene 的書里用遞歸函數和 G?del 配數來講問題的，所以裡面講 e （一個自然數）recursive 定義了一個（部分遞歸）函數 f 的時候意思是 f 的 G?del 配數是 e；我也模仿他說話好了，e （一個字元串）Pythonic-地定義了一個函數 f 的時候意思是 f 的 Python 源代碼是 e。順便說一下，遞歸函數裡面函數的參數都是自然數，我們說的函數嘛，可以往裡面傳任何 Python 基本類型值。（呃敲完才發現這段話啰哩啰嗦寫了這麼長，不過我還是覺得這些模型都等價是個了不起的事兒，我想了半天怎麼不開掛造個比它們更強的計算機都沒想出來）

證明需要用到一個叫 Smn 定理的引理，在第 342 頁。定理說對所有 m, n >= 0，存在一個 Python 函數 Smn(z, y1, ..., ym) 使得，如果 e （是一個字元串） Pythonic-地定義了一個關於 y1, ..., ym, x1, ..., xn 的 m + n 元函數 phi(y1, ..., ym, x1, ..., xn)，那麼對給定的 m 個東西 y1, ..., ym，Smn(e, y1, ..., ym) （又是一個字元串） Pythonic-地定義了一個關於剩下 x1, ..., xn 這 n 個變數的函數 phi(y1, ..., ym, x1, ..., xn)。呃這玩意兒看起來就是所謂的 Currying 嘛，把一個函數部分參數固定了得到一個新的函數。。。嗯然後這個引理怎麼證明呢，把函數寫出來就行了唄～學過 Python 的人都會：

def S11(z, y1): return "lambda x1: (%s)((%s), x1)" % (z, y1)def S10(z, y1): return "lambda : (%s)(%s)" % (z, y1)

嗯我只寫 S11 和 S10 好了，Smn 依次類推。順便說一下，在遞歸函數和 G?del 配數的模型里，這個定理也是構造出來的。

然後可以來證原來的定理了，為了方便我們設 n=1 吧，我們再來看一下要證的東西：對 psi(z, x1)，要找到 e 讓 eval(e)(x1) 和 psi(e, x1) 等價。考慮函數 psi(S11(y, y), x1) （來解釋一下，這是一個關於 y 和 x1 的函數，把 S11(y, y) 算出來當第一個參數，x1 當第二個參數傳進 psi 求值），令 f Pythonic-地定義 psi(S11(y, y), x1)（就是說 f 是 psi(S11(y, y), x1) 的源代碼），令 e=S11(f, f)，然後我們回顧一下 S11 的定義，S11 的第一個參數是一個函數的源代碼，第二個參數是給這個函數第一個參數取的值，我們這裡第一個參數 f 對應的函數就是 psi(S11(y, y), x1)，把第一個參數取值 f 以後就是 psi(S11(f, f), x1)，e 是它的源代碼，這樣 eval(e) 就是一個關於 x1 的函數，它和 psi(S11(f, f), x1) 等價。

定理是構造性的，讓我們把構造的過程拿 Python 寫出來，為了下面用我們這裡設 n=0：

def get_e(psi): f = "lambda y: (%s)(%s)" % (psi, "S10(y, y)") e = S10(f, f) return e

然後我們怎麼構造一個輸出自己的程序呢？嗯對 psi 取特殊值恆同就行了：

psi = """lambda x: x"""

把上面的所有東西加起來：

def S10(z, y1): return "lambda : (%s)(%r)" % (z, y1)def get_e(psi): f = "lambda y: (%s)(%s)" % (psi, "S10(y, y)") e = S10(f, f) return epsi = "lambda x: x"print(get_e(psi))print(eval(get_e(psi))())print(eval(psi)(get_e(psi)))

存成 kleene.py，然後運行：

$ python3 kleene.pylambda : (lambda y: (lambda x: x)(S10(y, y)))("lambda y: (lambda x: x)(S10(y, y))")lambda : (lambda y: (lambda x: x)(S10(y, y)))("lambda y: (lambda x: x)(S10(y, y))")lambda : (lambda y: (lambda x: x)(S10(y, y)))("lambda y: (lambda x: x)(S10(y, y))")

咦，確實我們發現上面每一行的東西都是一樣的，它們都是我們所謂的 e，運行結果確實滿足 eval(e)() = psi(e) = e（注意到我們的 psi 就取的是恆同），好棒呀。

嗯不過還是不太滿意，比如說我們 eval 的時候必須在剛才的環境裡面 eval，因為 S10 函數的緣故。不過這個好辦，我們手工把 S10 「內聯」進去就行了。

e = """lambda : (lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y)))("lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y))")"""psi = "lambda x: x"print(e)print(eval(e)())print(eval(psi)(e))

存成 kleene1.py，運行一下：

$ python3 kleene1.pylambda : (lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y)))("lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y))")lambda : (lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y)))("lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y))")lambda : (lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y)))("lambda y: (lambda x: x)("lambda : (%s)(%r)" % (y, y))")

不錯問題解決了。

還有個問題是我想要的是一個輸出自己的程序，你這裡只給出了一個返回自己的函數，有本質區別呀。。。嗯這是一個問題，因為對於遞歸函數，輸入和輸出非常明確，輸入就是函數自變數，輸出就是函數值，但是對於 Python 程序，輸入和輸出比較複雜，你可以規定各種各樣形式的輸入和輸出，比如把函數自變數叫輸入，函數值叫輸出，當然也可以把 stdin 叫輸入，stdout 叫輸出，當然最重要的就是可以把不同程序的輸入輸出連起來。嗯更多的事情我也沒想清楚，所以還是 hack 一下吧。。。hack 的辦法是改 psi 函數，把 psi 函數改成不僅能返回輸入，還能在返回輸入的時候順便輸出一下輸入就好了，順便兒輸出的時候還能調用一下自己。。。

psi = "lambda x: print(x), x"

誒但是我發現不對勁兒，Python 裡面沒有逗號運算符，還得自己搞個逗號運算符出來：

psi = "lambda x: (print("("+x+")()"), x)[-1]"

試試

def S10(z, y1): return "lambda : (%s)(%r)" % (z, y1)def get_e(psi): f = "lambda y: (%s)(%s)" % (psi, "S10(y, y)") e = S10(f, f) return epsi = "lambda x: (print("("+x+")()"), x)[-1]"eval(get_e(psi))()

$ python3 kleene.py(lambda : (lambda y: (lambda x: (print("("+x+")()"), x)[-1])(S10(y, y)))("lambda y: (lambda x: (print("("+x+")()"), x)[-1])(S10(y, y))"))()

把 S10 內聯進去，存成 kleene2.py：

(lambda : (lambda y: (lambda x: (print("("+x+")()"), x)[-1])("lambda : (%s)(%r)" % (y, y)))("lambda y: (lambda x: (print("("+x+")()"), x)[-1])("lambda : (%s)(%r)" % (y, y))"))()

然後運行一下發現它確實輸出自己。。。這就好了。。。

嗯寫完了以後發現整個構造過程裡面最難的是獲得一個函數的源代碼。。。當我們用 Python 不好做的時候只能手工「內聯」了（只要這個源代碼理論上存在倒也沒啥大影響）。。。以及，我在想我們這裡面大量運用 lambda，那 C 語言怎麼干這個事兒？畢竟 Python 很容易和遞歸函數類比，C 語言想要和遞歸函數類比還需要研究一番。最後，我想 Kleene 定理給我們的啟示就是我們不僅可以寫一個輸出自己的程序，還可以讓這個程序在輸出自己的同時做任何奇奇怪怪的事情，這還是非常有意義的。至於對更廣泛的語言直接應用 Kleene 定理嘛我不抱太大希望。。。話說回來，Kleene 定理我覺得意義最主要就是證明了對遞歸函數這個模型可以干一些事情，類似的事情在其他語言中應該也是可以乾的，至於怎麼干，技術細節和遞歸函數可能差非常遠然後嘛，我們平時做的構造輸出自己的程序（沒有理論指導拍腦門式的）其實可以看作對那種語言證明某個不動點定理，通過那個不動點應該很容易推導出來那種語言對應的 Kleene 定理吧。。。

所以你看也不能說構造一個奇葩的遞歸函數就叫計算理論，構造一個奇葩的程序就叫計算實踐，兩件事的意義其實差不多。話說我之前一直在想把整個計算理論用 Python 寫一遍，為此還看過不少計算理論書的目錄，好像 Hopcroft 的 Introduction to Automata Theory, Languages, and Computation 一直以來為廣大人民群眾所喜聞樂見，不過這本書有 Ruby 版的，而且內容和 Kleene 那本書比有點淺感覺。。。然後又不小心看了一本忘了叫啥的比較新的講計算理論的書一開始就說計算模型並不重要。。。就不想用 Python 寫了。。。話說回來在討論可不可計算的時候用 Python 挺好用的，但是討論複雜度的時候 Python 挺麻煩的，誰知道一句 Python 裡面有多少複雜度呢？而且 Python 的語法太複雜了，需要定義的地方不少。從 Python 虛擬機位元組碼也許定義複雜度好一點，但是虛擬機位元組碼太複雜了不是所有學 Python 的人都需要掌握的。從程序運行時間的漸進的界來定義也好一點，但是要估計這個東西甚至還得討論 CPU，更麻煩了。。。所以還是好好寫程序吧。。。