The final Google Turing puzzle

Contents

Introduction

On Saturday the 23^rd June 2012 there was a "Turing machine Google doodle" commemorating the 100^th anniversary of Alan Turing's birth. A full working version is now part of the Google Doodle archives:

Google Doodle for 2012 June 23: Alan Turing's 100th Birthday

This was on the main Google home page in place of the ordinary Google logo. Initially, the Turing machine runs a binary counter program, and will stop after a while unless you move the mouse.

$Turing machine counting (currently at 100<sub>2</sub>=4)$
Turing machine counting (currently at 100₂=4)

It will count until you click the round green "Play" button to play the Turing puzzle game. It gives you 6 "easy" Turing programming puzzles, which you solve by pushing the yellow buttons to set certain program steps, then press Play to see if you got it. If you've solved the puzzles and start over (or reload the page, or perhaps either) it gives you 6 "hard" puzzles.

$One of the ''hard'' puzzles$
One of the "hard" puzzles

After working through the normal puzzles, the Google Doodle starts replaying the solutions of the Turing puzzles, and the "=" box in the upper right changes to something that looks like a little dog, or maybe the Trojan Rabbit from Monty Python and the Holy Grail¹, on a colored background.

$Replaying the solutions$
Replaying the solutions

The Mystery Program

If you click on the doggie/bunny, the puzzle playback is replaced with a much more complex Turing program, with 3 rows of program symbols and 13 symbols per row (a total of 39 symbols):

$The 39-symbol mystery program$
The 39-symbol mystery program

The pattern on the tape grows to the right; here is how the program starts (with "." for an erased cell):

at step 1: 1 at step 2: _ at step 4: _1 at step 6: _10 at step 9: 110 at step 11: 1_0 at step 14: 1_01 at step 16: 1_010 at step 20: 11010 at step 22: 11_10 at step 26: 11_101 at step 30: 110101 at step 32: 110_01 at step 36: 110_011 at step 38: 110_0110 at step 43: 11010110 at step 45: 1101_110 at step 50: 1101_1101 at step 55: 110101101 at step 57: 11010_101 at step 62: 11010_1011 at step 64: 11010_10110 at step 70: 11010110110 at step 72: 110101_0110 ... at step 87: 1101011011010 (len = 13) ... at step 186: 110101101101011010110 (len = 21) ... at step 407: 1101011011010110101101101011011010 (len = 34) ... at step 937: 1101011011010110101101101011011010110101101101011010110 (len = 55) ... etc.

I'm counting head movements and writing or erasing a symbol as "steps". When a 0 or 1 symbol in the middle gets erased, it always replaces it with the same symbol again. Thus it makes sense to ignore these temporary erasures and just look at the whole binary string. It grows only to the right, and it's an irregular pattern.

Possible Mathematical Patterns

As the pattern grows, the successive values are 110, 11010, 110101, 11010110, 110101101, 11010110110, ... or in decimal: 6, 26, 53, 214, 429, 1718, 6874, 13749, ... which is not presently in the OEIS (even just the first 3 terms give no match).

By step 49273, it has written:

110101101101011010110110101101101011010110110101101011011010110110101 101011011010110110101101011011010110101101101011011010110101101101011 010110110101101101011010110110101101101011010110110101101011011010110 110101101011011010110110101101011011010110101101101011011010110101101 101011010110110101101101011010110110101101101011010110110101101011011 010110110101101011011010110101101101011011010110101101101011011010110 1011011010110101101101011011010110...

It seems to be almost periodic, but not quite. Here's what you get if you break it up into groups of 55 digits:

1101011011010110101101101011011010110101101101011010110
1101011011010110101101101011011010110101101101011010110
1101011011010110101101101011010110110101101101011010110
1101011011010110101101101011010110110101101101011010110
1101011011010110101101101011010110110101101101011010110
1101011010110110101101101011010110110101101101011010110
1101011010110110101101101011010110110101101011011010110
1101011010110110101101101011010110110101101011011010110
11010110...

As shown (by the highlighed 01 digits) every now and then a couple digits in a block of 55 changes. It does not change with every block of 55, though. Also, it takes quite a while before the original row appears again (however, that particular set of 55 bits occurs very often, just not starting in a position that's a multiple of 55).

In general, any initial substring no matter how long (and not just for Fibonacci lengths like 55), occurs arbitrarily many times in the rest of the digits, but the occurrences are irregularly spaced.

Taken as a binary fraction (0.1101011011010...) it is equivalent to 0.8392137714451652585671495977783023880500088230714420678280105786051... in decimal. It is irrational; the sequence of approximating fractions is:

0 / 1
1 / 1
5 / 6
21 / 25
26 / 31
47 / 56
167 / 199
214 / 255
1665 / 1984
5209 / 6207
6874 / 8191
438271 / 522240
1321687 / 1574911
1759958 / 2097151
3603955713 / 4294443008
...

The number doesn't fit any simple algebraic formula; my RIES program finds nothing ². I got nothing with ISC+ either³.

I sent most of the above to the seqfan and math-fun lists to solicit input and ideas.

My Analysis

By watching the machine do its work, it is possible to see that it has four loops where it spends most of its time:

L1 : Move to the right until reaching the end, then append 10

L2 : Move to the left until reaching a blank, then put 1 in the blank

L3 : Move to the right until reaching the end, then append 1

L4 : Move to the left until reaching a blank, then put 0 in the blank

$Locations of the loops and ''start'';`It is looping in L4, which will finish soon$
Locations of the loops and "start";
It is looping in L4, which will finish soon

After further inspection, one can see that:

After finishing L1, it always goes to L2
After finishing L2, it always moves right one space and then goes back to the "start"
After finishing L3, it always goes to L4
After finishing L4, it always moves right one space and then goes back to the "start"

and finally, at the "start" is a test to see if the current spot contains 0 or 1. If it contains 0 it erases the 0 and goes to loop L3, and if it contains 1 it erases the 1 and goes to loop L1.

However, since L2 goes back and replaces the 1 that was erased, and likewise L4 goes back and replaces the 0 that was erased, all erasures are temporary and we can just pay attention to what gets appended at the end.

Putting all this together, we see that the machine is doing the following:

Start with a single 1 on an otherwise blank infinite tape.
Starting on that single 1, scan from left to right one symbol at a time.
For each 1, add 10 to the end.
For each 0, add 1 to the end.
Continue indefinitely.

Using these rules it's easy to reconstruct the sequence. Here we show the "scan from left to right" in boldface, and the "add 10" or "add 1" to the end in italics :

1
110
11010
110101
11010110
110101101
11010110110
1101011011010
...

These numbers are found in OEIS sequence A171676:

A171676 : Ordered list in binary of the subwords (with leading zeros omitted) appearing in the infinite Fibonacci word

0, 1, 10, 11, 101, 110, 1010, 1011, 1101, 10101, 10110, 11010, 11011, 101011, 101101, 110101, 110110, 1010110, 1011010, 1011011, 1101011, 1101101, 10101101, 10110101, 10110110, 11010110, 11011010, 101011010, 101011011, 101101011, 101101101, 110101101, 110110101, 1010110101, 1010110110, 1011010110, 1011011010, 1101011010, 1101011011, 1101101011, ...

The "infinite Fibonacci word" is OEIS sequence A005614, a sequence of 0 and 1 terms:

A005614 : The infinite Fibonacci word (start with 1, apply 0→1, 1→10, iterate, take limit)

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, 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, 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, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, ...

If you add an initial 1, these bits are exactly the same as the sequence produced by the Google Turing machine.

(There is also A003849, which differs only in that the roles of 0 and 1 are reversed.)

Comments and Analysis by Others

Adam P. Goucher sent the following to math-fun :

Begin with the empty string
Apply the L-system rules: (1 → 10), (0 → 1)
Prepend '1' to the string
Apply the L-system rules again, then prepend 1 again
Continue indefinitely.

and gave the first few iterations:

(empty string) 1 110 110101 11010110110 1101011011010110101

John Graham-Cumming produced pseudo-code and a Perl implementation, and describes the output in his blog: What the final Turing Machine Google Doodle does

Footnotes

1 : The Trojan Rabbit Okay it's not that close a resemblance, but I couldn't resist.

2 : 0.839213771445165 gives these equations on the online RIES server; I also did a much longer RIES run on my own machine.

3 : ISC plus I might have been using ISC inforrectly. I think you need to try different numbers of digits: if 0.83921377144516 finds nothing, try 0.8392137714451, and so on.

Here are more binary digits, broken up into rows of 89 bits per row:

At Turing machine step 16643726:

11010110110101101011011010110110101101011011010110101101101011011010110101101101011011010

11010110110101101011011010110110101101011011010110110101101011011010110101101101011011010

11010110110101101101011010110110101101011011010110110101101011011010110101101101011011010

11010110110101101101011010110110101101011011010110110101101011011010110110101101011011010

11010110110101101101011010110110101101101011010110110101101011011010110110101101011011010

11011010110101101101011010110110101101101011010110110101101011011010110110101101011011010

11011010110101101101011010110110101101101011010110110101101101011010110110101101011011010

11011010110101101101011011010110101101101011010110110101101101011010110110101101011011010

11011010110101101101011011010110101101101011010110110101101101011010110110101101101011010

11011010110101101101011011010110101101101011011010110101101101011010110110101101101011010

11011010110110101101011011010110101101101011011010110101101101011010110110101101101011010

11011010110110101101011011010110101101101011011010110101101101011011010110101101101011010

11011010110110101101011011010110110101101011011010110101101101011011010110101101101011010

11011010110110101101011011010110110101101011011010110101101101011011010110101101101011011

01011010110110101101011011010110110101101011011010110101101101011011010110101101101011011

01011010110110101101011011010110110101101011011010110110101101011011010110101101101011011

01011010110110101101101011010110110101101011011010110110101101011011010110101101101011011

01011010110110101101101011010110110101101011011010110110101101011011010110110101101011011

01011010110110101101101011010110110101101101011010110110101101011011010110110101101011011

01011011010110101101101011010110110101101101011010110110101101011011010110110101101011011

01011011010110101101101011010110110101101101011010110110101101101011010110110101101011011

01011011010110101101101011011010110101101101011010110110101101101011010110110101101011011

01011011010110101101101011011010110101101101011010110110101101101011010110110101101101011

01011011010110101101101011011010110101101101011011010110101101101011010110110101101101011

01011011010110110101101011011010110101101101011011010110101101101011010110110101101101011

01011011010110110101101011011010110101101101011011010110101101101011011010110101101101011

01011011010110110101101011011010110110101101011011010110101101101011011010110101101101011

01101011010110110101101011011010110110101101011011010110101101101011011010110101101101011

01101011010110110101101011011010110110101101011011010110110101101011011010110101101101011

01101011010110110101101101011010110110101101011011010110110101101011011010110101101101011

01101011010110110101101101011010110110101101011011010110110101101011011010110110101101011

01101011010110110101101101011010110110101101101011010110110101101011011010110110101101011

01101011011010110101101101011010110110101101101011010110110101101011011010110110101101011

01101011011010110101101101011010110110101101101011010110110101101101011010110110101101011

01101011011010110101101101011011010110101101101011010110110101101101011010110110101101011

01101011011010110101101101011011010110101101101011010110110101101101011010110110101101101

01101011011010110101101101011011010110101101101011011010110101101101011010110110101101101

01101011011010110110101101011011010110101101101011011010110101101101011010110110101101101

01101011011010110110101101011011010110101101101011011010110101101101011011010110101101101

01101011011010110110101101011011010110110101101011011010110101101101011011010110101101101

01101101011010110110101101011011010110110101101011011010110101101101011011010110101101101

01101101011010110110101101011011010110110101101011011010110110101101011011010110101101101

01101101011010110110101101101011010110110101101011011010110110101101011011010110101101101

01101101011010110110101101101011010110110101101011011010110110101101011011010110110101101

0110110101101011011010 = 9.19340158787706 x 10²⁵²⁴

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2014 Apr 12.

s.27