深入理解運算原理｜從簡單的機器到無所不能的程式

158

|

第 5 章

TMRule.new(4, 'c', 4, 'c', :right), # skip c

TMRule.new(4, '_', 5, 'c', :right) # find blank, write c

])

=> #<struct DTMRulebook rules=[…]>

>> tape = Tape.new([], 'b', ['c', 'b', 'c', 'a'], '_')

=> #<Tape (b)cbca>

>> dtm = DTM.new(TMConfiguration.new(1, tape), [5], rulebook)

=> #<struct DTM …>

>> dtm.run; dtm.current_configuration.tape

=> #<Tape bcbcab(_)>

這部機器的狀態 2、3、4 幾乎完全相同，不同之處在於它們各個都代表一部記住與字串

開頭不同字元的機器，而在此例，當它們抵達結尾時，它們全部都會完全一些不同的事

情。

這部機器只能處理由字元

a

、

b

、

c

組成的字串；如果我們希望它能處理包

含

任何

字母字元的字串（或字母和數字字元，或任何長於我們選擇的更

大集合），我們就必須加入大量的狀態（可能需要記住其中的每個字元）

和大量的規則，才能處理更多的字元。

以這種方式利用目前的狀態，可以在使用大量的狀態作為代價的情況下，在磁帶頭來回

移動、將等同於機器明確擁有『暫存器』作為內部儲存的能力有效提供給我們的同時，

允許我們設計出可以記住任何有限組合行為的圖靈機。 ...