tag:blogger.com,1999:blog-3722233.post4969287880355180435..comments2024-02-29T15:59:22.700-06:00Comments on Computational Complexity: Why is it called the Turing Award?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-82039921556112757452012-07-06T06:30:25.725-05:002012-07-06T06:30:25.725-05:00Reply to Anonymous 4:19
The problem is not that yo...Reply to Anonymous 4:19<br />The problem is not that you are unpopular, but that you are misinformed. Look at some recent FOCS/STOC/SODA/ICALP/SOCG conference proceedings: there will be hardly any paper dealing with taxonomy. On the other hand, in the last few decades there have been great results in such diverse subareas as sublinear time bounds, computational economics, computational game theory, distributed computing, efficient network algorithms, data structures, and quantum computing, as well as truly wonderful and important interdisciplinary work: coding theory, statistics, compressed sensing, and embeddings of one topological space to another. I wrote the list just as topics came to my mind, it is very far from comprehensive, and, on purpose, avoids Complexity Theory. <br /><br />As for what Turing would have liked, it is very much open to debate. He did spend most of his professional life in institutions that today would be affiliated with CS. His name is not being used: we honor him. He was a genius, first and foremost.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73620366153056690922012-07-06T06:11:23.551-05:002012-07-06T06:11:23.551-05:00I believe that there were good reasons, not "...I believe that there were good reasons, not "lucky guesses" for the choice of Turing as the name of the prize. Although this period is even before I became a theoretician, it is not hard to look at what was known in Theoretical Computer Science in 1966. Besides Formal Languages, where the most visible greats were still very active, the field was seen as important but specialized,and without a single major figure, there was the beginning of Computational Complexity: Juris Hartmanis (in collaboration with Stearns, and sometimes with Lewis) has published the first time and space hierarchy results. Michael Rabin, independently, developed similar techniques. Parsing of context-free languages on Turing machines was well understood (the n^3 CYK algorithm, and log^2 space algorithm). The computational model for these results was the Turing machine. The existence of Universal Turing Machines gave a clean mathematical model, and motivation to pursue such results. There was the hope that a general theory could be based on what was then called Recursion Theory, that would be a foundation for Theoretical Computer Science. <br /><br />Turing also showed that many questions that could be asked as foundational, were not. For example, "is there a fundamental difference between hardware and software?" "Should we use base 3 logic?" "Is it important for programs to be self-modifying?" <br /><br />Perhaps most important, the implication of the idea of universality was that "symbol manipulation" could be as good as "specific problem solving." Incredible as this may sound today, this was considered a revolutionary insight in AI. In other words, you did not have to build a checker-playing program: you could instead set up a formal system in which you could prove the theorem "X is a winning configuration for White" and then use a theorem prover for this system: the resulting program would play checkers. A less trivial version is that in order to write a program to recognize patterns, you do not have to try to imitate biology. <br /><br />Come to think of it, this idea of "pushing symbols" instead of "dealing with the problem" is far from being universally accepted even today. <br /><br />Computer programs manipulate symbols. Turing showed that this is all any rigorous scientific method can do--so in a sense he showed that Computer Science is the most important scientific endeavor.<br /><br />People did know this in 1966. So, as a lucky guess, they decided to honor him.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21804823762770764672012-07-05T16:19:08.561-05:002012-07-05T16:19:08.561-05:00I'm sure this'll be unpopular, but I don&#...I'm sure this'll be unpopular, but I don't think Turing would approve very much. Alan Turing was a mathematician first and foremost, and would much rather his name be used for a mathematics prize. He would probably not approve at all of what theoretical CS has turned into (a sink: a collection of many bright young minds utterly wasted by a near-religious devotion to taxonomy, with no real innovation in decades)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35591666860169639972012-07-05T11:14:22.006-05:002012-07-05T11:14:22.006-05:00A related exercise is Simon Raper's "Grap...A related exercise is Simon Raper's "<a href="http://drunks-and-lampposts.com/2012/06/13/graphing-the-history-of-philosophy/" rel="nofollow">Graphing the history of philosophy</a>". <br /><br />Is there a similarly rich-structured graph for CS / CT / QM / QC / QIT? Where do Turing, Gödel, Kleene, and Post appear on it?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69662024671591435102012-07-04T11:56:57.473-05:002012-07-04T11:56:57.473-05:00The first book with "Turing Machine" in ...The first book with "Turing Machine" in the title was Charles Joseph Houghton's <i>An elementary introduction to the concept of a Turing machine</i> (1961); this was followed by many more.<br /><br />Similarly we have Ernest Nagel and James Newman (justly celebrated) exposition <i>Godel's Proof</i> (1960); this was followed by many more.<br /><br />Kleene's name is associated to several eponymous books like Renate A. Schmidt's <i>Relations and Kleene Algebras in Computer Science</i> (2008).<br /> <br />However, the sole book with "Post" in the title apparently is <i>Solvability, provability, definability: the collected works of Emil L. Post</i> (1994).<br /><br /><b>Conclusion:</b> Emil Post deserves that someone write a book-length scholarly survey with the word "Post" appearing eponymously in the title.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35020017329661780962012-07-04T00:41:10.939-05:002012-07-04T00:41:10.939-05:00Just one correction. Emil L. Post died April 21, 1...Just one correction. Emil L. Post died April 21, 1954 at age 57. In contrast to Turing he did no practical work in CS. But since by now we have Turing, Gödel, and Kleene awards it would be high time to create a Post award, too.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67639431971786547092012-07-03T19:10:30.307-05:002012-07-03T19:10:30.307-05:00Google NGRAM Viewer shows a tremendous increase in...Google NGRAM Viewer shows <a href="http://books.google.com/ngrams/graph?content=Turing+machine&year_start=1920&year_end=2000&corpus=0&smoothing=1" rel="nofollow">a tremendous increase in the incidence of "Turing machine" spanning the years 1957-63</a>. <br /><br />Then with the help of Google Books, we find a surge both in academic publications, and introductory texts like Martin Davis' <i>Computability and Unsolvability</i> (1958) and Charles Houghton's <i>An Elementary Introduction to the Concept of a Turing Machine</i> (1961).<br /><br />In physics we used to call this phenomenon "a bandwagon." For whatever reason(s) — plausibly a confluence of multiple reasons — there was a pronounced Turing bandwagon during the years 1957-63.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68400502529987469142012-07-03T17:06:13.147-05:002012-07-03T17:06:13.147-05:00But back in 1966 when Alan Perlis won the first Tu...<i>But back in 1966 when Alan Perlis won the first Turing award, Turing's influence on the field was far less obvious.</i><br /><br />[citation needed]JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.com