From: Juanger Date: 2008-05-12T08:28:28+09:00 Subject: Re: [QUIZ] The Turing Machine (#162) ------=_Part_1614_23836468.1210548507872 Content-Type: multipart/alternative; boundary="----=_Part_1615_22713097.1210548507873" ------=_Part_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 wrote: > -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D- > > 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 > > . > > 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. > > -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D- > > ## 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 > > > --=20 Ash Mac durbatul=FBk, ash Mac gimbatul, ash Mac thrakatul=FBk agh burzum-is= hi krimpatul. Juanger. ------=_Part_1615_22713097.1210548507873 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline I attached my solution.

On Fri, May 9, 20= 08 at 10:48 AM, Matthew Moss <matthew.moss@gmail.com> wrote:
-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

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.

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

## 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 characte= r
each, with a
     read/write head that points to one of these cells at a= ny given
time.  The
     tape is filled with an infinite run of blank character= s 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 curren= t
character under
     head of the tape.  That instruction will provide = a state for
the
     register, a character to place in the current memory c= ell, 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<= br> 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,<= br> 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 pali= ndrome.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=FBk, a= sh Mac gimbatul, ash Mac thrakatul=FBk agh burzum-ishi krimpatul.
Juange= r. ------=_Part_1615_22713097.1210548507873-- ------=_Part_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== ------=_Part_1614_23836468.1210548507872--