On May 9, 9:48 am, Matthew Moss <matthew.m... / gmail.com> 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

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