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);
}

Labels: ,

If you enjoyed this blog post, you might enjoy my travel book for people interested in science and technology: The Geek Atlas. Signed copies of The Geek Atlas are available.

<$BlogCommentBody$>

<$BlogCommentDateTime$> <$BlogCommentDeleteIcon$>

Post a Comment

Links to this post:

<$BlogBacklinkControl$> <$BlogBacklinkTitle$> <$BlogBacklinkDeleteIcon$>
<$BlogBacklinkSnippet$>
Create a Link

<< Home