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:
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:
And here's a little Perl program the simulates the Turing machine in the Google Doodle:
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 endThere 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 0This 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); }
Comments