And here's mine. http://pastie.caboo.se/195332 I use two array to simulate the tape. On Fri, May 9, 2008 at 11:48 PM, 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 > > > -- pluskid