I usually don't do multiple posts per day, but once I got the white-board, I just started crushing some code (brah) and had to share. As seen in the picture, I had outlined how I wanted to implement a Turing Machine ( TM ) in Ruby. I have since expanded my initial concept into a Universal Turing Machine (UTM). The code accepts an instruction file that contains the states necessary to compute something and a list of symbols. The file is a simulation of having the same instructions "on the tape".

The format is as follows:

#This is a comment, parser ignores it
state=stateName
(state,symbol) (newState,symbolToWrite,movement)
 .
 .
 .

I wrote one to detect a palindrome over the alphabet {0,1}*

#Turing instructions for palindrome detection over {0,1}
state=s
(s,$) (s,$,right)
(s,b) (qy,b,stop)
(s,0) (q0,$,right)
(s,1) (q1,$,right)
state=q0
(q0,b) (q00,b,left)
(q0,0) (q0,0,right)
(q0,1) (q0,1,right)
state=q1
(q1,b) (q11,b,left)
(q1,0) (q1,0,right)
(q1,1) (q1,1,right)
state=q00
(q00,$) (qy,$,stop)
(q00,0) (q2,b,left)
(q00,1) (qn,1,stop)
state=q11
(q11,$) (qy,$,stop)
(q11,0) (qn,0,stop)
(q11,1) (q2,b,left)
state=q2
(q2,$) (s,$,right)
(q2,0) (q2,0,left)
(q2,1) (q2,1,left)

As a brief refresher:

TM starts in "start" state
TM reads symbol
TM acts on that symbol as defined in its state programming seen above
repeat until TM halts (it could never halt but that's outside the scope of this post)

TM halts when it reaches a YES or NO answer to whatever the problem is. In the above instruction set, it halts on yes if the string is in fact a palindrome and no if it is not. For any arbitrarily long string, this TM will eventually halt.

Without further ado, the code:

class TuringOp
  attr_reader :newState, :writeVal, :movement
  def initialize(newState, writeVal, movement)
    @newState = newState
    @writeVal = writeVal
    @movement = movement
  end
end

class TuringState
  def initialize(name)
    @name = name
    @ops = Hash.new
  end
  
  def run(curSymbol)
    #return op object for now, perhaps refactor into a function taking the tape?
    @ops[curSymbol]
  end

  def add_operation(curSymbol, newState, writeVal, movement)
    @ops[curSymbol] = TuringOp.new(newState, writeVal, movement)
  end

  def to_s
    @name
  end
end

class TuringSymbol
  def initialize(rep)
    @rep = rep
  end

  def to_s
    @rep
  end
end

class TuringMachine
  def initialize(q, e, file)
    @states = Hash.new
    @symbols = []
    parse_symbols(e)
    #states are parsed in the file
    parse_encoding(file)
  end

  def dump_machine_info
    print "States: #{@states}"
    puts
    print "Symbols: #{@symbols}"
    puts
  end

  def num_states
    @states.size
  end

  def run(inputString)
    puts "Running Turing Machine with input string #{inputString}"
    #make a copy for writing 
    mutableString = inputString
    curPos = 0
    #assume for now any program will eventually halt
    #start state always "s"
    curState = "s"
    while true
      #read symbol from current position
      curSymbol = mutableString[curPos]
      #puts "DEBUG: curState: #{curState} curSymbol: #{curSymbol}"
      #lookup op to do
      tempOp = @states[curState].run(curSymbol)
      if tempOp == nil
          puts "ERROR: curState: #{curState} curSymbol: #{curSymbol}"
          exit
      end
      #perform operation
      curState = tempOp.newState
      mutableString[curPos] = tempOp.writeVal
      case tempOp.movement
        when "right"
          curPos = curPos + 1
        when "left"
          curPos = curPos - 1
        when "stop"
          break
      end #movement case
    end #infinite while loop

    #puts "Tape result: #{mutableString}"
    puts "Final state: #{curState}"
  end

private

  def parse_symbols(e)
    puts "Parsing symbols..."
    vals = e.split(',')
    vals.each do |sym|
      @symbols << TuringSymbol.new(sym)
    end 
  end

  def parse_encoding(fileName)
    puts "Parsing given machine..."
    File.open(fileName, "r") do |file|
      while line = file.gets
        unless line[0] == '#'
          if line.include?("state=")
            #create state object, give it an easily lookupable hash key
            temp = line.split('=')[1].strip
            @states[temp] = TuringState.new(temp)
          else
            #grab two "parts": (state,curSymbol)(newState,whatToWrite,movement)
            details = line.split(' ')
            #remove ()'s
            if details[0] != nil and details[1] != nil
              details[0].gsub!('(','')
              details[0].gsub!(')','')
              details[1].gsub!('(','')
              details[1].gsub!(')','')
            end
            #check if there is already is a state obj created and add steps to it if so
            cur = details[0].split(',')
            curState = cur[0]
            curSymbol = cur[1]
            #this check is unnecessary assuming a well formed instruction file
            if @states[curState] != nil
              #puts "Adding #{curSymbol} operation to #{curState}..."
              #parse 2nd half
              steps = details[1].split(',')
              newState = steps[0]
              symbolToWrite = steps[1]
              move = steps[2]
              @states[curState].add_operation(curSymbol, newState, symbolToWrite, move)
            else
              puts "Invalid state found, check instruction file, exiting..."
              exit
            end #state existance check
          end #if/else block
        end #unless
      end #while
    end #file
  end #encoding function
end #TM class

#start symbol is the dollar sign
machine = TuringMachine.new("", "$,b,0,1", "instructionsTest")
machine.dump_machine_info
#input strings must end with a blank/'b'
#no instance
machine.run("$0011b")
#yes instance
machine.run("$010000000010000000010b")

Results:

Quote

On the todo list:

• Implement a more OOP style to the operation call. Something along the lines of passing the tape string in and having the op take place all within itself.
  
• Make it more "Ruby-ism". I'm sure my coding style screams other languages' influence.
  
• The parser is currently brittle, expecting a well formed instruction file.
  
• Perhaps throw a GUI on this
  
• Some code cleanup

Oh, on somewhat of a related tangent*, if you haven't read Cryptonomicon, I highly recommend. Yes I'm a decade+ behind, but I just finished it and it was pretty awesome.

*

Happy coding!