On May 9, 9:48 am, Matthew Moss <matthew.m...@[...].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

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