Turing Machine Simulator

tm.rb

#!/usr/bin/env ruby

class TM
  BLANK = :blank
  MOVE_LEFT = :left
  MOVE_RIGHT = :right
  HALT = :halt

  attr_reader :pos, :state

  def initialize
    @rules = {} # { state: { char: [next_state, write_char, move] } }
    @tape = Array.new(1000, BLANK)
    reset_state!
  end

  def reset_state!
    @pos = 0
    @state = :q_0
  end

  def step
    next_state, write_char, move = @rules.dig(@state, @tape[@pos])

    unless next_state
      raise "No rule found state: :#{@state}, char: #{@tape[@pos]}" 
    end

    @tape[@pos] = write_char
    @state = next_state
    @pos += case move
      when :left  then -1
      when :right then 1
      when :halt  then 0
      end

    { state: @state, pos: @pos, tape: @tape.clone }
  end

  def tape
    @tape
      .rotate(100)
      .drop_while{|x| x == BLANK }
      .reverse
      .drop_while{|x| x == BLANK }
      .reverse
      .map {|x| x == :blank ? " " : x }
  end

  def tape=(new_tape)
    new_tape = new_tape.chars if new_tape.is_a? String
    @tape = (new_tape + Array.new(1000, BLANK))[0...1000]
  end

  def inspect
    "state: :#{@state}, pos: #{@pos}, tape: \"#{tape.join}\""
  end

  def to_s
    inspect
  end

  def add_rule(state, char, move, next_state = nil, write_char = nil)
    next_state = state unless next_state
    write_char = char unless write_char
    
    @rules[state] ||= {}
    @rules[state][char] = [next_state, write_char, move]
  end
end

tm = TM.new

tm.add_rule(:q_0, "1",    :right)
tm.add_rule(:q_0, "0",    :right)
tm.add_rule(:q_0, "+",    :right)
tm.add_rule(:q_0, :blank, :left, :q_b)

tm.add_rule(:q_b,     "0",    :left, :q_f, "1")
tm.add_rule(:q_b,     "1",    :left, :q_c, "0")

tm.add_rule(:q_c,     "0",    :left)
tm.add_rule(:q_c,     "1",    :left)
tm.add_rule(:q_c,     "+",    :left, :q_d)

tm.add_rule(:q_d,     "0",    :right, :q_0, "1")
tm.add_rule(:q_d,     "1",    :left,  :q_e, "0")

tm.add_rule(:q_e,     "1",    :left,  :q_e, "0")
tm.add_rule(:q_e,     "0",    :right, :q_0, "1")
tm.add_rule(:q_e,     :blank, :right, :q_0, "1")

tm.add_rule(:q_f,     "0",    :left,  :q_f, "1")
tm.add_rule(:q_f,     "1",    :left,  :q_c, "0")
tm.add_rule(:q_f,     "+",    :right, :q_g, :blank)

tm.add_rule(:q_g,     "0",    :right, :q_g, :blank)
tm.add_rule(:q_g,     "1",    :right, :q_g, :blank)
tm.add_rule(:q_g,     :blank, :right, :finished)

tm.tape = "101+011"
puts tm

until tm.state == :finished
  tm.step
  puts tm
end

puts

# 101 + 00

tm.reset_state!
tm.tape = "101+00"
puts tm

until tm.state == :finished
  tm.step
  puts tm
end

puts

# 11+11

tm.reset_state!
tm.tape = "11+11"
puts tm

until tm.state == :finished
  tm.step
  puts tm
end

puts

# 0+11

tm.reset_state!
tm.tape = "0+11"
puts tm

until tm.state == :finished
  tm.step
  puts tm
end