簡単なチューリング・マシン

「P≠NP」問題 現代数学の超難問 (ブルーバックス)

の第二章のチューリング・マシンを、Ruby で実装してみました。

コードは以下です。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 に限りません。