tm.rb (Turing machine simulator)

#!/usr/bin/ruby

def loadtm(tm)

  $max = 0
  state1 = 0

  File.open(tm).each \
  {
    |line|
  
    if (n = line.index('#')) then

      $comment[state1] = line[n+1..-1].strip
      line[n..-1] = ''
    end
  
    list = line.split
    
    if (list.size == 0) then
      state1 += 1
      next
    end

    n = list[0].to_i

    if (list.size == 1) then
      raise('expecting state ' + state1.to_s + ", got " + n.to_s) if (n != state1)
      next
    end

    if (list.size == 2) then
      $debug[n] = list[1]
      next
    end

    raise('not a 4 tuple: ' + line) if (list.size != 4)
  
    sym1, sym2, dir, state2 = list

    [sym1, sym2].each { |x| y = x.length; $max = y if (y > $max) }
  
    $states[state1] = {} if (!$states.key?(state1))

    state2 = state2.to_i if (state2 != 'HALT')
 
    $states[state1][sym1] = [sym2, dir, state2]
  }

end

def out(pos, tape, state, info)

  if (info) then
    if (state != 'HALT' and $prior != $comment[state]) then

      puts($comment[state]) 
      $prior = $comment[state]

    end
  end
    
  printf('%-4s  ', state.to_s)
  
  tape.each_with_index \
  { 
    |sym, index| 
 
    printf('%s%-*s', (index == pos) ? '>' : ' ', $max, sym) 
  }
  
  puts

end

def debug(varname, tape)

  if (varname == "T") then
    print("\t")
    return
  elsif (varname == "I") then
    print($i)
    return
  elsif (varname == "NL") then
    puts
    return
  elsif (varname[0].chr == 'S') then
    print(' ' * varname[1..-1].to_i)
    return
  end
  
  f = false
  b = 1
  n = 0
  tape.each \
  {
    |sym|

    if (sym == varname) then
      f = true 
      next
    end

    next if (!f)
          
    break if (!['0', '1'].include?(sym))
    
    n |= b if (sym == '1')

    b <<= 1
  }
  raise("no #{varname} on tape") if (!f)
  print(n)
end

raise('specify tm') if (ARGV.size != 1)
tm, = ARGV

$states = {}
$comment = []
$debug = {}

loadtm(tm)

tape = ['_']

pos = 0

state = 0

$dmode = 1
last = 100000



$i = 1
loop \
{
  out(pos, tape, state, true) if ($dmode == 0)
  
  if ($debug.key?(state)) then
    if ($dmode == 1) then
      arg = $debug[state]
      if (arg.match(/"(.*)"/)) then
        print($1)
      elsif (arg == "TM")
        out(pos, tape, state, true)
      else
        debug(arg, tape)
      end
    end
    state += 1
    $stdout.flush
    next
  end

  if ($dmode == 2)
    print("#{$i}\t")
    out(pos, tape, state, false)
  end
  
  sym2, dir, state2 = $states[state][sym1 = tape[pos]]

  if (state2.nil?) then
    out(pos, tape, state)
    raise("no trans '#{state},#{sym1}'") 
  end
  
  tape.push('_') if pos == tape.size - 1 and (sym2 != '_' or dir == 'R')

  tape[pos] = sym2

  pos += 1 if (dir == 'R')

  pos -= 1 if (dir == 'L')


  state = state2

  if (state == 'HALT') then
  
    break 
  end
  $i += 1
  break if ($i == last)
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s