tobold.org

correct • elegant • free

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.

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.

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.