- 作者: 野崎昭弘
- 出版社/メーカー: 講談社
- 発売日: 2015/09/18
- メディア: 新書
- この商品を含むブログ (1件) を見る
コードは以下です。pg は動作規則表(プログラム)、me はテープ(メモリ)です。変数 s は内部状態を表しています。テープは左方向(ヘッドは相対的に右に動く)には(メモリの足りる限り)どれだけでも移動しますが、開始位置より右に動くことはできません。
class Tm def initialize(pg) @pg = pg end def get(x, s) @pg.each do |li| next unless li[0] == s and li[1] == x return li[2..5] end puts "Syntax Error"; exit end def exe(me, pt=0) s = 0 p me begin x = me[pt] || 0 me[pt], s, mv, a = get(x, s) pt += mv; exit if pt < 0 p me end while a return me, pt end end pg = [[0, 0, 0, 0, 0, false], [0, 1, 0, 1, 1, true], [1, 0, 1, 1, 0, false], [1, 1, 0, 0, 1, true]] me = [1, 1, 1, 0] Tm.new(pg).exe(me)
結果(テープの状態)の遷移の例は以下のようです。このプログラムは、テープに左から 1 が偶数個並べばそのひとつ右に 0 を、奇数個並べば 1 を書き込むように出来ています。
[1, 1, 1, 0] s: 0 [0, 1, 1, 0] : 1 [0, 0, 1, 0] : 0 [0, 0, 0, 0] : 1 [0, 0, 0, 1] : 1
このプログラムは具体的には、テープの数字が 0 ならば停止、1 ならば続行して右に移動します。停止するときは、状態が 0 ならば 0 を、1 ならば 1 をテープに書き込みます。続行するときは、0 を書き込んでかつ状態が反転します。
なお、pg の配列の内容は
[状態s, 文字X, 文字Y, 次の状態, テープの移動方向, 続行するか否か]
です。プログラムの動作は、内部状態s とテープの数字X によって決まります。そのとき、数字Y がテープに書き込まれます。一般的には、使える数値は別に 0 または 1 に限りません。