The Turing Machine (#162)

Ruby
21

On Fri, May 9, 2008 at 5:48 PM, Matthew M. [email protected]
wrote:

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.

22

I attached my solution.

On Fri, May 9, 2008 at 10:48 AM, Matthew M. [email protected]

23

And here’s mine.

http://pastie.caboo.se/195332

I use two array to simulate the tape.

24

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thanks for the fun quiz. For fun I over-egged the solution:

tape.rb:

Turing machine tape.

class Tape

def initialize(string=‘’)
@string = string.length.zero? ? ‘_’ : string.dup
@offset = 0
end

def read
return @string[@offset].chr
end

def write(one_char_string)
@string[@offset] = one_char_string[0]
return
end

def move_head_left
if @offset == 0
@string.insert(0, ‘_’)
else
@offset -= 1
end
return
end

def move_head_right
@offset += 1
if @offset == @string.length
@string.insert(-1, ‘_’)
end
return
end

def content
return @string.dup
end

attr_reader :offset
end

turing.rb:

class Turing
def initialize(lines)
@action, @initial_state = load(lines)
end

def run(tape)
state = @initial_state
while action = @action[state][tape.read]
state = do_action(tape, state, *action)
end
end

def do_action(tape, current_state, next_state, write, move)
tape.write(write)
case move
when “L” then tape.move_head_left
when “R” then tape.move_head_right
end
return next_state
end

def load(lines)
action = Hash.new { |h,k| h[k] = {} }
initial_state = parse(lines) do |current_state, read, next_state,
write, move|
action[current_state][read] = [next_state, write, move]
end

 return action, initial_state

end

Make sure that the lines we are loading are all valid. Raise a

runtime error

if we suspect that garbage is being passed in. As each line is

parsed we yield

the validated information. The return value is the first

current_state mentioned

in the lines passed in.

The spec of the quiz maps neatly to a regex, so we’ll go with the

terse “parsing” and generic error message (we could keep track of

line

number in future if we wanted to be helpful)

def parse(lines)
initial_state = nil
lines.each_line do |line|
# deal with comments and blank lines
instructions = line.sub(/\s*#./, ‘’)
next if instructions =~ /^\s$/

   unless instructions =~ /^ \s* (\w+) # current state => $1
                             \s+ (\w)  # read char => $2
                             \s+ (\w+) # next state => $3
                             \s+ (\w)  # char to write => $4
                             \s+ (L|R) # tape head move direction

=> $5
\s* $
/x
raise RuntimeError, “bad line ‘#{line}’”
end

   current_state, read, next_state, write, move = $1, $2, $3, $4, $5
   initial_state ||= current_state;
   yield current_state, read, next_state, write, move
 end

 return initial_state

end
end

Having Turing::run call Turing::do_action let me play with
Console::ANSICode for fun:

tm.rb:

#!/usr/bin/env ruby

Ruby quiz 162

usage:

tm.rb [-d] program_file tape1 [tape2 […]]

require ‘turing’
require ‘tape’

class DisplayTuring < Turing
require ‘rubygems’
require ‘facets/ansicode’
include Console::ANSICode
def do_action(tape, current_state, next_state, write, move)
content = tape.content
offset = tape.offset
puts blue{ current_state } + “\t” +
blue{ content[0, offset] || ‘’ } +
black{ on_cyan { content[offset, 1] || ‘’ } } +
blue{ content[offset+1 … -1] || ‘’ }
super
end
end

machine_type = Turing
if ARGV.length > 0 && ARGV[0] == ‘-d’
machine_type = DisplayTuring
ARGV.shift
end

if ARGV.length < 2
raise RuntimeError, “bad args on command line”
end

t = machine_type.new(File.open(ARGV.shift))
ARGV.each do |tape_content|
tape = Tape.new(tape_content)
t.run(tape)
puts tape.content.tr(‘_’, ’ ').strip
end

Mike S. [email protected]
http://www.stok.ca/~mike/

The “`Stok’ disclaimers” apply.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Darwin)

iEYEARECAAYFAkgneKsACgkQnsTBwAWZE9qfPgCeJ+jNl2Rk9baHPSfAqvOZJ3Ih
R3EAniCupYipgp9OtejcQ/b+ddBfG3ND
=pA5K
-----END PGP SIGNATURE-----

25

A pretty simplistic solution:

#!/usr/bin/env ruby

class Turing
def initialize(file, tape=nil)
@tape = Hash.new(’_’)
@head = 0

# initialize tape
tape.split(//).each_with_index {|c,i| @tape[i] = c } if tape

# read program instructions
@program = Hash.new
File.open(file).each_line do |line|
  line.gsub!(/#.*/, '') # remove comments
  next if line =~ /^\s*$/ # skip blank lines

  line = line.split(/\s+/)
  @state = line[0] if @state.nil?
  @program[line[0..1]] = line[2..4]
end

end

def run
while next_state = @program[[@state, @tape[@head]]]
@state, @tape[@head], dir = next_state
@head += (dir == ‘R’) ? 1 : -1
end

puts @tape.sort.map {|_,v| v}.join.gsub(/^_*|_.*$/, '')

end
end

Turing.new(ARGV.shift, ARGV.shift).run if FILE == $0

26

On 5/9/08, Matthew M. [email protected] wrote:

 read/write head that points to one of these cells at any given
 head of the tape.  That instruction will provide a state for

the
register, a character to place in the current memory cell, and
an order to
move the head to the left or the right.

My first implementation is a fairly literal interpretation of the
description.
One thing I realized is that there is one more thing the machine must
track. It needs to know the boundaries of the tape that was input or
modified. Otherwise it can’t print it, since it could never tell the
difference between a very long run of blanks in the middle vs the
infinite portion at the ends.

http://pastie.caboo.se/195662

Then I tried to build the fastest implementation I could.

RubyQuiz 162

Turing machine implemented as a state machine

Adam S.

$DEBUG = true

#the state machine is a hash keyed by state as symbol
#each entry is an array indexed by tape value as int
#each array entry holds the next state, the value to write,

and the direction to go (stored as +/-1)

def turing prog,tape=nil,istate=nil
machine = Hash.new{|h,k|h[k]=Array.new}
machine = prog.inject(machine){|m,line|
if line !~ /^\s*$|^#/ #skip comments and blanks
state,val,newstate,newval,dir = line.split
m[state.to_sym][val[0]]=[newstate.to_sym,newval[0],(dir[0]-?O)/3]
istate||=state.to_sym #save initial state
end
m
}
#set initial conditions and move the head to the start of the tape
state,newval,delta = istate,tape[head=0],0
#loop as long as we have a valid state
while newval
#update the tape
tape[head]=newval
#move head and extend towards infinity if needed
tape.push(?) if (head+=delta)==tape.size
tape.unshift(?) and head=1 if head==0
shownext(state,newval,delta) and showstate(tape,head,state) if
$DEBUG
#lookup next state
state,newval,delta = machine[state][tape[head]]
end
puts;print tape.map{|v|v.chr}.join.gsub(/^+/,‘’).gsub(/+$/,‘’)
end

#set up the tape as an array of characters
def preparetape tape
if tape.is_a? String
tape.split(‘’).map{|c|c[0]}
else
tape||=[?_]
end
end

def showstate tape,head,state
print "#{head}: #{state}[#{tape[head].chr}] “.ljust(20)
tape.each_with_index{|c,i|print(i==head ? “<#{c.chr}>” : c.chr)}
end
def shownext state,val,delta
puts " => [#{state},#{val&&val.chr},#{delta}]”;true
end

turing File.open(ARGV[0]){|f|f.read},preparetape(ARGV[1])

On my machine, the second implementation can be >100 times faster for
complex programs.

-Adam

27

On May 12, 6:54 pm, Matthew M. [email protected] wrote:

Looks like a pretty nice solution, except I think (but didn’t confirm)
there is one problem:

  @head += (dir == 'R') ? 1 : -1

Doing this could cause the head to wrap around, since array[-1] in
Ruby is the last element of the array. It’s likely the examples won’t
exercise this constraint, but the tape should not loop…

That could be a problem, but I cheated: @tape is actually a hash. (I
was lazy and didn’t want to make a Tape class or add extra logic to
deal with going past the front of the tape.)

28

Looks like a pretty nice solution, except I think (but didn’t confirm)
there is one problem:

  @head += (dir == 'R') ? 1 : -1

Doing this could cause the head to wrap around, since array[-1] in
Ruby is the last element of the array. It’s likely the examples won’t
exercise this constraint, but the tape should not loop…

29

was lazy and didn’t want to make a Tape class or add extra logic to
deal with going past the front of the tape.)

Ah, well played, sir. I concede the point. :slight_smile: