turing.rb

class Tape
  def initialize
    @array = [0]
    @head = 0
  end
  
  attr_accessor :array, :head
  
  def read
    @array[@head]
  end
  
  def write(x)
    @array[@head] = x
  end
  
  def moveleft
    if @head == 0
      @array.unshift 0
    else
      @head -= 1
    end
  end
  
  def movewrite
    @head += 1
    if @array.size == @head
      @array[@head] = 0
    end
  end
  
  def inspect
    @array.join("").insert(@head, ">")
  end
end

L = 2
R = 3

class TuringMachine
  def initialize(program)
    @tape = Tape.new
    state = 0
    @program = program_tohash(program)
  end
  
  def program_tohash(program)
    hash = {}
    program.each do |(qi, s, a, qj)|
      hash[[qi, s]] = [a, qj]
    end
    hash
  end
  
  def run(*n)
    state = 0
    input n
    while true
      (action, newstate) = @program[[state, @tape.read()]]
      break if action == nil
      state = newstate
      doaction action
      #puts "#{state} #{@tape.inspect}"
      #sleep 0.1
    end
    output
  end
  
  def input(ns)
    @tape.array = []
    ns.each do |n|
      @tape.array += [1] * (n+1) + [0]
    end
    @tape.array.pop
    @tape.head = 0
  end
  
  def output
    @tape.array.count(1)
  end
  
  def doaction(action)
    case action
    when 0
      @tape.write 0
    when 1
      @tape.write 1
    when L
      @tape.moveleft
    when R
      @tape.movewrite
    end
  end
end

# zero function
program = [
    [0, 1, 0, 1],
    [1, 0, R, 0],
    [0, 0, R, 2],
    [2, 1, 1, 0],
]

# addition function
program = [
    [0, 1, 0, 1],
    [1, 0, R, 2],
    [2, 1, R, 2],
    [2, 0, 0, 3],
    [3, 0, R, 4],
    [4, 1, 0, 5],
    [5, 0, L, 6],
    [6, 0, 1, 7],
    [7, 1, R, 3],
    [4, 0, L, 8],
    [8, 0, L, 9],
    [9, 1, 0, 10],
]

# monus function (with bug)
program = [
    [0, 1, R, 0],
    [0, 0, 0, 2],
    [2, 0, L, 2],
    [2, 1, 0, 3],
    [3, 0, R, 3],
    [3, 1, 0, 4],
    [4, 0, R, 5],
    [5, 1, L, 2],
]

# monus function
program = [
  [0, 1, R, 0],
  [0, 0, 0, 1],
  [1, 0, L, 2],
  [2, 1, 0, 3],
  [3, 0, L, 4],
  [4, 0, 0, 5],
  [5, 0, R, 5],
  [5, 1, 1, 6],
  [6, 1, 0, 7],
  [7, 0, R, 6],
  [4, 1, R, 17],
  [17, 0, R, 17],
  [17, 1, 0, 18],
  [18, 0, R, 19],
  [19, 0, 0, 20],
  [19, 1, L, 21],
  [21, 0, L, 21],
  [21, 1, 1, 0],
]

t = TuringMachine.new(program)

p t.run(0, 0)

p t.run(1, 0)
p t.run(0, 1)

p t.run(2, 0)
p t.run(1, 1)
p t.run(0, 2)

p t.run(3, 0)
p t.run(2, 1)
p t.run(1, 2)
p t.run(0, 3)

p t.run(4, 0)
p t.run(3, 1)