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:
  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

sub 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:
  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

sub six:
  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:

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.