Monday, June 25, 2012

What the final Turing Machine Google Doodle does

If you solved the puzzles in the Google Doodle commemorating Alan Turing's 100th birthday and clicked on the rabbit you'd get to see the machine performing this program starting with a blank tape.

Translating that into pseudo-code you obtain the following:
```one

do
if one
blank

do
right
while not blank

one
right
zero

while not blank
left
end

one
right
else
blank

do
right
while not blank

one

while not blank
left
end

zero
right
end
end
```
There one, zero and blank each write those symbols to the same; when used in an if or while they test for the presence of a symbol.  Right and left move the tape one square left or right.

The two branches of the main if there are doing very similar things.  They both blank out the current square, then move right until they find blank space and write 1 0 or 1 depending on whether the original square examined in the if was 1 or 0.  Then the tape is moved back to the blank and the original number 1 or 0 replaced.

So, it's extending the sequence on the tape by 1 0 or 1 depending on whether the number it sees is 1 or 0.

Each time around the outer loop the tape changes as follows:
```1
1 1 0
1 1 0 1 0
1 1 0 1 0 1
1 1 0 1 0 1 1 0
1 1 0 1 0 1 1 0 1
1 1 0 1 0 1 1 0 1 1 0
1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 0 1 0 1 1 0 1 1 0 1 0 1
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0
```
This program appears to be calculating the rabbit sequence 1, 10, 101, 10110, ... and writing it out onto the tape.

And here's a little Perl program the simulates the Turing machine in the Google Doodle:
```use strict;
use warnings;

my @tape;
my \$pos = 0;

one();

do {
dump_tape();

if ( is_one() ) {
blank();
do { right() } while ( !is_blank() );

one(); right(); zero();

while ( !is_blank() ) { left() }

one();
} else {
blank();
do { right() } while ( !is_blank() );

one();

while ( !is_blank() ) { left() }

zero();
}

right();
} while(1);

sub zero  { x('0') }
sub one   { x('1') }
sub blank { x(' ') }
sub x     { \$tape[\$pos] = \$_[0] }

sub is_blank { is(' ') }
sub is_one   { is('1') }
sub is       { \$tape[\$pos] eq \$_[0] }

sub right
{
if ( \$pos == \$#tape ) {
push @tape, (' ');
}
\$pos += 1;
}
sub left  { \$pos -= 1 }

sub dump_tape
{
print join( ' ', @tape ), "\n";
sleep(1);
}
```