Slashdot Mirror
Honoring Alan Turing, "Father of Computer Science"
alphadogg writes "Google's Vint Cerf and others are spearheading celebrations in Silicon Valley and the UK this month to celebrate the 100th anniversary of Alan Turing's birth. 'The man challenged everyone's thinking,' says Vint Cerf, Google's chief Internet evangelist, in an interview with Network World. 'He was so early in the history of computing, and yet so incredibly visionary about it.' Cerf — who is president-elect of the Association for Computing Machinery and general chair of that organization's effort to celebrate the upcoming 100th anniversary of Turing's birth on June 23 — says that it's tough to overstate the importance of Turing's role in shaping the world of modern computing. Turing's accomplishments included his breakthrough Turing machine, cracking German military codes during WWII and designing a digital multiplier called the Automated Computing Machine."
Turing didn't just help with practical computers. A lot of his ideas mattered in many other fields. For example, his idea of the Turing machine http://en.wikipedia.org/wiki/Turing_machine and related work was vital to a lot of other fields such as the rise of theoretical computer science, and even as far as the study of equations with integer solutions (called Diophantine equations) in the form of Hilbert's Tenth Problem http://en.wikipedia.org/wiki/Hilbert's_tenth_problem.
Essentially, Hilbert asked whether there was a general algorithm to determine whether a given equation in integer variables had a solution. Even for individual equations figuring this out can be very difficult. For example it was known even in ancient times that x^2+y^2=z^2 had infinitely many integer solutions, but it took Fermat to show that x^4+y^4=z^4 did not. It turned out that there is no general way of answering these sorts of questions. The problem was solved by lot of people, especially Julia Robinson, Martin Davis, , Hilary Putnam, and ultimately finished off by Yuri Matiyasevich. The solution was to show that one can actually model an arbitrary Turing machine as a system of Diophantine equations, where the machine halting is equivalent to the Diophantine equations having a solution. Thus, if one can solve that one can answer whether any given Turing machine can halt, which Turing showed could not be done in general, using a clever trick- this is known as the Halting theorem http://en.wikipedia.org/wiki/Halting_problem. Curiously, the equivalent problem over the rationals is still open, and is turning out to be connected to deep issues in topology and the theory of elliptic curves. So Turing's ideas and thoughts are still pushing us forward and making us ask new questions.