------art_1614_23836468.1210548507872
Content-Type: multipart/alternative; 
	boundary---art_1615_22713097.1210548507873"

------art_1615_22713097.1210548507873
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I attached my solution.

On Fri, May 9, 2008 at 10:48 AM, Matthew Moss <matthew.moss / 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
>
>
>


-- 
Ash Mac durbatulū°, ash Mac gimbatul, ash Mac thrakatulū° agh burzum-ishi
krimpatul.
Juanger.

------art_1615_22713097.1210548507873
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I attached my solution.<br><br><div class="gmail_quote">On Fri, May 9, 2008 at 10:48 AM, Matthew Moss &lt;<a href="mailto:matthew.moss / gmail.com" target="_blank">matthew.moss / gmail.com</a>&gt; wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-<br>
<br>
The three rules of Ruby Quiz 2:<br>
<br>
1. &nbsp;Please do not post any solutions or spoiler discussion for this<br>
quiz until 48 hours have passed from the time on this message.<br>
<br>
2. &nbsp;Support Ruby Quiz 2 by submitting ideas as often as you can! (A<br>
permanent, new website is in the works for Ruby Quiz 2. Until then,<br>
please visit the temporary website at<br>
<br>
 &nbsp; &nbsp; &lt;<a href="http://matthew.moss.googlepages.com/home" target="_blank">http://matthew.moss.googlepages.com/home</a>&gt;.<br>
<br>
3. &nbsp;Enjoy!<br>
<br>
Suggestion: &nbsp;A [QUIZ] in the subject of emails about the problem<br>
helps everyone on Ruby Talk follow the discussion. &nbsp;Please reply to<br>
the original quiz message, if you can.<br>
<br>
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-<br>
<br>
## The Turing Machine<br>
<br>
_Quiz description by James Edward Gray II_<br>
<br>
The Turing Machine is a simple computing architecture dating all the<br>
way back to the 1930s. &nbsp;While extremely primitive compared to any<br>
modern machine, there has been a lot of research showing that a Turing<br>
Machine is capable of just about anything the fancier machines can do<br>
(although much less efficiently, of course).<br>
<br>
This week&#39;s task is to build a Turing Machine, so we can play around<br>
with the architecture.<br>
<br>
A Turing Machine has but three simple parts:<br>
<br>
 &nbsp; &nbsp;* A single state register.<br>
 &nbsp; &nbsp;* An infinite tape of memory cells that can hold one character<br>
each, with a<br>
 &nbsp; &nbsp; &nbsp;read/write head that points to one of these cells at any given<br>
time. &nbsp;The<br>
 &nbsp; &nbsp; &nbsp;tape is filled with an infinite run of blank characters in<br>
either<br>
 &nbsp; &nbsp; &nbsp;direction.<br>
 &nbsp; &nbsp;* A finite set of program instructions. &nbsp;The program is just a big<br>
table of<br>
 &nbsp; &nbsp; &nbsp;state transitions. &nbsp;The Turing Machine will look up an<br>
instruction based<br>
 &nbsp; &nbsp; &nbsp;the current value of the state register and the current<br>
character under<br>
 &nbsp; &nbsp; &nbsp;head of the tape. &nbsp;That instruction will provide a state for<br>
the<br>
 &nbsp; &nbsp; &nbsp;register, a character to place in the current memory cell, and<br>
an order to<br>
 &nbsp; &nbsp; &nbsp;move the head to the left or the right.<br>
<br>
To keep our Turning Machine simple, let&#39;s say that our state register<br>
can contain words matching the regular expression `/\w+/` and the tape<br>
only contains characters that match the expression `/\w/`. &nbsp;We will<br>
call our blank tape cell character the underscore.<br>
<br>
Program lines will be of the form:<br>
<br>
 &nbsp; &nbsp;CurrentState _ NewState C R<br>
<br>
The above translates to: &nbsp;if the current state is CurrentState and the<br>
character under the tape head is our blank character, set the state to<br>
NewState, replace the blank character with a C, and move the tape head<br>
to the right one position. &nbsp;All five elements will be present in each<br>
line and separated by one or more whitespace characters. &nbsp;Allow for<br>
trailing comments (using #) on a line, comment only lines, and blank<br>
lines in the program by ignoring all three.<br>
<br>
The initial state of your Turing machine should be set to the<br>
CurrentState mentioned on the first line of the program. &nbsp;Optionally,<br>
the initial contents of the tape can be provided when the program is<br>
load, but it will default to an all blank tape. &nbsp;The program runs<br>
until it fails to find an instruction for the CurrentState and the<br>
character currently under the tape head, at which point it prints the<br>
current contents of the tape head from the first non-blank character<br>
to the last non-blank character and exits.<br>
<br>
Here&#39;s a sample run of a simple program through my Turing Machine so<br>
you can see how this plays out:<br>
<br>
 &nbsp; &nbsp;$ cat <a href="http://palindrome.tm" target="_blank">palindrome.tm</a><br>
 &nbsp; &nbsp;# Report whether a string of 0 and 1 (ie. a binary<br>
 &nbsp; &nbsp;# number) is a palindrome.<br>
 &nbsp; &nbsp;look_first &nbsp; 0 &nbsp;go_end_0 &nbsp; &nbsp; _ &nbsp;R<br>
 &nbsp; &nbsp;look_first &nbsp; 1 &nbsp;go_end_1 &nbsp; &nbsp; _ &nbsp;R<br>
 &nbsp; &nbsp;look_first &nbsp; _ &nbsp;write_es &nbsp; &nbsp; Y &nbsp;R<br>
 &nbsp; &nbsp;go_end_0 &nbsp; &nbsp; 0 &nbsp;go_end_0 &nbsp; &nbsp; 0 &nbsp;R<br>
 &nbsp; &nbsp;go_end_0 &nbsp; &nbsp; 1 &nbsp;go_end_0 &nbsp; &nbsp; 1 &nbsp;R<br>
 &nbsp; &nbsp;go_end_0 &nbsp; &nbsp; _ &nbsp;check_end_0 &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;go_end_1 &nbsp; &nbsp; 0 &nbsp;go_end_1 &nbsp; &nbsp; 0 &nbsp;R<br>
 &nbsp; &nbsp;go_end_1 &nbsp; &nbsp; 1 &nbsp;go_end_1 &nbsp; &nbsp; 1 &nbsp;R<br>
 &nbsp; &nbsp;go_end_1 &nbsp; &nbsp; _ &nbsp;check_end_1 &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;check_end_0 &nbsp;0 &nbsp;ok_rewind &nbsp; &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;check_end_0 &nbsp;1 &nbsp;fail_rewind &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;check_end_0 &nbsp;_ &nbsp;ok_rewind &nbsp; &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;check_end_1 &nbsp;0 &nbsp;fail_rewind &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;check_end_1 &nbsp;1 &nbsp;ok_rewind &nbsp; &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;check_end_1 &nbsp;_ &nbsp;ok_rewind &nbsp; &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;ok_rewind &nbsp; &nbsp;0 &nbsp;ok_rewind &nbsp; &nbsp;0 &nbsp;L<br>
 &nbsp; &nbsp;ok_rewind &nbsp; &nbsp;1 &nbsp;ok_rewind &nbsp; &nbsp;1 &nbsp;L<br>
 &nbsp; &nbsp;ok_rewind &nbsp; &nbsp;_ &nbsp;look_first &nbsp; _ &nbsp;R<br>
 &nbsp; &nbsp;fail_rewind &nbsp;0 &nbsp;fail_rewind &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;fail_rewind &nbsp;1 &nbsp;fail_rewind &nbsp;_ &nbsp;L<br>
 &nbsp; &nbsp;fail_rewind &nbsp;_ &nbsp;write_o &nbsp; &nbsp; &nbsp;N &nbsp;R<br>
 &nbsp; &nbsp;write_es &nbsp; &nbsp; _ &nbsp;write_s &nbsp; &nbsp; &nbsp;e &nbsp;R<br>
 &nbsp; &nbsp;write_o &nbsp; &nbsp; &nbsp;_ &nbsp;done &nbsp; &nbsp; &nbsp;nbsp; o &nbsp;R<br>
 &nbsp; &nbsp;write_s &nbsp; &nbsp; &nbsp;_ &nbsp;done &nbsp; &nbsp; &nbsp;nbsp; s &nbsp;R<br>
<br>
 &nbsp; &nbsp;$ ruby tm.rb <a href="http://palindrome.tm" target="_blank">palindrome.tm</a> 011010110<br>
 &nbsp; &nbsp;Yes<br>
<br>
 &nbsp; &nbsp;$ ruby tm.rb <a href="http://palindrome.tm" target="_blank">palindrome.tm</a> 01101<br>
 &nbsp; &nbsp;No<br>
<br>
<br>
</blockquote></div><br><br clear="all"><br>-- <br>Ash Mac durbatulū°, ash Mac gimbatul, ash Mac thrakatulū° agh burzum-ishi krimpatul.<br>Juanger.

------art_1615_22713097.1210548507873--

------art_1614_23836468.1210548507872
Content-Type: text/x-ruby-script; name=tm.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_fg49adsg0
Content-Disposition: attachment; filename=tm.rb

Y2xhc3MgVHVyaW5nTWFjaGluZQogIAogIGF0dHJfYWNjZXNzb3IgOnRhcGUKICAKICBkZWYgaW5p
dGlhbGl6ZShpbnN0cnVjdGlvbnMsIGlucHV0ID0gIiIpCiAgICBAbW92ZSA9IHsiUiIgPT4gOnJp
Z2h0LCAiTCIgPT4gOmxlZnR9ICMgVHJhbnNsYXRvciBmb3IgUiBhbmQgTAogICAgQHRhcGUgPSBU
YXBlLm5ldyhpbnB1dCkgICAgICAgICAgICAgICAjIFRoZSBpbmZpbml0ZSB0YXBlCiAgICBAaGVh
ZCA9IEB0YXBlLmhlYWQgICAgICAgICAgICAgICAgICAgICMgVGhlIHJlYWRpbmctd3JpdGluZyBo
ZWFkCiAgICBAZGVsdGEgPSBIYXNoLm5ldyAgICAgICAgICAgICAgICAgICAgICMgT3VyIGRlbHRh
IGZ1bmN0aW9uIAogICAgQHN0YXRlID0gbmlsICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRo
ZSBjdXJyZW50IHN0YXRlCiAgICBmaWxsX2RlbHRhKGluc3RydWN0aW9ucykKICAgIHJ1bgogIGVu
ZAoKICBwcml2YXRlCiAgCiAgIyBGaWxscyB0aGUgZGVsdGEgZnVuY3Rpb24gaGFzaAogIGRlZiBm
aWxsX2RlbHRhKGluc3RydWN0aW9ucykKICAgIGlmIEZpbGUuZmlsZT8gaW5zdHJ1Y3Rpb25zCiAg
ICAgIG9wZW4oaW5zdHJ1Y3Rpb25zLCAiciIpIHsgfGZpbGV8CiAgICAgICAgaSA9IDAKICAgICAg
ICBmaWxlLmVhY2ggeyB8bGluZXwKICAgICAgICAgIG5leHQgaWYgbGluZSA9fiAvXigjLiopPyQv
CiAgICAgICAgICBwYXJzZV9ydWxlKGxpbmUsIGkgPT0gMCkKICAgICAgICAgIGkgKz0gMQogICAg
ICAgIH0KICAgICAgfQogICAgZW5kCiAgZW5kCgogICMgRGVmaW5lcyB0aGUga2V5cy92YWx1ZXMg
Zm9yIHRoZSBoYXNoCiAgZGVmIHBhcnNlX3J1bGUocnVsZV9saW5lLCBmaXJzdCA9IGZhbHNlKQog
ICAgcnVsZSA9IHJ1bGVfbGluZS5zcGxpdAogICAgQGRlbHRhW1tydWxlWzBdLCBydWxlWzFdXV0g
PSBbcnVsZVsyXSwgcnVsZVszXSwgcnVsZVs0XV0KICAgIEBzdGF0ZSA9IHJ1bGVbMF0gaWYgZmly
c3QgICAjIGluaXRpYWwgdmFsdWUgZm9yIEBzdGF0ZQogIGVuZAogIAogICMgR28gVHVyaW5nTWFj
aGluZSwgR28hIQogIGRlZiBydW4KICAgIHN0ZXAgPSBAZGVsdGFbW0BzdGF0ZSxAaGVhZC5jaGFy
XV0gIyBDYWxjdWxhdGVzIHRoZSBuZXh0IHN0ZXAKICAgIHdoaWxlIHN0ZXAKICAgICAgQHN0YXRl
ID0gc3RlcFswXQogICAgICBAaGVhZC5jaGFyID0gc3RlcFsxXQogICAgICBAaGVhZCA9IEBoZWFk
LnNlbmQoQG1vdmVbc3RlcFsyXV0pCiAgICAgIHN0ZXAgPSBAZGVsdGFbW0BzdGF0ZSxAaGVhZC5j
aGFyXV0KICAgIGVuZAogICAgQHRhcGUuZGlzcGxheSAgIyBQcmludCB0aGUgdGFwZQogIGVuZAog
IAplbmQKCmNsYXNzIFRhcGUKICAKICBhdHRyX2FjY2Vzc29yIDpoZWFkCiAgCiAgZGVmIGluaXRp
YWxpemUoaW5wdXQpCiAgICBpZiBpbnB1dC5zaXplID4gMAogICAgICBpID0gMAogICAgICBsYXN0
ID0gbmlsCiAgICAgIGFjdHVhbCA9IG5pbAogICAgICBpbnB1dC5zY2FuKC8uL20pIHsgfGN8ICMg
Q3JlYXRlIHRoZSBDZWxscyBhbmQgbGluayB0aGVtCiAgICAgICAgYWN0dWFsID0gQ2VsbC5uZXco
YykKICAgICAgICBpZiBpID09IDAKICAgICAgICAgIEBoZWFkID0gbGFzdCA9IGFjdHVhbAogICAg
ICAgIGVsc2UKICAgICAgICAgIGxhc3QucmlnaHQgPSBhY3R1YWwKICAgICAgICAgIGFjdHVhbC5s
ZWZ0ID0gbGFzdAogICAgICAgICAgbGFzdCA9IGFjdHVhbAogICAgICAgIGVuZAogICAgICAgIGkg
Kz0gMQogICAgICB9CiAgICBlbHNlCiAgICAgIEBoZWFkID0gQ2VsbC5uZXcoIl8iKQogICAgZW5k
CiAgZW5kCiAgCiAgIyBQcmludCB0aGUgbm9uLWJsYW5rIGNvbnRlbnRzIG9mIHRoZSB0YXBlCiAg
ZGVmIGRpc3BsYXkKICAgIHVudGlsIEBoZWFkLmxlZnRfYm91bmRhcnk/ICMgcmV3aW5kIHRvIHRo
ZSBiZWdpbmluZwogICAgICBAaGVhZCA9IEBoZWFkLmxlZnQKICAgIGVuZAogICAgdW50aWwgQGhl
YWQucmlnaHRfYm91bmRhcnk/ICMgcHJpbnQgZWFjaCBjaGFyIHRvIHRoZSBlbmQKICAgICAgcHJp
bnQgQGhlYWQuY2hhciB1bmxlc3MgQGhlYWQuY2hhciA9PSAiXyIKICAgICAgQGhlYWQgPSBAaGVh
ZC5yaWdodAogICAgZW5kCiAgICBwdXRzICIiCiAgZW5kCiAgCmVuZAoKY2xhc3MgQ2VsbAogIAog
IGF0dHJfYWNjZXNzb3IgOmNoYXIKICBhdHRyX3dyaXRlciA6cmlnaHQsIDpsZWZ0CiAgCiAgZGVm
IGluaXRpYWxpemUoY2hhciwgbGVmdCA9IG5pbCwgcmlnaHQgPSBuaWwpCiAgICBAY2hhciA9IGNo
YXIKICAgIEByaWdodCA9IHJpZ2h0CiAgICBAbGVmdCA9IGxlZnQKICBlbmQKICAKICAjIEdldCB0
aGUgY2VsbCBhdCB0aGUgcmlnaHQKICAjIENyZWF0ZXMgYSBjZWxsIHdpdGggYSBibGFuayBjaGFy
YWN0ZXIgYXMgbmVlZGVkCiAgZGVmIHJpZ2h0CiAgICB1bmxlc3MgQHJpZ2h0CiAgICAgIEByaWdo
dCA9IENlbGwubmV3KCJfIiwgc2VsZiwgbmlsKQogICAgZW5kCiAgICBAcmlnaHQKICBlbmQKICAK
ICAjIEdldCB0aGUgY2VsbCBhdCB0aGUgbGVmdAogICMgQ3JlYXRlcyBhIGNlbGwgd2l0aCBhIGJs
YW5rIGNoYXJhY3RlciBhcyBuZWVkZWQgIAogIGRlZiBsZWZ0CiAgICB1bmxlc3MgQGxlZnQKICAg
ICAgQGxlZnQgPSBDZWxsLm5ldygiXyIsIG5pbCwgc2VsZikKICAgIGVuZAogICAgQGxlZnQKICBl
bmQKICAKICAjIElzIGl0IHRoZSBmaXJzdCBkZWZpbmVkIGNlbGwgaW4gdGhlIHRhcGU/PwogIGRl
ZiBsZWZ0X2JvdW5kYXJ5PwogICAgdW5sZXNzIEBsZWZ0CiAgICAgIHRydWUKICAgIGVsc2UgCiAg
ICAgIGZhbHNlIAogICAgZW5kCiAgZW5kCiAgCiAgIyBJcyBpdCB0aGUgbGFzdCBkZWZpbmVkIGNl
bGwgaW4gdGhlIHRhcGU/PwogIGRlZiByaWdodF9ib3VuZGFyeT8KICAgIHVubGVzcyBAcmlnaHQK
ICAgICAgdHJ1ZQogICAgZWxzZQogICAgICBmYWxzZQogICAgZW5kCiAgZW5kCmVuZAoKY2FzZSBB
UkdWLnNpemUKd2hlbiAwCiAgcHV0cyAiSSBuZWVkIGEgcHJvZ3JhbSAhISIKd2hlbiAxCiAgdG0g
PSBUdXJpbmdNYWNoaW5lLm5ldyhBUkdWWzBdKQp3aGVuIDIKICB0bSA9IFR1cmluZ01hY2hpbmUu
bmV3KEFSR1ZbMF0sIEFSR1ZbMV0pCmVuZA------art_1614_23836468.1210548507872--