Turing's Centenary
==================
I'm disappointed by today's Google doodle. A marvellous idea, of course,
to commemorate the centenary of Turing's birth with a model of a Turing
machine. And as you'd expect, it looks good. The font used on the tape
has a nice 1930s feel. But it is a triumph of form over content.
The machine starts off with a binary counter, which I rather like. But
this simple Turing Machine is closed source! Where is the state
description that drives it? That's the interesting bit. I've peered a
little bit at the Javascript that drives it, but it's minified, so even
after running through an indenter it's fairly impenetrable. More closed
source.
It's interesting to ponder what Turing himself would have made of the
open vs closed source debate. He touched both extremes: wide open as an
academic, closed tight as a military intelligence officer.
The binary counter is an extremely ironic Turing Machine. (I'm not going
to say why, it took me a while to realise. Think about it!) I don't know
if that was deliberate, as there's no clue given anywhere that I can
see. I hope that tomorrow they will post some more explanation to the
doodle archive.
Anyway, when you click on the counter, it changes to something else.
Now we do have a state description, well, sort of. It's nothing like the
set of 5-tuples that describe a real Turing Machine; each tuple is
(current symbol, current state, new symbol, new state, left-or-right
move).
In the Google version you get a movement, *or* a change of symbol,
*or*... the state is implictly represented by a kind of program counter,
normally “incremented” but with branches and loops available. It's like
they've stuck an anachronistic von Neumann architecture over it!
And what they've done with this odd Turing-like machine is a series of
puzzles. Set the machine up so that it can change ``01011`` into
``00011``. Now change ``11011`` into ``01011``. They remind me of
`railway shunting puzzles`_ that I enjoyed as a kid.
.. _railway shunting puzzles: http://en.wikipedia.org/wiki/Train_shunting_puzzle
But why? What's the point? The point of the Turing Machine is that it
embodies an *algorithm*, and the reason for studying algorithms is that
they can do useful things, like adding two numbers together. Could
something like that not have been incorporated?
And of course, *really* the point of Turing Machines is that we can
build a Universal Turing Machine, thus proving that algorithms are
subject to Gödelization, and that **code is data**. I grant it might
have been difficult to get the idea across in 487 x 229 pixels.
Oh well. At least the Google doodle got me thinking, and I took a look
at *On Computable Numbers, With An Application To The
Entscheidungsproblem* for the first time in over 20 years. Here are
three different versions: images_ of the original publication,
digitized_ but unmodified, and `tidied up`_ with footnotes and
corrections.
.. _images: http://l3d.cs.colorado.edu/~ctg/classes/lib/canon/turing-compnum.pdf
.. _digitized: http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
.. _tidied up: http://www.thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf
And Turing was, finally, lucky. The birth centenaries of Alonzo Church
and Kurt Gödel went by in the last few years entirely unmarked by
Google.