第(1/3)頁

    圖靈機并不是特指某一個或某一類機器，而是一種用數學的語言所定義出來的概念，是為了解答20世紀數學家對數學的終極追問而發明的一種工具。它的目的是為了對人類頭腦內復雜數學活動的抽象和簡化。

    定義圖靈機需要七個集合。其中最重要的兩個分別是“有限的非空狀態（state）的集合”與“有限的非空符號（symbol）的集合”。前者代表著“這臺機器能夠在紙帶上讀取和寫入的符號種類”，也被稱作“色數”。后者則代表“這機器內部可以出現的狀態”，被稱作“狀態數”——可以簡單的理解為“機器可以開一檔二檔”。

    余下五個則包括了“空白符號”、“初始的輸入符號”、“初始狀態”、“轉移函數集合”，以及特殊的“停機狀態”，即“機器進入該狀態之后就必須停機”。

    只要具備這七個要素，那么一臺機器就可以是圖靈機。

    實際上，偉大的數學家阿蘭·圖靈在創造這個概念的時候，并沒有設計出可以實際運行的機器。多年之后，馮·諾依曼才制造了一種基于電力的圖靈機工程實現。

    舉個例子，算盤被一根橫梁分作上下兩邊。上珠兩顆，通過靠梁與否，可以用來表現0~2三種符號。下珠五顆，通過靠梁與否，可以用來表現0~5六種狀態。算盤可以視作一種具有三色、六狀態的機器。

    這個時候，若是有數學家在紙上寫下了三色六狀態所對應的所有轉移函數，并訓練一個人（或猴子）嚴格按照轉移函數集合撥動算盤，那么這個算盤再加使用者，就可以視作“一個圖靈機”了。

    約格莫夫依稀記得，很多年前，他好像與向山做過類似的研究。將dna視作圖靈機的“紙帶”，dna的四種堿基對視作“符號的集合”，而將氨基酸視作“狀態”，核糖體與mrna則具備了“轉移函數集合”……

    地球真核生物的細胞核，或許是四色n狀態的圖靈機。

    而在眾多的圖靈機之中，有一種被稱作“海貍機”的玩意最為離譜。

    bb(n)，bb意為“busy    beaver”，忙碌的海貍。是一個在給定參數后，尋找可能產生的最大輸出的可終止程序。最簡單的二色二狀態海貍機，只有“開和關”兩種狀態，并且只能輸出“0或1”，且會在輸出1的時候停止。二色二狀態海貍機可以通過6次狀態轉換輸出4個1，因此bb（2）=6。

    bb（3）=21。

    bb(4)=107。
    第(1/3)頁