Scientist Appreciation: Alan Turing

I had my Computational Complexity and Computability course tonight, and on the way home while slogging through the snow I wondered how I could work a post around the rather fascinating course material. Then I realised it gave me a perfect excuse to resurrect one of my favourite series on this blog which sadly fell the wayside: Scientist Appreciation! So, since he is so central to the subject of computability, this installment of Scientist Appreciation is devoted to Alan Turing.

Alan Turing had an unfortunately short life, but prior to his untimely death at the age of 41 he completed works and earned prestige which would make most academics inwardly weep with envy. His work helped form the theoretical foundation of computer science while he also goes down in engineering history as helping to construct one of the first true computers. Additionally, he gained popular fame as a code breaker during World War II working to counter the infamous Enigma machine as well as having his name become widely known in the realm of both artificial intelligence and science fiction through his proposition of the Turing Test for intelligence. While he is probably more popularly famous for his cryptography and the Turing Test, the rest of this post will focus on his theoretical framing of the notion of computability.

The true power (as well as the beauty and frustration) of mathematics is its elegant rigour and formal set of rules. If you truly want to know the properties of something, find a way to frame it mathematically and probe the results. Thus, when people were trying to understand the concept of an algorithm and determine just what sort of problems were computable, Turing created the eponymous concept of the Turing Machine (TM for short). In its regular formulation, a TM can be envisioned as an assembly line with a computational head positioned above a sheet of some sort (paper, perhaps) which can be both read and written to by the head. This sheet extends to infinity to the right, but has an ending to the left (from which the input is written). In each computational step, the head reads in an input from one position on the sheet, changes its internal state, has the option of writing over the current sheet's position, and then moves either to the left or the right (if it tries to move left in the initial position it stays where it is). This might sound like an awkward and plodding kind of computational machine to have, but there are some really fascinating things which can be shown about them. I don't know if there is any interest, so I won't go into detail now, but if any of my readers want me to give examples of some interesting problems with TMs let me know in the comments (or send me an email, if you have my email address). The thing is, I think I might just enjoy this because it is the kind of mathematics that comes the most naturally to me (as naturally as I think any university level math can come to a non-genius). Even if no one cares, I might not be able to restrain myself after I talk about Church in the next Scientist Appreciation and tie his work in with Turing's.

Anyway, my laptop is really acting up tonight, so I'm going to end this post here and hope my computer doesn't die (it also means I haven't proof-read this, so I hope it isn't too abysmal. Of course, I could always save as a draft and publish tomorrow, but what would be the fun in that?). In conclusion, Alan Turing made an amazing account of himself for his short life, and his early death was a tragedy for mathematics and computer science.