Re: [SPOILER] Perl Quiz of the Week #24 (Turing Machine simulation)

On Fri, Sep 17, 2004 at 10:26:42AM -0400, Mark Jason Dominus wrote:
> Here's mine.  I probably spent as much time fussing with the format of
> the debugging output as I did with the rest of the program combined.

I've found the debugging output in your implementation to be very useful.
In my own program I indicated the head position by printing a caret under
it on the following line, but enclosing the head position on a single line
makes it much easier to visually track head movements between cycles.

One very minor bug I noticed was that if the head is at the rightmost
defined tape cell, the trailing ">" character is not displayed.  Perhaps
the simplest workaround is to extend the tape preemptively in debug mode,
ensuring the head always stays one position before the end:

	--- mjd-orig    Sat Sep 18 18:28:58 2004
	+++ mjd+mct     Sat Sep 18 18:37:58 2004
	@@ -24,6 +24,7 @@
	 while (my $ttab = $transition{$STATE}) {

	   if ($ENV{DEBUG}) {
	+    push @TAPE, "_" if $HEAD == $#TAPE;
	     print sprintf("%5s: ", $STATE);

While using your implementation to debug Turing programs, I discovered an
additional small bug.  If in a given state there is no state table entry
matching the tape cell under the head, the program exits as expected, but
only after erasing the cell (setting it to undef).  For example, if the
Turing program:

	A 1 B 1 L

is given an initial tape of "0", it will output "" rather than "0".  One
possible workaround is:

	--- mjd-orig    Sat Sep 18 18:28:58 2004
	+++ mjd+mct     Sat Sep 18 18:21:57 2004
	@@ -34,7 +34,10 @@
	   }

	   my $inc;
	-  ($STATE, $TAPE[$HEAD], $inc) = @{$ttab->{$TAPE[$HEAD]}};
	+  my $foo;
	+  ($STATE, $foo, $inc) = @{$ttab->{$TAPE[$HEAD]}};
	+  last unless defined $foo;
	+  $TAPE[$HEAD] = $foo;
	   $HEAD += $inc;

	   # Extend the tape

-mct

-- 
perl -e'$u="\4\5\6";sub H{8*($_[1]%79)+($_[0]%8)}sub G{vec$u,H(@_),1}sub S{vec
($n,H(@_),1)=$_[2]}$_=q^{P`clear`;for$iX){PG($iY)?"O":" "forX8);P"\n"}for$iX){
forX8){$c=scalar grep{G@$_}[$i-1Y-1Z-1YZ-1Y+1ZY-1ZY+1Z+1Y-1Z+1YZ+1Y+1];S$iY,G(
$iY)?$c=~/[23]/?1:0:$c==3?1:0}}$u=$n;select$M,$C,$T,.2;redo}^;s/Z/],[\$i/g;s/Y
/,\$_/xg;s/X/(0..7/g;s/P/print+/g;eval' #     Michael C. Toren <[email protected]>