Update: The Turing machine Google Doodle that was up for only a day to celebrate Alan Turing's 100th birthday is back. You can now play it as much as you want, when you want.

The doodle is available in a live playable form at the Doodle Archive.

The Google Doodle is often a masterpiece of  design but this time it is a masterpiece of computer science. The doodle is a complete Turing Machine that you can interact with in an attempt to solve a puzzle.

What is really interesting is that this simple doodle demonstrates all of the ideas of programming - conditionals and loops, data and storage - and the idea of a stored program machine.

A Turing Machine consists of two parts: the tape that the machine can read and write and the controller that determines what happens at each step.

In the case of the doodle, the tape is limited to what you see on the screen and the controller is limited to the operations you are provided with at each step of the puzzle.

What exactly is the puzzle?

If you click the green Go button then you will see a number in the box at the top right. This is the target number that gives the first letter of Google, i.e. the G. Your problem is to work out how to set the controller to convert the initial number on the tape to the target number.

A Turing machine always works in the same way: the controller has a set of states and at each step it moves to a new state after performing the action that the current state indicates.

For example on the initial tape there is a left arrow and a right arrow that simply mean move the tape one place in that direction. A state with a 0 writes a zero to that position and a state with a 1 writes a one to the position.

Spoiler alert - the solution to the first letter is described here. If you don't want any help skip to "Easy!".

For example, if you are given the following starting configuration:

Then, if you just click the green Go button, what happens is that the tape reader moves one place to the left, writes a 0, then moves three places to the right, and writes a 0. The result is 00010 which isn't the target number.

To get the target number you have to change the "write 0" instructions to "write 1" instructions - you just click on them to change them.  If you run the machine again, you will find that it moves to the left, writes a 1, moves three places to the right and writes a 1 - which gives the correct value:

The doodle then checks to see if the two numbers are the same and if they are it gives you the first letter - G.

Easy!

Well the first step is easy but the level of logic needed goes up for each letter of Google.

At the next level the machine has a conditional which moves to the lower set of states depending on whether the content of the tape is a zero,  one or blank.

The controller above says - "Moves one place to the left, if the tape has a 0 move to the state below and write a zero". Then the program ends because the remaining states to the right are blank.

The third letter introduces a loop back state:

If you click on the circular arrow icon then which state you jump back to changes. In this part of the puzzle you simply have to decide which state to return to.

 After this no new state symbols are introduced, but the problems get harder. The final one asks you to select the correct version of four operations.

If really is great fun, and watching the machine execute its "program" really does give you an idea of how a Turing machine or any computer actually works.

When you solve the first six puzzles you will see a "big" program run to produce the sequence 1,10,101,10110,,,

If you solve the initial six puzzles then you are presented with six more difficult ones to try out. All you have to do to see the new set of problems is attempt to play again - refresh the page and click the green arrow.

Trivia note: The binary code used to represent the letters is the old Baudot teleprinter code used at the time Turing was cracking codes.

If you really, really get stuck then there is a video that shows you the solutions - but don't watch it!

Try not to watch this video!
It reveals the answer but doesn't provide any explanation.

Thanks Google for providing a doodle that is both amusing and educational.

Luckily Google Doodles are not as ephemeral as they seem. If you want to find it in the Google Doodle Archive, remember that it the is the doodle for the 100th anniversary of Alan Turing's birth,  June 23, 2012

More Information

Google Doodle Archive

Related Articles

What is a Turing Machine?

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.