Re: The Turing Machine (#162)

I was a little late submitting this week, so, rather than fleshing this
solution out, I just challenged myself to write a short but good
program. I think I did a pretty good job, at 33 lines of non-golfed
code.

Thanks to Andrew J. and his solution to RubyQuiz 69 for showing me
the trick of using hashes for lazy evaluation.

state = nil
instructions = File.open(ARGV[0]) do |f|
f.readlines.map{|s|
(s=s.match(/^[^#]+/)[0].strip).empty? ? nil :
s}.compact.
inject({}){|hsh,s|
md=s.match(/(\w+)\s+(\w)\s+(\w+)\s+(\w)\s+([LR])/)
state = state || md[1]
hsh[[md[1],md[2]]]=[md[3],md[4],md[5]]
hsh
}
end

tape = Hash.new do |cell,v|
h = cell.dup
h[:C] = ‘_’
h[v==‘L’ ? ‘R’ : ‘L’] = cell
cell[v] = h
end

tape[:C] = ‘_’
ARGV[1].to_s.split(//).reverse.each{|c|tape=tape[‘L’];tape[:C]=c}

until instructions[[state,tape[:C]]].nil?
state, ch, move = instructions[[state,tape[:C]]]
tape[:C] = ch
tape = tape[move]
end

tape = tape[‘L’] while tape.keys.include? ‘L’
output = [tape[:C]]
(tape = tape[‘R’]; output << tape[:C]) while tape.keys.include? ‘R’

puts output.reject{|c|c==’_’}.join

----- Original Message ----
From: Matthew M. [email protected]
To: ruby-talk ML [email protected]
Sent: Friday, May 9, 2008 10:48:40 AM
Subject: [QUIZ] The Turing Machine (#162)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q. 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 Q. 2 by submitting ideas as often as you can! (A
    permanent, new website is in the works for Ruby Q. 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 T. follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The Turing Machine

Quiz description by James Edward G. 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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs