## mark a section (Learn more)

#!/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

This paste will be private.