On 5/9/08, Matthew Moss <matthew.moss / gmail.com> wrote:
> The three rules of Ruby Quiz 2:
> ...
> This week's task is to build a Turing Machine, so we can play around
> with the architecture.
>
> A Turing Machine has but three simple parts:
>
>    * A single state register.
>    * An infinite tape of memory cells that can hold one character
> each, with a
>      read/write head that points to one of these cells at any given
> time.  The
>      tape is filled with an infinite run of blank characters in
> either
>      direction.
>    * A finite set of program instructions.  The program is just a big
> table of
>      state transitions.  The Turing Machine will look up an
> instruction based
>      the current value of the state register and the current
> character under
>      head of the tape.  That instruction will provide a state for
> the
>      register, a character to place in the current memory cell, and
> an order to
>      move the head to the left or the right.
>

My first implementation is a fairly literal interpretation of the description.
One thing I realized is that there is one more thing the machine must
track.  It needs to know the boundaries of the tape that was input or
modified.  Otherwise it can't print it, since it could never tell the
difference between a very long run of blanks in the middle vs the
infinite portion at the ends.

http://pastie.caboo.se/195662

Then I tried to build the fastest implementation I could.

# RubyQuiz 162
# Turing machine implemented as a state machine
#  Adam Shelly
$DEBUG = true

#the state machine is a hash keyed by state as symbol
#each entry is an array indexed by tape value as int
#each array entry holds the next state, the value to write,
# and the direction to go (stored as +/-1)

def turing prog,tape=nil,istate=nil
  machine = Hash.new{|h,k|h[k]=Array.new}
  machine = prog.inject(machine){|m,line|
    if line !~ /^\s*$|^#/                    #skip comments and blanks
      state,val,newstate,newval,dir = line.split
      m[state.to_sym][val[0]]=[newstate.to_sym,newval[0],(dir[0]-?O)/3]
      istate||=state.to_sym                         #save initial state
    end
    m
  }
  #set initial conditions and move the head to the start of the tape
  state,newval,delta = istate,tape[head=0],0
  #loop as long as we have a valid state
  while newval
    #update the tape
    tape[head]=newval
    #move head and extend towards infinity if needed
    tape.push(?_) if (head+=delta)==tape.size
    tape.unshift(?_) and head=1 if head==0
    shownext(state,newval,delta) and showstate(tape,head,state) if $DEBUG
    #lookup next state
    state,newval,delta = machine[state][tape[head]]
  end
  puts;print tape.map{|v|v.chr}.join.gsub(/^_+/,'').gsub(/_+$/,'')
end

 #set up the tape as an array of characters
def preparetape tape
  if tape.is_a? String
    tape.split('').map{|c|c[0]}
  else
    tape||=[?_]
  end
end

def showstate tape,head,state
   print "#{head}: #{state}[#{tape[head].chr}] ".ljust(20)
   tape.each_with_index{|c,i|print(i==head ? "<#{c.chr}>" : c.chr)}
end
def shownext state,val,delta
  puts " => [#{state},#{val&&val.chr},#{delta}]";true
end

turing File.open(ARGV[0]){|f|f.read},preparetape(ARGV[1])

---
On my machine, the second implementation can be >100 times faster for
complex programs.

-Adam