Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] The Turing Machine (#162)

Reply
Thread Tools

[QUIZ] The Turing Machine (#162)

 
 
Mike Stok
Guest
Posts: n/a
 
      05-11-2008
-----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 ffset
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 Stok <(E-Mail Removed)>
http://www.stok.ca/~mike/

The "`Stok' disclaimers" apply.




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

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

 
Reply With Quote
 
 
 
 
Chiyuan Zhang
Guest
Posts: n/a
 
      05-12-2008
And here's mine.

http://pastie.caboo.se/195332

I use two array to simulate the tape.

On Fri, May 9, 2008 at 11:48 PM, Matthew Moss <(E-Mail Removed)> wrote:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> The three rules of Ruby Quiz 2:
>
> 1. Please do not post any solutions or spoiler discussion for this
> quiz until 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
> permanent, new website is in the works for Ruby Quiz 2. Until then,
> please visit the temporary website at
>
> <http://matthew.moss.googlepages.com/home>.
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem
> helps everyone on Ruby Talk follow the discussion. Please reply to
> the original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> ## 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.
>
> A Turing Machine has but three simple parts:
>
> * A single state register.
> * An infinite tape of memory cells that can hold one character
> each, with a
> read/write head that points to one of these cells at any given
> time. The
> tape is filled with an infinite run of blank characters in
> either
> direction.
> * A finite set of program instructions. The program is just a big
> table of
> state transitions. The Turing Machine will look up an
> instruction based
> the current value of the state register and the current
> character under
> 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.
>
> To keep our Turning Machine simple, let's say that our state register
> can contain words matching the regular expression `/\w+/` and the tape
> only contains characters that match the expression `/\w/`. We will
> call our blank tape cell character the underscore.
>
> Program lines will be of the form:
>
> CurrentState _ NewState C R
>
> The above translates to: if the current state is CurrentState and the
> character under the tape head is our blank character, set the state to
> NewState, replace the blank character with a C, and move the tape head
> to the right one position. All five elements will be present in each
> line and separated by one or more whitespace characters. Allow for
> trailing comments (using #) on a line, comment only lines, and blank
> lines in the program by ignoring all three.
>
> The initial state of your Turing machine should be set to the
> CurrentState mentioned on the first line of the program. Optionally,
> the initial contents of the tape can be provided when the program is
> load, but it will default to an all blank tape. The program runs
> until it fails to find an instruction for the CurrentState and the
> character currently under the tape head, at which point it prints the
> current contents of the tape head from the first non-blank character
> to the last non-blank character and exits.
>
> Here's a sample run of a simple program through my Turing Machine so
> you can see how this plays out:
>
> $ cat palindrome.tm
> # Report whether a string of 0 and 1 (ie. a binary
> # number) is a palindrome.
> look_first 0 go_end_0 _ R
> look_first 1 go_end_1 _ R
> look_first _ write_es Y R
> go_end_0 0 go_end_0 0 R
> go_end_0 1 go_end_0 1 R
> go_end_0 _ check_end_0 _ L
> go_end_1 0 go_end_1 0 R
> go_end_1 1 go_end_1 1 R
> go_end_1 _ check_end_1 _ L
> check_end_0 0 ok_rewind _ L
> check_end_0 1 fail_rewind _ L
> check_end_0 _ ok_rewind _ L
> check_end_1 0 fail_rewind _ L
> check_end_1 1 ok_rewind _ L
> check_end_1 _ ok_rewind _ L
> ok_rewind 0 ok_rewind 0 L
> ok_rewind 1 ok_rewind 1 L
> ok_rewind _ look_first _ R
> fail_rewind 0 fail_rewind _ L
> fail_rewind 1 fail_rewind _ L
> fail_rewind _ write_o N R
> write_es _ write_s e R
> write_o _ done o R
> write_s _ done s R
>
> $ ruby tm.rb palindrome.tm 011010110
> Yes
>
> $ ruby tm.rb palindrome.tm 01101
> No
>
>
>




--
pluskid

 
Reply With Quote
 
 
 
 
Adam Shelly
Guest
Posts: n/a
 
      05-12-2008
On 5/9/08, Matthew Moss <(E-Mail Removed)> wrote:
> The three rules of Ruby Quiz 2:
> ...
> This week's task is to build a Turing Machine, so we can play around
> with the architecture.
>
> A Turing Machine has but three simple parts:
>
> * A single state register.
> * An infinite tape of memory cells that can hold one character
> each, with a
> read/write head that points to one of these cells at any given
> time. The
> tape is filled with an infinite run of blank characters in
> either
> direction.
> * A finite set of program instructions. The program is just a big
> table of
> state transitions. The Turing Machine will look up an
> instruction based
> the current value of the state register and the current
> character under
> 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 Shelly
$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

 
Reply With Quote
 
Alpha Chen
Guest
Posts: n/a
 
      05-12-2008
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
 
Reply With Quote
 
Matthew Moss
Guest
Posts: n/a
 
      05-13-2008
Looks like a pretty nice solution, except I think (but didn't confirm)
there is one problem:

> =A0 =A0 =A0 @head +=3D (dir =3D=3D '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...

 
Reply With Quote
 
Alpha Chen
Guest
Posts: n/a
 
      05-13-2008
On May 12, 6:54*pm, Matthew Moss <(E-Mail Removed)> 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.)
 
Reply With Quote
 
Matthew Moss
Guest
Posts: n/a
 
      05-13-2008
> > 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.)


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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SUMMARY] The Turing Machine (#162) Matthew Moss Ruby 4 05-16-2008 07:15 PM
Programming a Turing Machine roxorsoxor2345 C++ 1 12-15-2006 05:47 PM
Turing machine Kvele C Programming 3 01-07-2005 03:23 AM
C++ Simulator of a Universal Turing Machine Alex Vinokur C++ 0 12-19-2003 05:24 AM
C++ Simulator of a Nondeterministic Turing Machine Alex Vinokur C++ 0 11-12-2003 06:47 PM



Advertisments