アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

5.3

 最大の能力

151

#

状態

3:

文字列の末尾を探して右にスキャンする（

b

を覚えている）

TMRule.new(3, 'a', 3, 'a', :right), # a

をスキップする

TMRule.new(3, 'b', 3, 'b', :right), # b

をスキップする

TMRule.new(3, 'c', 3, 'c', :right), # c

をスキップする

TMRule.new(3, '_', 5, 'b', :right), #

空白を見つけて、

b

を書く

#

状態

4:

文字列の末尾を探して右にスキャンする（

c

を覚えている）

TMRule.new(4, 'a', 4, 'a', :right), # a

をスキップする

TMRule.new(4, 'b', 4, 'b', :right), # b

をスキップする

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

をスキップする

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

空白を見つけて、

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 ...