[QUIZ] The Turing Machine (#162)
Matthew Moss
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
Matthew Moss
> 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>.
Forgot to put in the revised URL for the less-temporary website:
Chris Shea
I created another program for our Turning machines that reverses a
string of zeros and ones.
$ cat reverse.tm
# Reverses a string of 0s and 1s
mark_start 0 mark_start 0 L
mark_start 1 mark_start 1 L
mark_start _ mark_end S R
mark_end 0 mark_end 0 R
mark_end 1 mark_end 1 R
mark_end _ rewind E L
rewind 0 rewind 0 L
rewind 1 rewind 1 L
rewind S read_first S R
read_first 0 append_0 _ L
read_first 1 append_1 _ L
read_first _ read_first _ R
read_first E erase_marks _ L
erase_marks _ erase_marks _ L
erase_marks S done _ L
append_0 S write_0 S L
append_0 0 append_0 0 L
append_0 1 append_0 1 L
append_0 _ append_0 _ L
append_1 S write_1 S L
append_1 0 append_1 0 L
append_1 1 append_1 1 L
append_1 _ append_1 _ L
write_0 0 write_0 0 L
write_0 1 write_0 1 L
write_0 _ find_start 0 R
write_1 0 write_1 0 L
write_1 1 write_1 1 L
write_1 _ find_start 1 R
find_start 0 find_start 0 R
find_start 1 find_start 1 R
find_start S read_first S R
$ ruby tm.rb reverse.tm 1011
1101
The names of the states could probably use some improvement, and maybe
there's a more efficient implementation, but there it is. I hope
others share some.
Chris
Adam Shelly
> I created another program for our Turning machines that reverses a
> string of zeros and ones.
> I hope others share some.
>
$ cat add1.rb
#adds 1 to a binary number
seekLSB 1 seekLSB 1 R
seekLSB 0 seekLSB 0 R
seekLSB _ add1 _ L
add1 1 add1 0 L
add1 0 done 1 L
add1 _ done 1 L
$ruby turing.rb add1.rb 0
1
$ruby turing.rb add1.rb 1011
1100
-Adam
Chiyuan Zhang
instruction for not moving the head?
--
pluskid
James Gray
> Does it mean the tape head move action can only be [RL] ? Is there an
> instruction for not moving the head?
Correct, the tape moves with each instruction.
James Edward Gray II
Glen F. Pankow
> ... I hope others share some.
Below is a (very ugly) machine to convert binary to octal,
since it seems binary is the popular test representation.
$ ruby quiz-162 to_oct.tm
0
$ ruby quiz-162 to_oct.tm 0
0
$ ruby quiz-162 to_oct.tm 101
5
$ ruby quiz-162 to_oct.tm 000001010011100101110111
1234567
An annotated example:
$ ruby quiz-162 to_oct.tm 0011101
# Span to the end of the binary digits; mark the end.
span_end 0 -> span_endB 0 R : >0< 0 1 1 1 0 1
span_endB 0 -> span_endB 0 R : 0 >0< 1 1 1 0 1
span_endB 1 -> span_endB 1 R : 0 0 >1< 1 1 0 1
span_endB 1 -> span_endB 1 R : 0 0 1 >1< 1 0 1
span_endB 1 -> span_endB 1 R : 0 0 1 1 >1< 0 1
span_endB 0 -> span_endB 0 R : 0 0 1 1 1 >0< 1
span_endB 1 -> span_endB 1 R : 0 0 1 1 1 0 >1<
span_endB _ -> cvt_xxx X L : 0 0 1 1 1 0 1 >_<
# Convert each set of three binary digits to an octal digit.
cvt_xxx 1 -> cvt_xx1 _ L : 0 0 1 1 1 0 >1< X
cvt_xx1 0 -> cvt_x01 _ L : 0 0 1 1 1 >0< _ X
cvt_x01 1 -> cvt_xxx 5 L : 0 0 1 1 >1< _ _ X
cvt_xxx 1 -> cvt_xx1 _ L : 0 0 1 >1< 5 _ _ X
cvt_xx1 1 -> cvt_x11 _ L : 0 0 >1< _ 5 _ _ X
cvt_x11 0 -> cvt_xxx 3 L : 0 >0< _ _ 5 _ _ X
cvt_xxx 0 -> cvt_xx0 _ L : >0< 3 _ _ 5 _ _ X
cvt_xx0 _ -> squeeze 0 L : >_< _ 3 _ _ 5 _ _ X
# Squeeze intervening spaces.
squeeze _ -> squeezeA _ R : >_< 0 _ 3 _ _ 5 _ _ X
squeezeA 0 -> squeezeA _ R : _ >0< _ 3 _ _ 5 _ _ X
squeezeA _ -> squeezeA _ R : _ _ >_< 3 _ _ 5 _ _ X
squeezeA 3 -> squeezeB 3 R : _ _ _ >3< _ _ 5 _ _ X
squeezeB _ -> squeezeC X R : _ _ _ 3 >_< _ 5 _ _ X
squeezeC _ -> squeezeC _ R : _ _ _ 3 X >_< 5 _ _ X
squeezeC 5 -> squeeze5 _ L : _ _ _ 3 X _ >5< _ _ X
squeeze5 _ -> squeeze5 _ L : _ _ _ 3 X >_< _ _ _ X
squeeze5 X -> squeezeD 5 R : _ _ _ 3 >X< _ _ _ _ X
squeezeD _ -> squeezeC X R : _ _ _ 3 5 >_< _ _ _ X
squeezeC _ -> squeezeC _ R : _ _ _ 3 5 X >_< _ _ X
squeezeC _ -> squeezeC _ R : _ _ _ 3 5 X _ >_< _ X
squeezeC _ -> squeezeC _ R : _ _ _ 3 5 X _ _ >_< X
squeezeC X -> squeezeX _ L : _ _ _ 3 5 X _ _ _ >X<
squeezeX _ -> squeezeX _ L : _ _ _ 3 5 X _ _ >_< _
squeezeX _ -> squeezeX _ L : _ _ _ 3 5 X _ >_< _ _
squeezeX _ -> squeezeX _ L : _ _ _ 3 5 X >_< _ _ _
squeezeX X -> __done__ _ L : _ _ _ 3 5 >X< _ _ _ _
__done__ 5 -> --none-- : _ _ _ 3 >5< _ _ _ _ _
---> '35'
$ cat to_oct.tm
#
# Convert binary to octal.
#
#
# Span to the end of the binary digits; mark the end.
#
span_end 0 span_endB 0 R
span_end 1 span_endB 1 R
span_end _ __done__ 0 R
span_endB 0 span_endB 0 R
span_endB 1 span_endB 1 R
span_endB _ cvt_xxx X L
#
# Convert each set of three binary digits to an octal digit.
#
cvt_xxx 0 cvt_xx0 _ L
cvt_xxx 1 cvt_xx1 _ L
cvt_xxx _ squeeze 0 L
cvt_xx0 0 cvt_x00 _ L
cvt_xx0 1 cvt_x10 _ L
cvt_xx0 _ squeeze 0 L
cvt_x00 0 cvt_xxx 0 L
cvt_x00 1 cvt_xxx 4 L
cvt_x00 _ squeeze 0 L
cvt_x10 0 cvt_xxx 2 L
cvt_x10 1 cvt_xxx 6 L
cvt_x10 _ squeeze 2 L
cvt_xx1 0 cvt_x01 _ L
cvt_xx1 1 cvt_x11 _ L
cvt_xx1 _ squeeze 1 L
cvt_x01 0 cvt_xxx 1 L
cvt_x01 1 cvt_xxx 5 L
cvt_x01 _ squeeze 1 L
cvt_x11 0 cvt_xxx 3 L
cvt_x11 1 cvt_xxx 7 L
cvt_x11 _ squeeze 3 L
#
# Squeeze intervening spaces.
#
squeeze _ squeeze _ R
squeeze 0 squeeze _ R
squeeze 1 squeezeB 1 R
squeeze 2 squeezeB 2 R
squeeze 3 squeezeB 3 R
squeeze 4 squeezeB 4 R
squeeze 5 squeezeB 5 R
squeeze 6 squeezeB 6 R
squeeze 7 squeezeB 7 R
squeeze X __done__ 0 R
squeezeB _ squeezeC X R
squeezeC _ squeezeC _ R
squeezeC 0 squeeze0 _ L
squeeze0 _ squeeze0 _ L
squeeze0 X squeezeD 0 R
squeezeD _ squeezeC X R
squeezeC 1 squeeze1 _ L
squeeze1 _ squeeze1 _ L
squeeze1 X squeezeD 1 R
squeezeC 2 squeeze2 _ L
squeeze2 _ squeeze2 _ L
squeeze2 X squeezeD 2 R
squeezeC 3 squeeze3 _ L
squeeze3 _ squeeze3 _ L
squeeze3 X squeezeD 3 R
squeezeC 4 squeeze4 _ L
squeeze4 _ squeeze4 _ L
squeeze4 X squeezeD 4 R
squeezeC 5 squeeze5 _ L
squeeze5 _ squeeze5 _ L
squeeze5 X squeezeD 5 R
squeezeC 6 squeeze6 _ L
squeeze6 _ squeeze6 _ L
squeeze6 X squeezeD 6 R
squeezeC 7 squeeze7 _ L
squeeze7 _ squeeze7 _ L
squeeze7 X squeezeD 7 R
squeezeC X squeezeX _ L
squeezeX _ squeezeX _ L
squeezeX X __done__ _ L
Juanger
stay in the same cell and the one that doesn't).
In our case, you will have to use another state to emulate that behaviour.
On Fri, May 9, 2008 at 11:42 PM, James Gray <ja...@grayproductions.net>
wrote:
--
Ash Mac durbatulûk, ash Mac gimbatul, ash Mac thrakatulûk agh burzum-ishi
krimpatul.
Juanger.
Adam Shelly
> Chris Shea wrote:
>> ... I hope others share some.
>
> Below is a (very ugly) machine to convert binary to octal,
> since it seems binary is the popular test representation.
>
converter I took a fairly different approach. I think binary is
popular because it limits the number of state transitions required.
Compare my seekLSB state to the exitHex state - both do the same
thing, but the one that supports hex is 6 times bigger.
-Adam
--------------
## bin2hex.tm
## converts binary to hex
## by creating an accumulator (the store)
## to the left of the input, and moving one
## bit at a time from the input to the store
#first find the MSB of the input
seekMSB 1 seekMSB 1 L
seekMSB 0 seekMSB 0 L
seekMSB _ makeStore _ L
#creates the storage for the hex value: tape:= 0_<input>
makeStore _ moveRight 0 R
#goes to lsb of input
moveRight _ seekLSB _ R
seekLSB 1 seekLSB 1 R
seekLSB 0 seekLSB 0 R
seekLSB _ dec _ L
#decrement binary, starting from LSB
#when we get to a 1 we are done
#if we get to a _ we must have started with all 0s .
dec 0 dec 1 L
dec 1 findStore 0 L
dec _ clearRight _ R #so just cleanup the original input
#seeks back to the store
findStore 0 findStore 0 L
findStore 1 findStore 1 L
findStore _ addToStore _ L
#adds 1 to store
addToStore _ exitHex 1 R
addToStore 0 exitHex 1 R
addToStore 1 exitHex 2 R
addToStore 2 exitHex 3 R
addToStore 3 exitHex 4 R
addToStore 4 exitHex 5 R
addToStore 5 exitHex 6 R
addToStore 6 exitHex 7 R
addToStore 7 exitHex 8 R
addToStore 8 exitHex 9 R
addToStore 9 exitHex A R
addToStore A exitHex B R
addToStore B exitHex C R
addToStore C exitHex D R
addToStore D exitHex E R
addToStore E exitHex F R
addToStore F addToStore 0 L #carry
#move head back into the input
exitHex 0 exitHex 0 R
exitHex 1 exitHex 1 R
exitHex 2 exitHex 2 R
exitHex 3 exitHex 3 R
exitHex 4 exitHex 4 R
exitHex 5 exitHex 5 R
exitHex 6 exitHex 6 R
exitHex 7 exitHex 7 R
exitHex 8 exitHex 8 R
exitHex 9 exitHex 9 R
exitHex A exitHex A R
exitHex B exitHex B R
exitHex C exitHex C R
exitHex D exitHex D R
exitHex E exitHex E R
exitHex F exitHex F R
exitHex _ seekLSB _ R
#erase a binary string to the right
clearRight 0 clearRight _ R
clearRight 1 clearRight _ R
clearRight _ done _ L #done cleanup, ready to print
Matthew Moss
Machine Quiz. I have enough work to do as it is writing summaries for
Ruby Quiz, and I *really* don't want to read a bunch of turing machine
code.
:) Just kidding...
(No I'm not. ;)
Chris Shea
Too bad. I've started on a DSL for creating Turing machine code. I
just generated a 1,568 line program to reverse a lowercase word.
$ ./tm rev.tm ruby
ybur
$ ./tm rev.tm turing
gnirut
$ ./tm rev.tm racecar
racecar
$ time ./tm rev.tm abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba
0.84s user 0.01s system 99% cpu 0.857 total
http://pastie.textmate.org/195072
Chris
ThoML
Yummy. Please share.
> http://pastie.textmate.org/195072
Cool.
Chris Shea
> > I've started on a DSL for creating Turing machine code.
>
> Yummy. Please share.
Unless it's going to be a follow-up quiz. I think it'd make a great
series of follow-up quizzes. First we abstract the Turing machine a
little, then a little more, and a little more, and up until we write a
Ruby implementation.
Chris
Chris Carter
> Just so you guys know, I have no intentions of starting Turning
> Machine Quiz. I have enough work to do as it is writing summaries for
> Ruby Quiz, and I *really* don't want to read a bunch of turing machine
> code.
I am surprised nobody has shared their Hello World!
saurasaurus:~ cdcarter$ cat hello.tm
# Hello World!
curr_state _ h h R
h _ e e R
e _ l l R
l _ l2 l R
l2 _ o o R
o _ w w R
w _ o2 o R
o2 _ r r R
r _ l3 l R
l3 _ d d R
d _ ex ! R
--
Chris Carter
concentrationstudios.com
brynmawrcs.com
Chris Shea
It looks like it's been 48 hours, so here's what I whipped up:
http://pastie.textmate.org/195153
I hope it's pretty straightforward.
Chris
ThoML
Already. Ok, so here is mine.
#!/usr/bin/env ruby
def tm(rules, q, input)
directions = {'L' => -1, 'R' => 1}
tape = input ? input.split(//) : []
p = 0
loop do
q, c, d = rules[[q, tape[p] || '_']]
return tape.join unless q
tape[p] = c == '_' ? nil : c
p += directions[d] || raise('Unknown direction: %s' % d)
if p == -1
tape.unshift(nil)
p = 0
end
end
end
def read_rules(file)
rules = {}
q = nil
File.readlines(file).each do |l|
a = l.scan(/#|\S+/)
next if a[0] == '#' or a.empty?
q ||= a[0]
rules[a[0,2]] = a[2,5]
end
return [rules, q]
end
if __FILE__ == $0
file, input = ARGV
puts tm(*read_rules(file), input)
end
Chris Carter
> http://pastie.textmate.org/195153
>
> I hope it's pretty straightforward.
>
> Chris
Here's mine:
http://pastie.textmate.org/195165
It is pretty simple, and short.
Sandro Paganotti
hard implement the Tape model)
Hope you like it :D
Solution: http://pastie.textmate.org/195173
--
Go outside! The graphics are amazing!
Andrew Thompson
read up on it for this quiz but I had fun implementing one:
http://eagle.bsd.st/~andrew/turing.rb
Andrew
--
Posted via http://www.ruby-forum.com/.
Jesús Gabriel y Galán
> ## 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.
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.
Mike Stok
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 Stok <mi...@stok.ca>
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-----
Chiyuan Zhang
Adam Shelly
> 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.
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
Alpha Chen
#!/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
Matthew Moss
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...
Alpha Chen
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.)
Matthew Moss
> > 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. :)
Matthew Moss
code were sent in, including one example of over 1,500 lines,
generated by code. Most others were simpler, handcrafted rulesets and
tapes, dealing primarily with the limited input set of binary numbers.
This kept code size smaller and easier to understand.
A thought occurred to me that we might make an Extended Turing
Machine, so we would no longer have to eliminate very repetitive state
information. To take a small portion of one example:
...
mark_start v mark_start v L
mark_start w mark_start w L
mark_start x mark_start x L
mark_start y mark_start y L
mark_start z mark_start z L
mark_start _ mark_end S R
mark_end a mark_end a R
mark_end b mark_end b R
mark_end c mark_end c R
mark_end d mark_end d R
...
Using a regular expression for the second argument with an implicit
grouping, we could write our Turing Machines more easily.
...
mark_start [a-z] mark_start $1 L
mark_start _ mark_end S R
mark_end [a-z] mark_end $1 R
...
I don't doubt that there are other efficiencies we could impose on the
simple Turing Machine language, to create a better language, a better
Turing Machine. Yet, I think the point here is simply to explore the
Turing Machine for what it is, rather than turn it into a higher level
language. If we want that, we might as well stick with Ruby. (Still, a
generator to help us write lengthy Turing Machine programs, such as
was used for the 1500 line example, would be interesting.)
I'm going to look at Alpha Chen's solution this week; it's short and
simple, yet managed to surprise me a little. We start with the last
line: the "main" of the solution.
Turing.new(ARGV.shift, ARGV.shift).run if __FILE__ == $0
Chen creates a new Turing Machine, passing in the first two command
line arguments, but only if `__FILE__` (a constant containing the
filename) is equal to `$0`. This is a typical check made to see if we
are loading this module in an attempt to execute it, rather than
loading it from another module via the `require` mechanism.
Now to initializing the Turing class.
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
The initialization of `@tape` as a Hash I missed the first time
around. And it may seem strange to use a Hash to represent a tape,
since Array would seem the proper fit. Still, the use of Hash here is
clever to simplify other code later. It might not be a general purpose
trick; still, we're implementing a Turing Machine here, which is
hardly a critical application.
Initializing `@tape` is slightly more complex because of this. The
provided tape, if not nil, is broken into an array of characters by
use of `split(//)`, but this must then be iterated over and each
character inserted into the hash.
Reading the program rules is pretty simple. As each line is read in,
comments are first removed, and then blank lines are skipped via:
next if line =~ /^\s*$/
This regular expression matches the beginning of the line with `^`,
then end of the line with `$`, and any amount of whitespace with
`\s*`. If a blank line is found, `next` starts the next iteration of
the loop.
After the line is split into words, the program is stored in the
`@program` hash with this:
@program[line[0..1]] = line[2..4]
Chen's program hash is keyed by two elements: the current machine
state and the symbol under the machine head. These two items form a
more complete state of the machine and keying the hash by this
combined state makes for simple code later. To the hash, for that key,
is inserted the rest of the rule.
Running the machine in Chen's code is done as follows:
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
As mentioned above, looking up the next state requires keying into the
program with two pieces of information: the current state and the
symbol under the tape's head. If no entry can be found in the program,
`next_state` will be nil and the loop will end.
Otherwise, `next_state` is broken down into its three parts and
assigned to the appropriate portions of the Turing Machine. The
direction is used to update `@head`, either forward or backward one
cell. This is where the use of `@tape` as a Hash, rather than an
Array, simplifies the code. Chen no longer needs to check Array
boundaries, to see if the tape needs to be extended to either the left
or the right. Introducing a new "index" to `@tape` simply allocates
another Hash entry.
After the loop exits, the contents of the tape need to be output.
Because `@tape` is a hash, there is a temptation to call `Hash#values`
to get the content, but such is to be avoided, as I don't believe Ruby
guarantees the order of the values. To get the values out in order
along the tape, Chen uses `Hash#sort` with no block, which will sort
key-value pairs Since the keys are first in each of those pairs, and
the keys are the indices of the tape, the values will be sorted
correctly.
`map` is used to remove the keys and keep only the values, and `join`
binds them back together into a single string. The final bit is a
substitution attempting to strip off any external blanks, so only the
"useful" content of the tape is displayed. Chen's regular expression
(slightly corrected in the code shown above), removes all blanks
immediately after the start of the line _or_ immediately preceding the
end of the line.
Tomorrow, we'll do some simple spam prevention...
--
Matthew Moss <matthe...@gmail.com>
Alpha Chen
But a small nitpick... =)
On May 15, 11:26 am, Matthew Moss <matthew.m...@gmail.com> wrote:
> puts @tape.sort.map {|_,v| v}.join.gsub(/^_*|_*$/, '')
>
> "useful" content of the tape is displayed. Chen's regular expression
> (slightly corrected in the code shown above), removes all blanks
> immediately after the start of the line _or_ immediately preceding the
> end of the line.
Shouldn't the regex return "a" instead of "a_b" for "_a_b_"?
Matthew Moss
No... the intent was that blanks be removed from the ends, but
everything else retained.
Alpha Chen
Oops, my mistake! Goes to show how well I can read the spec...
Robert Dober
Cheers
Robert
--
http://ruby-smalltalk.blogspot.com/
---
Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein