tkykmw code

学びたいことを学ぶ

アンダースタンディング コンピュテーション 5章

5章。DFAからプッシュダウンオートマトンを経て、ついにチューリングマシンへ到達。

ここまで来ると、かなり自由な発想で規則を設計できるようになり、なるほど普通のプログラミング言語と通底する存在だとうなずける。

たとえば156ページで紹介されている、1と0による文字のエンコードは、チューリングマシンの規則として実装可能だ。

f:id:tkykmw:20180818210601p:plain

ここで注目すべき点として、ある文字のエンコード規則は、一つ前の文字のエンコード規則を流用できる。

たとえばbのエンコードは、'1' + 'aのエンコード結果' になっている。bとcの関係も全く同じ。この法則を利用すれば、エンコードできる文字を一つ増やすのに、状態を一つ増やすだけでいい。

と、いうようなチューニングも、作っているうちに、自然に実行できてしまった。まさにプログラミングだ。

こういった調子で、「チューリングマシンの規則を、汎用チューリングマシンが読める形式にエンコードするチューリングマシン」が作れたとしたら、それを使って自分自身をエンコードしてしまえば、もはや汎用チューリングマシン一つですべてが完結する。

万能性万歳。