------ 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 <<a href="mailto:matthew.moss / gmail.com" target="_blank">matthew.moss / gmail.com</a>> 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. 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. 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> <<a href="http://matthew.moss.googlepages.com/home" target="_blank">http://matthew.moss.googlepages.com/home</a>>.<br> <br> 3. Enjoy!<br> <br> Suggestion: A [QUIZ] in the subject of emails about the problem<br> helps everyone on Ruby Talk follow the discussion. 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. 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'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> * A single state register.<br> * An infinite tape of memory cells that can hold one character<br> each, with a<br> read/write head that points to one of these cells at any given<br> time. The<br> tape is filled with an infinite run of blank characters in<br> either<br> direction.<br> * A finite set of program instructions. The program is just a big<br> table of<br> state transitions. The Turing Machine will look up an<br> instruction based<br> the current value of the state register and the current<br> character under<br> head of the tape. That instruction will provide a state for<br> the<br> register, a character to place in the current memory cell, and<br> an order to<br> move the head to the left or the right.<br> <br> To keep our Turning Machine simple, let'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/`. We will<br> call our blank tape cell character the underscore.<br> <br> Program lines will be of the form:<br> <br> CurrentState _ NewState C R<br> <br> The above translates to: 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. All five elements will be present in each<br> line and separated by one or more whitespace characters. 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. 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. 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's a sample run of a simple program through my Turing Machine so<br> you can see how this plays out:<br> <br> $ cat <a href="http://palindrome.tm" target="_blank">palindrome.tm</a><br> # Report whether a string of 0 and 1 (ie. a binary<br> # number) is a palindrome.<br> look_first 0 go_end_0 _ R<br> look_first 1 go_end_1 _ R<br> look_first _ write_es Y R<br> go_end_0 0 go_end_0 0 R<br> go_end_0 1 go_end_0 1 R<br> go_end_0 _ check_end_0 _ L<br> go_end_1 0 go_end_1 0 R<br> go_end_1 1 go_end_1 1 R<br> go_end_1 _ check_end_1 _ L<br> check_end_0 0 ok_rewind _ L<br> check_end_0 1 fail_rewind _ L<br> check_end_0 _ ok_rewind _ L<br> check_end_1 0 fail_rewind _ L<br> check_end_1 1 ok_rewind _ L<br> check_end_1 _ ok_rewind _ L<br> ok_rewind 0 ok_rewind 0 L<br> ok_rewind 1 ok_rewind 1 L<br> ok_rewind _ look_first _ R<br> fail_rewind 0 fail_rewind _ L<br> fail_rewind 1 fail_rewind _ L<br> fail_rewind _ write_o N R<br> write_es _ write_s e R<br> write_o _ done nbsp; o R<br> write_s _ done nbsp; s R<br> <br> $ ruby tm.rb <a href="http://palindrome.tm" target="_blank">palindrome.tm</a> 011010110<br> Yes<br> <br> $ ruby tm.rb <a href="http://palindrome.tm" target="_blank">palindrome.tm</a> 01101<br> 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--