圖靈機
把紙帶當作軌道(tape as tracks)
想像把你那單行的筆記格子畫成幾條水平車道,於是每格現在有上半與下半(或三列、或更多)。一條車道可以放原始資料,另一條放你對齊在正下方的草稿筆記。這就是軌道技巧:一種讓「一條」紙帶表現得彷彿有好幾條平行列、且讀寫頭一次全部讀到的方法。
這訣竅純粹是紙帶字母表的重新標記。要得到兩條軌道,你讓每個紙帶符號成為一個「對」,像 (a, X),意思是「這格上軌道是 a、下軌道是 X」。讀寫頭仍一次讀一格,但讀格子 (a, X) 會同時給它兩個軌道的值,而寫入則一次替換兩者。要三條軌道就用三元組,以此類推。由於字母表仍是有限的(你只是有更多複合符號),這不需要任何新機件:它仍然是一台再平常不過的單帶圖靈機,只是字母表更豐富。
軌道是一種主力設計技巧。第二條軌道是放計數器、標示讀寫頭「原點」位置的記號、或部分輸入之滾動副本的自然去處,全都與第一軌道上的資料保持步調一致的對齊。它與「真有好幾條獨立紙帶」密切相關卻更便宜:多帶機器有各自獨立的讀寫頭,而軌道共用一個讀寫頭、因此一起移動。誠實的說法:軌道不增加任何計算能力(一台樸素的單軌機器能做多軌機器能做的任何事),它們只是讓機器更容易設計與描述。
要檢查上下並排的兩個二進位數是否相等,把第一個數放上軌道、第二個數放下軌道,於是每格是個對,像 (1, 1) 或 (0, 1)。讀寫頭掃一遍,只在每格的兩個分量都相符時才接受。
兩條軌道 = 一條紙帶上的對符號,由一個讀寫頭一起讀寫。
軌道不過是用複合符號組織一條紙帶的方式;它們不增加能力。別把它們與多帶機器混淆,後者有好幾條獨立的紙帶與讀寫頭(同樣能力相當,只是更方便)。
又稱
另見