Quadruple Turing Machine (Ruby)

From LiteratePrograms

Jump to: navigation, search

We describe a simple Ruby program for simulating an abstract Turing machine. This demonstrates that Ruby is Turing-complete (with the caveat that limitations in word size limit the effective addressable memory). This version takes a quadruple of parameters [state1, symbol, action, state2]. For a quintuple version and an overview of Turing Machines in Ruby, see Turing_machine_simulator_(Ruby)


Contents

Main simulator

State representation

We represent states and symbols using Ruby symbols. The State class has instance variables describing the tape contents, the current position of the head on the tape, and the current control state. There are methods to initialize, update, and trace the state and convenience methods for accessing the tape:

<<State class>>=
class State
  attr_reader :tape
  attr_reader :head
  attr_reader :control_state
  initialize state method
  update state method
  trace state method
  convenience methods
end


To initialize the state, we initialize the tape with the input string, position the head at the start of the tape, and set the initial control state:

<<initialize state method>>=
def initialize(initial_state, input_string)
  @tape = input_string.dup
  @head = 0
  @control_state = initial_state
end


We can update the state based on what the transition function tells us to do. It supplies a new control state and an action. The action can be another symbol to write in the current location (pointed to by @head), or a direction indicated by :L for left or :R for right:

<<update state method>>=
def update(action, next_state, map)
  raise "Crash!" if next_state == :invalid
  @control_state = next_state
  case action
  when :L
    if (@head <= 0)
      @tape.unshift(:b)
      @head = 0
    else
      @head -= 1
    end
  when :R
    @head += 1
  else
    @tape[@head] = action
  end
end


Note that the head can move past the start, by adding a new "blank". The right end of the tape is auto-expanded with blank symbols by our use of the Array default value above.

For diagnostic purposes, it's also useful to print out some of the details of the state. We'll display the first 60 symbols of tape so that it may easily fit in a terminal. We need to provide a mapping to translate the symbols on the tape to simple screen characters:

<<trace state method>>=
def trace(map)
  if @head < 60
    puts " " * (@head + 17) + "v"
  else
    puts
  end
  tape = (0..60).collect{ |i| map[tape_at(i)] }.join
  puts "%15s: %s" % [ @control_state, tape ]
end

Finally, we provide a convenience methods to fetch symbols from the tape. The tape_at method abstracts access to the tape so we see a blank symbol anywhere the tape has not been written to. The current_symbol method gives us the symbol currently under the head.

<<convenience methods>>=
def tape_at(pos)
  @tape[pos] || :blank
end
def current_symbol
  tape_at(@head)
end


Machine representation

As mentioned above, Q and Γ are represented by Ruby symbols. We also assume the convention, demonstrated above, of using the symbol :blank to represent the blank symbol. The TuringMachine class represents the remaining information about the machine:

<<Turing machine class>>=
class TuringMachine
  attr_accessor :start_state
  attr_reader :accepting_states
  attr_reader :transitions
  initialize machine method
  run simulation method
end

The transition table is a hash which maps state/symbol pairs as the input key which to action/state doubles as the output value.

While accepting_state is simply initialized to an empty array, we must provide a default value for transitions in order to handle bad input. We use a special state :invalid to indicate this default production. Further specification of the machine is delayed until "programming", discussed below.

<<initialize machine method>>=
def initialize
  @accepting_states = []
  @transitions = Hash.new{ [ :invalid, :L ] }
end

Simulation

We now come to our primary simulation function. Using our machine state functionality, we can take a programmed TuringMachine object, feed it an input string and step through successive states. We provide a mapping of symbols to characters so that it can be passed on to the state tracing method:

<<run simulation method>>=
def simulate(input_string, map)
  state = State.new(@start_state, input_string)
  state.trace(map)
  until @accepting_states.include?(state.control_state)
    action, next_state =
      @transitions[[state.control_state, state.current_symbol]]
    begin
      state.update(action, next_state, map)
    rescue Exception => e
      puts e
      return
    end
    state.trace(map)
  end
end


Files

We place each of the classes above into their own files, as is the usual ruby idiom. The TuringMachine class depends on the State class, so we require the state library file in the Turing machine library:

<<state.rb>>=
State class
<<turing_machine.rb>>=
require 'state'
Turing machine class

Test driver

We'll begin by instantiating a TuringMachine object for it and "programming" that object with the start and finish states:

<<Example turing machine>>=
machine = TuringMachine.new
machine.start_state = :start
machine.accepting_states << :finish
define transitions

We then add entries for each arc in the diagram:

<<define transitions>>=
machine.transitions[[ :start, :a    ]] = [ :R, :state1 ]
machine.transitions[[ :start, :b    ]] = [ :b, :invalid ]
machine.transitions[[ :state1, :a    ]] = [ :R, :state1 ]
machine.transitions[[ :state1, :b    ]] = [ :b, :state2 ]
machine.transitions[[ :state2, :blank    ]] = [ :blank, :finish ]
machine.transitions[[ :state2, :b    ]] = [ :R, :state2 ]

Now, we simply invoke the simulate method object, allowing the user to specify the initial input on the command line:

<<example_turing_machine.rb>>=
require 'turing_machine'
unless ARGV.size == 1
  STDERR.puts "Usage: simulate_turing_machine <input string>"
  exit(-1)
end
# convert string into list of symbols
input_string = ARGV.first.split(//).map{ |ch| ch.intern }
Example turing machine
# define trace map
map = {
  :blank => '#',
  :a     => 'a',
  :b     => 'b',
  :L     => 'L',
  :R     => 'R'
}
# run simulation
machine.simulate(input_string, map)

If we run the program on a string in the language, like "aaabbb", the program will return quickly; otherwise it will work for a bit, then print out "Crash!" when it tries to perform an invalid transition. We ensure it's going through the right intermediate states through the tracing we added to the simulate function.

Now we can see, for example:

<<example_output.txt>>=
$ ruby example_turing_machine.rb ab
                 v
          start: ab###########################################################
                  v
         state1: ab###########################################################
                  v
         state2: ab###########################################################
                   v
         state2: ab###########################################################
                   v
         finish: ab###########################################################

See Quadruple Turing Machine simulator (Ruby)/Example output for a longer example output.

Download code
Views