Britain has come to it's senses in at least small way and has issued a formal apology to Alan Turing for it's what it did to him - actions which led directly to his suicide at the age of 41. The apology can be found
here.
It is happy that this apology has taken place. I hope that the British and American governments both apologize for the harsh treatment of homosexuals in various psych wards until 1973. Dr. Turing's death was a great blow to mathematics and computer science, yes, but it is the larger issue that takes precedence. It is not just sad that Turing was destroyed because he was so bright a light, it is sad because so many suffered and have become forgotten. I don't mean to cast aspersion on the British Government. Indeed, the Prime Minister recognizes this in the above linked statement.
However, I feel that I ought to explain Dr. Turing's work, in order to have people comprehend him as a man of incredible insight and rare genius rather than as a victim of society. To do this will require some scene setting.
In 1900 David Hilbert (above) proposed a list of 23 problems, the solutions of which he proposed should take approximately a century of search. One of these questions (the second) asked for mathematicians to prove the axioms of arithmetic consistent. He was, in fact, referring to the work of Gottlob Frege, whose
Begriffsschift had seemingly embedded the Peano Arithmetic in rock solid ground. All that remained to Hilbert was the asked for proof - and a century seemed plenty of time to write even such a non-trivial thing out.
In 1901, however, the question changed. Bertrand Russell developed a formal paradox in Begriffsschrift. This paradox comes about through self-reference, and the importance of strange loops in these things is an interesting study that is beyond our scope. The point is that Begriffsschrift was as solid a foundation as a rollicking sea. The question altered suddenly in 1910. Luckily, a new system was written by Russell himself free of the paradoxes of the old kind.
Unfortunately (or perhaps not) the mathematician Kurt Gödel proved that there were contradictions in Russel's work and these contradictions come not out of weakness but strength! Indeed every sufficiently strong mathematical system must bear the Gödellian problem.
Godel had proved that
No Mathematical System Strong Enough To Hold The Counting Numbers Could Be Consistent And Complete. At this point, the only thing that remained of Hilbert's naive 2nd problem was this: the Entscheidungsproblem ("Decision Problem"). Could we build a mathematical device to simply throw out all the Godelian chaff and keep all the number theory wheat?
Enter Alan Turing, whose memory we are attempting to honor.
Dr. Turing was a student of the great logician Alanzo Church, who also did work on the Entscheidungsproblem (in fact, Church solved the problem first - but no one figured it out except people who had studied his λ-calculus extensively. Turing's beautiful and intuitive proof is the better and thus the wider known) and had figured out the basic problem was that no one really knew what mathematical machinery looked like. There were the systems of Russell, Zermelo, and Peano - but these were abstract set pushers. The sentences they made were dead, no one had ever bothered to define how someone could build a process in these languages.
Well, no one except Church and Turing. Turing's method is beautiful and simple, relying on only one even simpler idea. That idea is Finite State Machines.
A Finite State Machine is a machine that when fed an input, changes state. The above, for instance, is fed an arbitrarily long binary number and bounces between states until it lands in S1 or S2. If it lands in S1, then the number has an even count of zeros and the machines accepts. Otherwise, the machine rejects. Try it and see!
Many "languages" (groups of acceptable strings) can be defined with finite state machines. But try to build one that can check if parenthesis are balanced. It is impossible, the machine needs some kind of memory in order to know how many layers deep it is!
And Turing began thinking about memory. What is a mathematician? A mathematician has a finite number of states (an enormous number, but finite) in his head and all the paper in the world to write on. And what is a Turing Machine? A finite state machine with all the memory in the world.
Anything in the world that can be done mechanically can be done with a Turing Machine. So Truing subtly re-wrote the question. He began to consider whether if one made a Turing Machine made to look over mathematical statements it could be the thresher aforementioned. His conclusion involved an insight into mathematics hidden deep in Godel's proof, an insight his explicit drawing has enriched every mathematician since.
This insight is deceptively simple "Turing Machines are a language," - more broadly "Metamathematics is a language." Since Turing Machines can define a language, then could not one be made to build Turing Machines? One could, this is the Universal Turing Machine. One can feed a string in to a UTM (we now call this "programming computers") and it can output any Turing Machine, which itself can do wonders. Dr. Turing's simple conceptions had struck to the heart of mathematics, which was so moved that it split and the new creature was dubbed "computer science".
And the Entscheidungsproblem? It's solution is simple: "No." Turing simply built an anti-Gödellian thresher and showed that it could not even thresh the program for an anti-Gödellian thresher! Yes, the Turing Machine turned the Entscheidungsproblem from a fearsome German phrase to a well-understood part of computation. Speaking of which, the Turing Machine becomes vital and powerful in the study of computational complexity; it gives the basis for the development of Artificial Intelligence while offer clarification on the intellegence of ourselves; his work on "Unorginized Machines" has given way to Neural Networking and Genetic Algorithms; his work crystallized the mathematical underpinnings of modern cryptography.
These are perhaps Turing's deepest developments - the ones he will be remembered for when schoolchildren have to be reminded that Hitler and Attila lived at different times. These amazing feats did not slow Dr. Turing down as, famously, the writing of
Principa Mathematica had done to Bertrand Russell. He remained a force of mathematical nature, working on ideas of practical, abstract, and computational nature until the end of his life. His service during WWII involved the most successful signals intelligence corp in history, and it is - as the Prime Minister of Britain notes - no coincidence that he was on the winning side.
In learning the story of the life of Dr Turing one becomes aware that the only essential thing Turing lacked was a society capable of accepting him, a society that would allow him to flourish. Instead he got one that took the best of his work and destroyed him in a fit of false moralistic madness. The society -not government true, but the
society- that saved von Braun had destroyed Turing. If anything should be learned by the world from Turing's life (there is too much that must be learned from his work) it has nothing to do with homosexuality. What must be learned is the acceptance of deviation from the mean, the promotion of talent even if it comes with peculiarity, and the end of the wicked practice of the categorization of humans in a hierarchy of "moral correctness" that underpins all prejudice.
There's something about Latin. It has, to me, a distancing effect. There's not a joke on the page on the Iraq War, but I can't help laughing. Latin is so distant and dead, but here it is pretending it is contemporary. It's hysterical!
