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

5.2

 非決定性チューリングマシン

147

試しに、先ほど見た

'aaabbbccc'

のような文字列を認識するためのチューリングマシンを構築し

てみましょう。

>>

rulebook = DTMRulebook.new([

#

状態

1: a

を探して右にスキャンする

TMRule.new(1, 'X', 1, 'X', :right), # X

をスキップする

TMRule.new(1, 'a', 2, 'X', :right), # a

を消して、状態

2

に進む

TMRule.new(1, '_', 6, '_', :left), #

空白を見つけて、状態

6

（受理状態）に進む

#

状態

2: b

を探して右にスキャンする

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

をスキップする

TMRule.new(2, 'X', 2, 'X', :right), # X

をスキップする

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

を消して、状態

3

に進む

#

状態

3: c

を探して右にスキャンする

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

をスキップする

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

をスキップする

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

を消して、状態

4

に進む

#

状態

4:

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

TMRule.new(4, ...