1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#!/usr/bin/env ruby -wKU

# A simple implementation of a Turing machine.
class TuringMachine
  
  # Create a new TuringMachine.  Giving a set of instructions as an Array of
  # Strings (which will be parsed for you).  Optionally, one may pass in the
  # initial state of the tape as a String.  The tape head will be positioned
  # at the first character of the +tape+ string.
  def initialize(instructions, tape='')
    @instructions = Parser.parse(instructions)
    # @tape_r contains the tape under the tape head and rightward.
    # @tape_l contains the tape leftward from the tape head.
    @tape_r       = tape.split(//)
    @tape_l       = []
  end
  
  # The meat of it all.  Loop through the instructions until none match the
  # current state of the machine.  At the end, print out the contents of the
  # tape.
  def run
    state = @instructions.first[:state]
    keep_going = true
    
    while keep_going
      keep_going = false
      @instructions.each do |instruction|
        if state == instruction[:state] and read == instruction[:read]
          state = instruction[:set_state]
          write(instruction[:write])
          move(instruction[:move])
          
          keep_going = true
        end
      end
    end
    
    output_tape
  end
  
  # Read the value at the tape head.  '_' represents blankness.
  def read
    @tape_r.first || '_'
  end
  
  # Write the value at the tape head.
  def write(value)
    @tape_r[0] = value
  end
  
  # Move the tape head right or left.
  def move(direction)
    case direction
    when 'R'
      @tape_l.unshift(@tape_r.shift)
    when 'L'
      @tape_r.unshift(@tape_l.shift)
    end
  end
  
  # Writes the contents of the tape to STDOUT, stripping off any blanks on
  # either end
  def output_tape
    output = "#{@tape_l.reverse}#{@tape_r}"
    output.sub!(/^_+/,'')
    output.sub!(/_+$/,'')
    
    STDOUT.puts(output)
  end
  
  # The Parser module just handles (surpise!) parsing the instructions.
  module Parser
    
    # Parse the instructions, ignoring blank lines and comments (lines
    # starting with a #)
    def self.parse(instructions)
      instructions.map! do |instruction|
        case instruction
        when /^\s*$/, /^\s*#/
          nil
        when /^(\w+)\s+(\w)\s+(\w+)\s+(\w)\s+(R|L)/
          {:state => $1,
           :read => $2,
           :set_state => $3,
           :write => $4,
           :move => $5}
        else
          raise ArgumentError, "Badly formed instruction '#{instruction}'"
        end
      end
      instructions.compact
    end
    
  end
end

if __FILE__ == $PROGRAM_NAME
  instructions = File.readlines(ARGV.first)
  machine = TuringMachine.new(instructions, ARGV[1].to_s)
  machine.run
end