盧赫：“什麼叫自動機？“

艾達否：“自動機就是對訊號序列進行判定的數學模型。我嘴裡的自動機特質有限狀態機，當這個機處於某種狀態時，它會讀到相應的訊號，根據轉移函式跳到下一個狀態，可以視作一臺沒有記憶體結構的計算機。

比如你現在餓了，那你就要去食堂，把晶瑩飽滿、粘糯有較勁、香到不可思議的新米飯一勺一勺填進嘴裡，直到胃被塞滿。飢餓感是訊號，餓了要吃飯是狀態，去食堂是轉移函式，飽是執行完轉移函式之後的新狀態。

你每時每刻都在處理各種各樣的狀態，直到停機，或者說死掉。”

盧赫：“那什麼叫圖靈完備？”

艾達否：“能模擬圖靈機的自動機稱作圖靈完備。”

盧赫：“什麼叫圖靈機？”

艾達否：“一個可以執行任何演算法的簡單模型。它有一個無限長的紙帶，紙帶被分成一個個相鄰的格子，每個格子都可以寫上至多一個字元；它還有一個讀寫頭，可以讀取、擦除、寫入當前格子的內容，也可以每次向左或向右移動一個格子；它有一個字元表，包含紙帶上可能出現的所有字元；

它還要有一個狀態暫存器，追蹤每一步計算過程機器所處的狀態直到停機；它還可以包含一個指令集，用來指定讀寫頭的行為，比如你告訴讀寫頭：當你身處編號53的格子並看到其內容為0時，擦除，改寫為1，並向右移一格。此外，令下一狀態為執行。

舉個栗子，如果它的字符集只包含0、1和空白，那麼它就是一個包含3個訊號的圖靈機。如果它的紙帶上寫了個110，那麼你可以讓它執行一系列的指令執行位反轉演算法，把110改寫成001。比如：指標遇0寫入1紙帶右移，遇1寫入0紙帶右移。

那你要問了，如果指標遇到空字元呢？

你沒有告訴它遇到空字元怎麼做，所以它只會不斷讀取空字元，但不操作。這個時候你可以給它加一個狀態指令：遇到空字元就停機，它就可以完美執行你的位反演算法。它現在可以被視為一個包含3個訊號和1個狀態的有限狀態機。

如果你吃飽了撐著沒事幹，想要把它設計得複雜一些，比如想讓它一做完位反轉運算就復原，把110變成001後再復原成110。那麼你給它兩個狀態：當讀寫頭在向右移動的過程中讀到空字元時，改為向左移動；當讀寫頭在向左移動的過程中遇到空字元時，停機。這是一個包含3個訊號和2個狀態的有限狀態機.。

只要你給它新增足夠多的狀態，並把這個假想模型物理實現，就能夠讓它執行一切複雜演算法，只要這個演算法是可計算的。”

盧赫：“你在這裡做了限定，只能執行可計算的演算法。”

艾達否：“沒錯，它只能解決可計算的問題。你可以給它一個正整數 n，讓它判斷n是否是質數，但不能問它今天中午食堂會有什麼飯。你可以給它一個邏輯蘊含的命題，要求它求出逆否命題，但不能包含悖論，比如理髮師給並且只給那些不給自己理髮的人理髮，那他給不給自己理髮？”

盧赫：“這麼簡單的結構，對於複雜演算法它是如何算的呢？”

艾達否：“它算起來也很簡單。三種基本函式：零函式、後繼函式、投影函式，外加三種基本操作：函式組合、原始函式遞迴以及極小化，就能夠解決一切可計算問題[1]。”

盧赫：“……我換個我能聽懂的問題吧，怎樣判斷一個語言是圖靈完備的？”

艾達否：“如果一個語言能夠實現上述的三種基本函式和基本操作，並且能夠據此實現偏遞迴函式，那麼它就是圖靈完備的。”

盧赫：“為什麼這麼說？”

艾達否：“因為只有能實現偏遞迴，才能夠實