On Fri, May 9, 2008 at 5:48 PM, Matthew Moss <matthew.moss / gmail.com> wrote:
> ## The Turing Machine
>
> _Quiz description by James Edward Gray II_
>
> The Turing Machine is a simple computing architecture dating all the
> way back to the 1930s.  While extremely primitive compared to any
> modern machine, there has been a lot of research showing that a Turing
> Machine is capable of just about anything the fancier machines can do
> (although much less efficiently, of course).
>
> This week's task is to build a Turing Machine, so we can play around
> with the architecture.

Hi,

This is what I did: the TuringMachine is made of a TuringTape, a
String for the current state and a hash of instructions. The
TuringTape represents the infinite tape, and it's an array of chars
and a pointer to the current position, with methods for reading,
writing and moving the head. The instructions have a string and a char
as the key for the hash, and the value of the hash is a new state, a
char to write and a head move. The rest of the program is just reading
a file and the initial tape values and running the program, which
involves finding an instruction for the current state and char, and
executing the instruction (changing the state, writing the char and
moving the head):

InstructionCondition = Struct.new :state, :char
InstructionAction = Struct.new :next_state, :char, :head_move

class TuringTape
  def initialize contents=nil
    @contents = (contents || "_").split ""
    @head = 0
  end

  def move_head dir
    if dir == :R
      @head += 1
      unless @contents[@head]
        @contents << "_"
      end
    else
      if @head == 0
        @contents.unshift "_"
      else
        @head -= 1
      end
    end
    self
  end

  def read
    @contents[@head]
  end

  def write char
    @contents[@head] = char
  end

  def contents
    @contents.join.tr("_", " ").strip
  end
end

class TuringMachine
  def initialize program, initial_tape_contents
    @tape = TuringTape.new initial_tape_contents
    @program = {}
    @current_state = nil
    program.each do |line|
      # skip comment lines
      next if line =~ /\A\s*\#/
      current_state, char, next_state, char_to_write, head_move =
line.split(" ")
      # skip blank lines
      next unless current_state
      # The starting state will be the first one found in the program
      unless @current_state
        @current_state = current_state
      end
      @program[InstructionCondition.new(current_state, char)] =
InstructionAction.new(next_state, char_to_write, head_move.to_sym)
    end
  end

  def run
    while instruction =
@program[InstructionCondition.new(@current_state, @tape.read)]
      @current_state = instruction.next_state
      @tape.write instruction.char
      @tape.move_head instruction.head_move
    end
    @tape.contents
  end
end

program = File.read(ARGV[0])
tape = ARGV[1]
puts TuringMachine.new(program,tape).run

Thanks for the quiz,

Jesus.