Google Doodle - A Turing Machine Puzzle - Update: Play it Now
Written by Harry Fairhead   
Tuesday, 26 June 2012

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:

 Turingdoodle1

 

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:

 

Turingdoodle2

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.

 

Turingdoodle3

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:

Turingdoodle4

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.

 

Turingdoodle5

 

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

 

turingrabbit


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.

 turingadvanced

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?

 

blog comments powered by Disqus

 

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.

 

Banner


Bredan Eich Leaves Mozilla
04/04/2014

Last week Brendan Eich was appointed CEO of Mozilla. Yesterday he resigned that position and left the company he co-founded 15 years ago, saying "I will be taking time before I decide what to do next. [ ... ]



HeartBleed - The Programmers View
10/04/2014

You've heard about the HeartBleed vulnerability in OpenSSL, you probably have had to deal with its consequences - but perhaps you don't know just how old fashioned a bug it is. 


More News

 

Last Updated ( Tuesday, 26 June 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.