背景

之前讀了 Martin Davis 的《Computability and Unsolvability》，決定對其中的圖靈機和遞歸函數等價性證明做一個（不嚴謹的）整理，證明方法比較有趣，雖然最終結果并沒有太大的驚喜。

整理本身的目標是拋開晦澀難懂的數學符號，從結合實際的角度給一個概念上的說明，以此希望自己下次回顧的時候不會完全看不懂。

更方便討論的圖靈機

馮諾依曼體系結構可以看作是圖靈機的一個具體實現，同時增加了對圖靈機上一些基本操作的封裝，比如說，圖靈機包括一條無限長的被分成一個單元格的紙帶，單元格上可以標記 0 或 1，這個紙帶就可以對應到計算機內存，這個紙帶上最開始的內容就可以看作輸入，最終內容可以看作輸出，圖靈機中在具體某個狀態(tài)下看到紙帶當前單元格上的內容執(zhí)行左移右移或者修改紙帶內容的操作并跳轉到某個狀態(tài)即對應為在內存上讀出某個數據，執(zhí)行某種計算，寫回計算結果，并跳轉到新的指令地址的操作。而程序指令集增加的操作可以看作對圖靈機一系列操作的封裝，并不增加計算能力。

而面向過程的高級語言比如 C 語言又很好的反應了馮諾依曼體系結構的特點，比如變量對應到內存，語句對應到指令，同時有各種循環(huán)結構或者直接通過 goto 進行語句間的跳轉。所以同樣可以比較簡單的把這樣的高級語言看作是和圖靈機等價的。所以后面會直接在高級語言的基礎上進行討論。

遞歸函數以及遞歸函數到圖靈機的等價性

而遞歸函數的數學表達比較簡單，并且看上去比較規(guī)則。不嚴格的說，遞歸函數表示的是任意可計算函數都可以通過對一些基本函數進行組合而成。基本函數的一些例子

def s(x): return x + 1 def n(x): return 0

而組合的方式一共包括以下三種

# 組合，對任意 h a b 函數 def c(x):return h(a(x), b(x))# 遞歸，對任意 g h def r(x, y):return x == 0 ? g(y): h(x, y, f(x - 1, y))# 最小化，對任意 g def m(x):i = 0while g(i, x): i += 1return i

所以既然基本函數和組合函數都能很容易的寫成面向過程的代碼，潛在的就表示遞歸函數可以很方便的改寫成圖靈機，所以所有的遞歸函數都可以用圖靈機計算。

圖靈機到遞歸函數的等價性

所以證明的另一半就是證明所有的圖靈機都是遞歸函數，也是比較有趣的部分。

證明的基本方法是編碼整個圖靈機的運算過程，然后枚舉所有計算過程直到找到一個計算過程滿足程序執(zhí)行過程和程序要求并最終退出，然后從中得到計算結果。

比如說，對以下過程

def f(x):i = 0# 語句 0while i != 2: i += 1# 語句 1return i

要對整個執(zhí)行過程進行編碼，對狀態(tài) <s, v> 表示為在語句 s 時 i 的值為 v，則初始狀態(tài)為 <0, 0>，最終結束狀態(tài)為 <1, 2>，對整個執(zhí)行過程，最終要找到 <0, 0>, <0, 1>, <0, 2>, <1, 2>。

所以對應的遞歸函數最外層會類似于

def f(x):for e in [[(0, 0)], [(0, 1)], [(1, 0)], [(1, 1)], [(0, 0), (0, 0)], [(0, 0), (0, 1)], # 無窮多的狀態(tài)序列...]:# 符合初始狀態(tài)if e[0] == (0, 0) # 符合結束狀態(tài)and e[-1] == (0, 2)# 對狀態(tài)序列中的每一個狀態(tài)，# 都能得到下一個狀態(tài)and all([ yields(e[i], e[i + 1]) for i in range(len(e) - 1)])return e[-1][1]

將執(zhí)行過程進行兩遍的哥德爾編碼，即先對每個狀態(tài)進行哥德爾編碼，再對整個狀態(tài)序列進行編碼，我們就會在最上層得到一個調用了最小化函數的組合函數

def f(x): # 組合函數return gl(1, gl(ln(g(x)) - 1, i))def g(x): # 最小化函數i = 0while not t(i): i += 1return i

其中 gl(x, y) 是從哥德爾編碼中 y 中得到第 x 位的值。ln 返回哥德爾編碼對應的序列長度，而 t 函數

def t(x):return valid(x) # 符合初始狀態(tài)and gl(0, x) == gn(0, 0) # 符合結束狀態(tài)and gl(ln(x) - 1, x) == gn(0, 2) # 對狀態(tài)序列中的每一個狀態(tài)，# 都能得到下一個狀態(tài)and all ([ yields(gl(i, x), gl(i + 1, x)) for i in range(ln(x) - 1)])

其中 valid 測試是否為合法的兩遍哥德爾編碼結果，gn 是哥德爾編碼函數。而 yields 函數描述了合法的程序狀態(tài)轉換

def yields(x, y):# if i != 2: i += 1return (gl(0, x) == 0 and gl(1, x) != 2 and gl(0, y) == 0 and gl(1, y) == s(gl(1, x)))# else: breakor (gl(0, x) == 0 and gl(1, x) == 2 and gl(0, y) == 1 and gl(1, y) == 2)

其中的子函數都可以由遞歸函數規(guī)則生成，舉其中一個簡化了的例子

def f(x, y):return x != 2 and y == 0

等價于

def f(x, y):return (not abs(x - 2)) + abs(y) == 0

其中加法可以表示為

def plus(x, y):return x == 0 ? y: 1 + plus(x - 1, y)

而沒有的驚喜在于整個證明過程并不能有效的找出圖靈機中潛在的函數調用結構。嚴格證明可參考《Computability and Unsolvability》。

停機問題

所以從遞歸函數的角度看，停機問題其實只存在于最小化函數，而其它函數都是保證退出的，而其實對于整個圖靈機到遞歸函數的證明也只在最后一步使用了最小化函數。

總結

以上是生活随笔為你收集整理的函数的凹凸性证明_理解图灵机和递归函数的等价性证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。