回覆列表
  • 1 # 使用者2709212030613

    普適圖靈機的概念。雖然其細節是複雜的,但是它背後的原則並不十分複雜。它的基本思想是把任意一臺圖靈機T的指令的表編碼成在磁帶上表示成0和1的串。然後這段磁帶被當作某一臺特殊的被稱作普適圖靈機U的輸入的開始部分,接著這臺機器正如T所要進行的那樣,作用於輸入的餘下部分。普適圖靈機是萬有的模仿者。“磁帶”的開始部分賦予該普適機器U需要用以準確模擬任何給定機器T的全部資訊!

    為了瞭解這是如何進行的,我們首先需要一種給圖靈機編號的系統方式。考慮定義某個特殊的,譬如講在前面描述的圖靈機的一個指令表。我們必須按照某種準確的方案把這表編碼成0和1的串。我們可藉助於以前採用的“收縮”步驟來辦到。因為,如果我們用數2,3,4,5和6來分別代表符號R、L、STOP、箭頭(→)以及逗點,那麼我們就可以用110、1110、11110、111110以及1111110的收縮把它們編碼。這樣,出現在該表中的這些符號實際的串可以採用分別被編碼成0和10的位數0和1。由於在該圖靈機的表中,在二進位計數的結尾大寫的數的位置足以把大寫的0和1從其他小寫的阿拉伯數字中區分開來,所以我們不需要用不同的記號。這樣,1101將被讀成二進位數1101,而在磁帶上被編碼成1010010。特別是,00讀作00,它可毫不含糊地被編碼成0,或者作為被完全省略的符號。實際上我們可以不必對任何箭頭或任何在它緊前頭的符號進行編碼,而依靠指令的數字順序去標明哪些符號必須是什麼。儘管在採用這個步驟時,在必要之處要提供一些額外的“啞”指令,以保證在這個順序中沒有縫隙。這樣的做法具有相當好的經濟性。(例如,圖靈機XN+1沒有告訴我們對1100要做什麼的命令,這是因為這條指令在機器執行時從不發生,所以我們應該插入一條“啞”指令,譬如講1100→00R,它可合併到表中而不改變任何東西。類似地,我們應該把101→00R插入到XN×2中去。)若沒有這些“啞的”,表中後面的指令的編碼就會被糟蹋了。因為在結尾處的符號L或R足以把一條指令和另一條隔開,所以我們在每一指令中實際不需要逗號。因此,我們採用下面的編碼:

    0表示0或0,10表示1或1,110表示R,1110表示L,11110表示stop。

    作為一個例子,讓我們為圖靈機XN+1編碼(插入指令1100→00R)。在去掉箭頭和在它們緊前面的位數以及逗號之後,我們得到

    00R 11R 00R 101R 110L 101R 01STOP

    1000L 1011L 1001L1100R101R00R1111R

    111R 1110R

    為了和早先說的相一致,我們可以去掉每一個00,並把每一個01簡單地用1來取代,這樣得到

    R11RR101R110L101R1STOP1000L1011L1

    001L1100R101RR1111R111R1110R

    如下是在磁帶上的相應的碼:

    11010101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100110

    我們總是可以把開始的110(以及它之前的無限的空白磁帶)刪去。由於它表示00R,這代表開頭的指令00→00R。而我已隱含地把它當作所有圖靈機共有的。這樣儀器可從磁帶記號左邊任意遠的地方向右跑到第一個記號為止。而且,由於所有圖靈機都應該把它們的描述用最後的110結束(因為它們所有都用R、L或STOP來結束),所以我們也可把它(以及假想跟在後面的0的無限序列)刪去。這可以算作兩個小節約。所得到的二進位數是該圖靈機的號碼,它在XN+1的情況下為:

    101011011010010110101001110100101101011110100001110100101011101000101110101000110100101101101010101011010101101010100。

    這一特殊的數在標準十進位記號下為

    450813704461563958982113775643437908。

    我們有時不嚴格地把號碼為n的圖靈機稱為第n臺圖靈機,並用Tn來表示。這樣,XN+1是第450813704461563958982113775643437908臺圖靈機!

    我們必須順著這圖靈機的“表”走這麼遠,才找到一臺甚至只進行如此平凡的(在擴充套件二進位記號上)對自然數加一的運算,這真使人印象深刻!(儘管在我的編碼中還可以有很少的改善餘地,但我認為自己進行得相當有效率。)實際存在某些更低號碼的有趣的圖靈機。例如,+1的二進位號碼為

    101011010111101010

    它只是十進位制的177642!這樣,只不過是把一個附加的1加到序列1的尾巴上的特別平凡的圖靈機+1是第177642臺圖靈機。為了好奇的原因,我們可以注意在任一種進位制中“乘二”是在圖靈機表中這兩個號碼之間的某處。我們找到XN×2的號碼為10389728107,而×2的號碼為1492923420919872026917547669。

    人們從這些號碼的大小,也許會毫不奇怪地發現,絕大多數的自然數根本不是可工作的圖靈機的號碼。現在我們根據這種編號把最先的十三臺圖靈機列出來:

    T0:00→00R,01→00R,

    T1:00→00R,01→00L,

    T2:00→00R,01→01R,

    T3:00→00R,01→00STOP,

    T4:00→00R,01→10R,

    T5:00→00R,01→01L,

    T6:00→00R,01→00R,10→00R,

    T7:00→00R,01→???,

    T8:00→00R,01→100R,

    T9:00→00R,01→10L,

    T10:00→00R,01→11R,

    T11:00→00R,01→01STOP,

    T12:00→00R,01→00R,10→00R。

    其中,T0簡單地就是向右移動並且抹去它所遇到的每一件東西,永不停止並永不往回退。機器T1最終得到同樣的效應。但它是以更笨拙的方法,在它抹去磁帶上的每個記號後再往後跳回。機器T2也和機器T0一樣無限地向右移動,但是它更有禮貌,簡單地讓磁帶上的每一件東西原封不動。由於它們中沒有一臺會停下,所以沒有一臺可以合格地被稱為圖靈機。T3是第一臺可敬的機器。它的確是在改變第一個(最左邊)的1為0後便謙虛地停止。

    T4遭遇了嚴重的問題。它在磁帶上找到第一個1後就進入了一個沒有列表的內態,所以它沒有下一步要做什麼的指令。T8、T9和T10遇到同樣的問題。T7的困難甚至更基本。把它編碼的0和1的串涉及到五個接續的1的序列:110111110。對於這種序列不存在任何解釋,所以只要它在磁帶上發現第一個1就被絆住。(我把T7或其他任何機器Tn,它的n的二進位展開包含多於四個1的序列稱為不是正確指明的。)機器T5、T6和T12遭遇到和T0、T1和T2類似的問題。它們簡單地、無限地、永遠不停地跑下去。所有T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是偽品!只有T3和T11是可工作的,但不是非常有趣的圖靈機。T11甚至比T3更謙虛,它在遇到1時就停止,並且沒有改變任何東西!

    我們應該注意到,在表中還有一個多餘。由於T6和T12從未進入內態1,機器T12和T6等同,並在行為上和T0等同。我們既不必為這個多餘,也不必為表中的圖靈機偽品而煩惱。人們的確可以改善編碼以擺脫許多偽品和大大減少重複。所有這些都是以使我們可憐的普適圖靈機變得更復雜作為代價。普適圖靈機必須把所讀到的號碼n解碼並假裝成圖靈機Tn。如果我們可以把所有偽品(或者多餘量)取走,這還是值得做的。但是,我們很快就會看到,這是不可能的!這樣,我們就不觸動我們的編碼好了。

    例如,可方便地把具有

    …0001101110010000…

    接續記號的磁帶解釋成某個數字的二進位表示。我們記得0在兩端會無限地繼續下去,但是隻有有限個1。我還假定1的數目為非零(也就是說至少有一個1)。我們可以選擇去讀在第一個和最後一個1(包括在內)之中的有限的符號串,在上述的情況是為一自然數的二進位寫法

    110111001,

    它在十進位表示中為441。然而,這一過程只能給我們奇數(其二進位表示以1結尾的數)。而我們要能表示所有的自然數。這樣,我們採取移走最後的1的簡單方案(這個1僅僅被當作表示這一程式的終止記號),而把餘下來的當成二進位數來讀5。因此,對於上述的例子,我們有二進位數

    11011100,

    它是十進位的220。這個步驟具有零也用磁帶上的記號代表的好處,也就是

    …0000001000000…

    我們考慮圖靈機Tn對我們從右邊提供給它的磁帶上(有限的)0和1的串的作用。根據上面給出的方案,可方便地把這串也考慮作某一個數,譬如m的二進位代表。我們假定,機器Tn在進行了一系列的步驟後最終到達停止(即到達STOP)。現在機器在左邊產生的二進位數串是該計算的答案。讓我們也以同樣方式把這當作,譬如是p的二進位代表來讀。我們把表達當第n臺圖靈機作用到m上時產生p的關係寫成:

    Tn(m)=p。

    現在,以稍微不同的方式看這一關係。我們把它認為是一種應用於一對數n和m以得到數p的一個特別運算。(這樣,若給定兩個數n和m,視第n臺圖靈機對m作用的結果而得出p。)這一特別運算是一個完全演算法的步驟。所以它可由一臺特殊的圖靈機U來執行。也就是說,U作用到一對(n,m)上產生p。由於機器U必須作用於n和m兩者以產生單獨結果p,我們需要某種把一對(n,m)編碼到一條磁帶上的方法。為此,我們可假定n以通常二進位記號寫出並緊接著以序列111110終結。(我們記得,任一臺正確指明的圖靈機的二進位數都是僅僅由0,10,110,1110和11110組成的序列,因此它不包含比四個1更多的序列。這樣,如果Tn是正確指明的機器,則111110的發生的確表明數n的描述已終結。)按照我們上面的規定,跟著它的每一件東西簡單地是代表m的磁帶(也就是,緊跟二進位數m的是1000…)。這樣,這第二個部分簡單地就是Tn假設要作用的磁帶。

    作為一個例子,如果我們取n=11和m=6當作U要作用的磁帶,其記號序列為

    …000101111111011010000…

    這是由以下組成的:

    …0000(開始的空白帶)

    1011(11的二進位表示)

    111110(終結n)

    110…(6的二進位表示)

    10000…(餘下的磁帶)。

    在Tn作用到m上的運算的每一接續的步驟,圖靈機U要做的是去考察n的表示式中的接續數位的結構,以使得在m的數位(也就是Tn的磁帶)上可進行適當的代換。在原則上(雖然在實踐中肯定很繁瑣)不難看到人們實際如何建造這樣的一臺機器。它本身的指令表會簡單地提供一種,在每一階段讀到被編碼到數n中的“表”中,應用到m給出的磁帶的位數時,合適元素的手段。肯定在m和n的數位之間要有許多前前後後的進退,其過程會極為緩慢。儘管如此,一定能提供出這臺機器的指令表,而我們把它稱為普適圖靈機。把該機器對一對數n和m的作用表為U(n,m),我們得到:

    U(n,m)=Tn(m)。

    這兒Tn是一臺正確指明的圖靈機6。當首先為U提供數n時,它準確地摸擬第n臺圖靈機!

    因為U為一臺圖靈機,它自身也必須有一號碼;也就是說,我們有

    U=Tu

    此處號碼u待定。u究竟是多少呢?事實上我們可以準確地給出u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498

  • 中秋節和大豐收的關聯?
  • 利比亞現在亂嗎?