From: Chris Shea Date: 2008-05-10T04:30:07+09:00 Subject: Re: The Turing Machine (#162) On May 9, 9:48 am, Matthew Moss 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 > > . > > 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