[seqfan] The final Google Turing puzzle: what is 11010110110101101011011...

Robert Munafo mrob27 at gmail.com
Sat Jun 23 06:40:50 CEST 2012


I've been trying to "solve" the 3-line, 39-symbol Turing machine that
you get at the "end" of the Google doodle puzzles.

See [1] below for background. After solving the 6 puzzles, click on
the little color "dog" icon in the upper right to see the 39-step
program I'm investigating.

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 [4], on a
colored background. If you click on the doggie/bunny, the puzzle
playback is replaced with a much more complex Turing 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 5:  .1
 at step 8:  .10
 at step 11:  110
 at step 13:  1.0
 at step 17:  1.01
 at step 20:  1.010
 at step 24:  11010
 at step 26:  11.10
 at step 31:  11.101
 at step 35:  110101
 at step 37:  110.01
 at step 42:  110.011
 at step 45:  110.0110
 at step 50:  11010110
 at step 52:  1101.110
 at step 58:  1101.1101
 at step 63:  110101101
 at step 65:  11010.101
 at step 71:  11010.1011
 at step 74:  11010.10110
 at step 80:  11010110110
 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 seems to
be always replace 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.

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 OEIS (even just
the first 3 terms give no match).

By step 49720, it has written:

1101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101011011010110110101101011011010110110101101011011010110101101101011011010110...

It looks like any initial substring, no matter how long, 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
 ...

It doesn't fit any simple algebraic formula; my RIES program finds
nothing [2]. I got nothing with ISC+ either [3] (but I might be using
it wrong, I think you need to try different numbers of digits: if
0.83921377144516 finds nothing, try 0.8392137714451, and so on.)

Let me know if you have ideas for other, fancier tests I can apply to
this sequence, the fraction, etc.

- Robert Munafo

[1] Background:

If you go to Google today (Sat June 23rd) the Google Doodle is a
Turing machine. Initially it's running a binary counter program, until
you click the green "Play" button to pay the Turing 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 solve the puzzles and start over (or
reload, I'm not sure) it gives you 6 "hard" puzzles.

[2] See http://mrob.com/pub/ries/ries.php?target=0.839213771445165
  I also did a much longer RIES run on my own machine.

[3] http://isc.carma.newcastle.edu.au/index

[4] http://www.youtube.com/watch?v=T2PdyxMtiYM
  Okay it's not that close a resemblance, but I couldn't resist.

-- 
  Robert Munafo  --  mrob.com
  Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 -
mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com



More information about the SeqFan mailing list