Sample solutions and discussion Perl Quiz of The Week #24 (20040915) There were 14 Perl solutions, one in Python, one in Ruby, and a whole bunch of interesting Turing Machines contributed -- I was thrilled by the play this quiz inspired. Here's my solution, with annotations: #!/usr/bin/perl use strict; use warnings; my ($filename, $input) = @ARGV; die "Usage: $0 filename [input]" if !defined $filename or @ARGV > 2; Make sure the program has exactly 1 or 2 input parameters. my (%table, $state, @tape, $head); Define the Turing Machine's basic elements as global variables. my %movehead = (L => -1, R => 1); Initialize a hash for converting the state transition table's direction symbol to a value suitable for adding to an array subscript. open (FH, $filename) or die "Can't open $filename: $!"; while () { Open and start reading the state transition file. next if !/\S/ or /^\s*#/; Skip all-blank and blank-but-for-comment lines. chomp; my ($cur_state, $cur_symbol, $new_state, $new_symbol, $dir) = /^\s*(\w+)\s+(\w)\s+(\w+)\s+(\w)\s+(L|R)(?:\s*#.*)?/ or die "Bad instruction at $filename line $.: $_"; Use a complicated regexp to parse the line, error-checking at the same time. $state = $cur_state unless defined $state; Set the initial state. $table{$cur_state, $cur_symbol} = [$new_state, $new_symbol, $movehead{$dir}]; Load the %table hash with an arrayref consisting of the corresponding info. $table{$cur_state, $cur_symbol} is equivalent to $table{join $;, $cur_state, $cur_symbol}. In Perl 4, this was the usual implementation of multidimensional arrays; it can still be a convenient way to simulate a hash whose keys have multiple parts. } close (FH); die "No instructions present in $filename" unless defined $state; Die if there was no state table (which also means there's no current state.) @tape = defined $input ? split //, $input : ('_'); The tape is implemented as an ordinary Perl array, which will be extended in either direction as necessary. Initialize the tape to the input string or a single '_' character. $head = 0; Initialize $head, the current position of the tape, which will be used as a subscript to @tape. while (defined (my $instruction = $table{$state, $tape[$head]})) { This is the Turing Machine algorithm. While there is a state transition defined for the current state and the current character... my $move; ($state, $tape[$head], $move) = @$instruction; $head += $move; Change the state to the new state; write the new character to the tape; move the head. push @tape, '_' if $head > $#tape; # grow tape to the right unshift @tape, '_' and $head++ if $head < 0; # grow tape to the left Extend the tape to either direction, if necessary. } If the loop exits, there was no transition defined for the current state and current character, so the Turing Machine should halt. shift @tape while @tape and $tape[0] eq '_'; pop @tape while @tape and $tape[-1] eq '_'; Clean up '_' characters from both sides of the tape. print join '', @tape, "\n"; Print the contents of the tape. As some early respondents noted, this quiz was simpler than it might have seemed at first glimpse. A Turing Machine's definition spells out the algorithm that will drive any implementation. Two major points on which the submissions differed were the data structure of the state table and the implementation of the infinite tape. (I was happy to see the Python and Ruby submissions, but as I don't speak those languages, I'm not going to comment on their internals.) For the data structure, a hash of hashrefs whose values were arrayrefs was most popular, used by Burton West, Dominus, Ericson, Fuglerud, Modi, Nielsen, and Sanderson. For instance, from Dominus' program: $transition{$instate}{$intape} = [$outstate, $outtape, $motion{$motion}]; Instead of arrayrefs, Pletinckx, Rafferty, Tucker, and Varga used a hashref so they could name the values, as shown by Rafferty's program: $states{$start}{$input} = { end => $end, output => $output, dir => $dir }; Kimball's program, which uses only Llama Book features, used a hash whose key contains the state name and current symbol delimited by a space, and whose value was space delimited string of the next state, next symbol, and direction. $instructions{"$current_state $current_char"} = "$new_state $new_char $direction"; (This program is available at http://perl.plover.com/qotw/misc/r024/kimball.pl ) Dominus outlined some approaches to representing the infinite tape: http://perl.plover.com/~alias/list.cgi?1:mss:2230 >Getting an infinite tape is not as difficult as some people seemed to >think it would be. There are at least three techniques that occurred >to me. One would be to have > > TAPE(n) is stored in $tape[1 - 2*$n] when n < 0 > in $tape[ 2*$n] when n >= 0 > >and an alternative would use this as a backend to a tied array which >would interpret the negative subscripts transparently. > >A third way is the way I did it in this program, which I think is >simple and elegant. Most people used that third way (Dominus, Ericson, Fuglerud, Pletinckx, Quint, Sanderson, Tucker, and myself, as shown above.) [ MJD: I should have pointed out that the tied array technique can also be used in conjunction with the third approach, so that I really listed either two or four techniques, depending on how you count. ] Everyone else came up with still more ways. Burton West, Kimball, Nielsen, and Varga used a hash; Rafferty used an object based an a hash. Modi used a string. To test the programs' behavior on good programs, I used binary_incr.tm, hello_world.tm (complete with typo), and multiply.tm (unary multiplication) from the examples in the quiz, plus the binary_add, stack and parens tm's that people submitted to qotw-discuss, plus the following: echo.tm: s0 _ s1 _ R This should just echo the input string. If passed nothing, or if passed a string containing only '_' characters, it should print nothing. 0.tm: 0 1 0 1 R 0 0 0 0 R 0 _ 1 _ L 1 1 1 0 L 1 0 2 1 L 1 _ 2 1 L 2 1 2 1 L 2 0 2 0 L 2 _ 3 _ R This is binary_incr with a state named 0. As Dominus noted, if a program depends on the truth of a state name as opposed to whether it's defined, it will fail for this valid case. And two more tests suggested by discussion on qotw-discuss. nostate1.tm: A 1 B 1 L This should work the same as echo. nostate2.tm a _ b 1 R b _ c _ R c _ d _ R d _ e _ R e X stop X R If there was no input string, output 1. If the input string begins with a blank, replace the blank with a 1 and print it. Otherwise, just print the input string. Finally, I tested them on a series of invalid inputs, for which they should die: bad1.tm: a@ a b 1 R # bad state name bad2.tm: a b c d q # bad direction bad3.tm a ? b c L # bad current symbol bad4.tm a b c $ L # bad new symbol bad5.tm a b * c L # bad new state bad6.tm a a a a # no more! bad7.tm 1 2 3 4 5 6 7 # too many elements Finally, I tested them on empty.tm, which was an empty file. The specification did not make explicit what the behavior in this case should be. From the definition of a Turing Machine, I think it's most sensible to consider this an error case: a Turing Machine must have a state transition table and a current state. But I don't consider any particular behavior correct or incorrect for this case, as it wasn't defined. Some of the programs went into infinite loops. In some cases, I'm giving people credit for dying when I shouldn't because I broke out of my test program while it was running a submission that was in an infinite loop. The solutions of Dalke, Tucker, Rafferty, Ericson, Gray, Kimball, and Quint passed all of the tests. Of the remaining submissions, one didn't parse comments. A couple of them didn't correctly strip leading and trailing underscores. echo.tm posed a problem for some, as did dealing with state names of '0' or input of '0'. The nostate tms were also a common source of trouble. One went into an infinite loop if it ended with a blank tape. So though Turing Machines are simple, getting everything right in an implementation of even a simple thing isn't easy. My testing program, the tm files, the verbose results, and everyone's submissions are available from http://perl.plover.com/qotw/misc/r024/ for those who'd like to play along at home. Note that the testing program goes into infinite loops when the submissions do. Thanks to everyone who participated (including those who didn't submit solutions.)