*June 22, 2012*

The Google Doodle for June 22, 2012, is an interactive Turing-like machine, in honor of Alan Turing's 100th birthday. There are various puzzles to solve, and as some have noticed, after solving all the puzzles a bunny icon appears. Clicking on the bunny icon presents a complex machine that seems to output random numbers. What does it do?

After some analysis, I determined that this machine is computing a form
of the Fibonacci series. **UPDATE**: I am informed that specifically it
is generating a sequence similar to the
Rabbit
Sequence, which is related to Fibonacci's
original
formulation of the sequence.

Here is how I came up with my analysis. The machine looks like this while it is running:

The machine starts with a blank tape and with the instruction pointer in the upper left corner. I'm assuming that you understand all of the machine's operands (since you can only access the bunny machine after finishing the various puzzles).

The first thing I noticed was a couple of three element loops:

Each of these loops will move the tape pointer left or right until finding a blank tape square.

I next tried to simplify the machine by breaking it up into subroutines. Essentially, each time the machine made a substantial jump, I called the part of the instruction set that the machine jumped to a new subroutine.

Next, I translated the subroutines to a sort of pseudocode.

sub main:sub four:

write 1

goto one

sub one:

if tape reads 1:

goto two

else

write blank

move right

move right until tape reads blank

goto six

sub two:

write blank

move right

move right until tape reads blank

goto three

sub three:

write 1

move right

write 0

move left until tape reads blank

goto four

write 1

goto five

sub five:

move right

goto one

sub six:

write 1

move left until tape reads blank

goto seven

sub seven:

write 0

goto eight

sub eight:

goto five

Now, I consolidated some of the subroutines together. Particularly, I consolidated subroutines three, four, and five into subroutine two, and I consolidated subroutines seven, eight, and five into subroutine six. I also moved some of subroutine one into subroutine six.

sub main:

write 1

goto one

sub one:

if tape reads 1:

goto two

else

goto six

sub two:sub six:

write blank

move right

move right until tape reads blank

write 1

move right

write 0

move left until tape reads blank

write 1

move right

goto one

write blank

move right

move right until tape reads blank

write 1

move left until tape reads blank

write 0

move right

goto one

At this point, it's becoming clear what's going on. In subroutine one, you check to see whether the element under the tape is 1 or not. If the element is 1, then you perform subroutine two; otherwise you perform subroutine six.

In subroutine two, the tape pointer is on a 1 value. You write a blank on that spot, and then move to the right end of the tape. Then you write a 1 and a 0, and move left until you reach a blank—in particular, the blank that originally held the 1 you read at the beginning of subroutine two! Then you rewrite the 1 that used to be there, and move right one cell to repeat.

In subroutine six, you do the same thing as subroutine two, except instead you write only a 1 at the right end of the tape.

In other words, you read the tape sequentially from left to right, and depending on whether the tape reads 0 or 1, you append the sequence 1 or 10 to the tape!

So now consider what happens with the tape at a high level. You start running subroutine main, and write a 1 on the tape. The tape now contains a single 1.

Since there is one 1 on the tape, you write 10 to the end of the tape. Now the newly appended part has one 1 and one 0.

From that part, you append 10 (for the existing 1) and then append 1 (for the existing 0). The newly appended part has two 1's and one 0.

Let's continue:

Current part | Appended part | # 1's | # 0's |
---|---|---|---|

1 | 10 | 1 | 1 |

10 | 101 | 2 | 1 |

101 | 10110 | 3 | 2 |

10110 | 10110101 | 5 | 3 |

10110101 | 1011010110110 | 8 | 5 |

Notice the pattern in the number of ones and zeros? I'll leave it as an exercise to the reader to prove the pattern generally.