From: Matthew Moss Date: 2008-05-16T03:26:44+09:00 Subject: [SUMMARY] The Turing Machine (#162) While waiting for 48 hours to pass, several examples of Turing Machine code were sent in, including one example of over 1,500 lines, generated by code. Most others were simpler, handcrafted rulesets and tapes, dealing primarily with the limited input set of binary numbers. This kept code size smaller and easier to understand. A thought occurred to me that we might make an Extended Turing Machine, so we would no longer have to eliminate very repetitive state information. To take a small portion of one example: ... mark_start v mark_start v L mark_start w mark_start w L mark_start x mark_start x L mark_start y mark_start y L mark_start z mark_start z L mark_start _ mark_end S R mark_end a mark_end a R mark_end b mark_end b R mark_end c mark_end c R mark_end d mark_end d R ... Using a regular expression for the second argument with an implicit grouping, we could write our Turing Machines more easily. ... mark_start [a-z] mark_start $1 L mark_start _ mark_end S R mark_end [a-z] mark_end $1 R ... I don't doubt that there are other efficiencies we could impose on the simple Turing Machine language, to create a better language, a better Turing Machine. Yet, I think the point here is simply to explore the Turing Machine for what it is, rather than turn it into a higher level language. If we want that, we might as well stick with Ruby. (Still, a generator to help us write lengthy Turing Machine programs, such as was used for the 1500 line example, would be interesting.) I'm going to look at Alpha Chen's solution this week; it's short and simple, yet managed to surprise me a little. We start with the last line: the "main" of the solution. Turing.new(ARGV.shift, ARGV.shift).run if __FILE__ == $0 Chen creates a new Turing Machine, passing in the first two command line arguments, but only if `__FILE__` (a constant containing the filename) is equal to `$0`. This is a typical check made to see if we are loading this module in an attempt to execute it, rather than loading it from another module via the `require` mechanism. Now to initializing the Turing class. def initialize(file, tape=nil) @tape = Hash.new('_') @head = 0 # initialize tape tape.split(//).each_with_index {|c,i| @tape[i] = c } if tape # read program instructions @program = Hash.new File.open(file).each_line do |line| line.gsub!(/#.*/, '') # remove comments next if line =~ /^\s*$/ # skip blank lines line = line.split(/\s+/) @state = line[0] if @state.nil? @program[line[0..1]] = line[2..4] end end The initialization of `@tape` as a Hash I missed the first time around. And it may seem strange to use a Hash to represent a tape, since Array would seem the proper fit. Still, the use of Hash here is clever to simplify other code later. It might not be a general purpose trick; still, we're implementing a Turing Machine here, which is hardly a critical application. Initializing `@tape` is slightly more complex because of this. The provided tape, if not nil, is broken into an array of characters by use of `split(//)`, but this must then be iterated over and each character inserted into the hash. Reading the program rules is pretty simple. As each line is read in, comments are first removed, and then blank lines are skipped via: next if line =~ /^\s*$/ This regular expression matches the beginning of the line with `^`, then end of the line with `$`, and any amount of whitespace with `\s*`. If a blank line is found, `next` starts the next iteration of the loop. After the line is split into words, the program is stored in the `@program` hash with this: @program[line[0..1]] = line[2..4] Chen's program hash is keyed by two elements: the current machine state and the symbol under the machine head. These two items form a more complete state of the machine and keying the hash by this combined state makes for simple code later. To the hash, for that key, is inserted the rest of the rule. Running the machine in Chen's code is done as follows: def run while next_state = @program[[@state, @tape[@head]]] @state, @tape[@head], dir = next_state @head += (dir == 'R') ? 1 : -1 end puts @tape.sort.map {|_,v| v}.join.gsub(/^_*|_*$/, '') end As mentioned above, looking up the next state requires keying into the program with two pieces of information: the current state and the symbol under the tape's head. If no entry can be found in the program, `next_state` will be nil and the loop will end. Otherwise, `next_state` is broken down into its three parts and assigned to the appropriate portions of the Turing Machine. The direction is used to update `@head`, either forward or backward one cell. This is where the use of `@tape` as a Hash, rather than an Array, simplifies the code. Chen no longer needs to check Array boundaries, to see if the tape needs to be extended to either the left or the right. Introducing a new "index" to `@tape` simply allocates another Hash entry. After the loop exits, the contents of the tape need to be output. Because `@tape` is a hash, there is a temptation to call `Hash#values` to get the content, but such is to be avoided, as I don't believe Ruby guarantees the order of the values. To get the values out in order along the tape, Chen uses `Hash#sort` with no block, which will sort key-value pairs Since the keys are first in each of those pairs, and the keys are the indices of the tape, the values will be sorted correctly. `map` is used to remove the keys and keep only the values, and `join` binds them back together into a single string. The final bit is a substitution attempting to strip off any external blanks, so only the "useful" content of the tape is displayed. Chen's regular expression (slightly corrected in the code shown above), removes all blanks immediately after the start of the line _or_ immediately preceding the end of the line. Tomorrow, we'll do some simple spam prevention... -- Matthew Moss