tag:blogger.com,1999:blog-3722233.post5381796633499606754..comments2024-11-03T21:27:06.200-06:00Comments on Computational Complexity: The Enduring Legacy of the Turing MachineLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-56317691190827258052011-01-07T06:10:40.738-06:002011-01-07T06:10:40.738-06:00GASARCH said: Also worth checking out: the book A ...GASARCH said: <i>Also worth checking out: the book </i>A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine<br /><br />In parallel with Turing's 1936 article, it's great fun to deconstruct von Neumann's 1945 artlcle <i>First Draft of a Report on the EDVAC</i>.<br /><br />Four observations: (1) both Turing and von Neumann's have an astounding capacity for working things through in detail ... in both articles, seminal ideas are interspersed with in-depth analyses of minutiae.<br /><br />(2) Neither article is easy to read ... and von Neumann carefully explains why this necessarily is the case:<br /><br />----------------<br />"The ideal procedure would be, to take up the five specific parts [of the von Neumann architecture] in some definite order, to treat each one of them exhaustively, and go on to the next one only after the predecessor is completely disposed of. However, this seems hardly feasible. The desirable features of the various parts, and the decisions based on them, emerge only after a somewhat zigzagging discussion. It is therefore necessary to take up one part first, pass after an incomplete discussion to a second part, return after an equally incomplete discussion of the latter with the combined results to the first part, extend the discussion of the first part without yet concluding it, then possibly go on to a third part, etc. Furthermore, these discussions of specific parts will be mixed with discussions of general principles, of arithmetical procedures, of the elements to be used, etc."<br /><br />"In the course of such a discussion the desired features and the arrangements which seem best suited to secure them will crystallize gradually until the device and its control assume a fairly definite shape. As emphasized before, this applies to the physical device as well as to the arithmetical and logical arrangements which govern its functioning."<br />----------------<br /><br />(3) Even though these are (arguably) the two most important works in the history of computer science, neither work was recognized as a "breakthrough" at the time of publication. Prior to WWWII, only two of Turing's colleagues expressed any substantial appreciation of this work (these two being Richard Braithwaite and Heinrich Scholz). Similarly, von Neumann's IAS colleagues showed no great appreciation of the merits of actually <i>building</i> computing machines ... many IAS colleagues actively opposed von Neumann's line of research.<br /><br />(4) And finally, neither Turing nor von Neumann envisioned future trends with perfect accuracy. For example, von Neumann envisions a total memory of 2^18 bits (which he calls "memory units") ... and asserts that it is "obviously impractical" to store that many bits using logic gates (which he calls "E-elements"). Nowadays, the per-bit cost of "E-element" memory has fallen to 10^(-10) dollars. If computers make sense without Moore's Law, how much <i>more</i> sense do they make <i>with</i> Moore's Law?<br /><br />Here is <a href="http://faculty.washington.edu/sidles/STEM_roadmaps/vonNeumann_NORC_speech.mov" rel="nofollow">a 1954 audio recording</a> of von Neumann defending computer research ... only after a full decade of hard work and repeated public presentations, by von Neumann, Turing, and many other pioneers, did widespread appreciation emerge of the unbounded potential for advances in computer science.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3842590705079268792011-01-06T11:40:18.086-06:002011-01-06T11:40:18.086-06:00Lance,
Thanks for sharing this intriguing series....Lance,<br /><br />Thanks for sharing this intriguing series.<br /><br />I am quite sympathetic to your view, though with a small amendment in the characterization of later developments in our understanding of computation. Indeed, Turing beautifully anticipated many of the directions future study would take and addressed many of their liabilities. I would add that substantive extensions and applications have been made, but none of them redefine the core sense of computation, so much as explore his ideas (e.g. Type-2 Turing Machines in Weihrauch's work on Computable Analysis explores the computation of real numbers outlined in Turing's paper; various works on oracles) or add new structure (finitary or infinitary) for the computation to work with (infinite speedups or discrimination, and other supertasks) or within (neural networks, tilings). Also, it seems to me that the various attempts to integrate information and computation have led to a great deal of confusion, with the exception of well-defined (if abused) notions of information (e.g. Shannon information, algorithmic information). These points are, I suspect, a matter of emphasis and not disagreement.Johnny Logichttps://www.blogger.com/profile/12400552435971349275noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53000106706370015232011-01-06T10:44:08.494-06:002011-01-06T10:44:08.494-06:00Also worth checking out:
The book
The Annotated Tu...Also worth checking out:<br />The book<br /><a href="http://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055" rel="nofollow">The Annotated Turing: A Guided Tour Through<br />Alan Turing's Historic Paper on Computability and the Turing Machine</a><br />and/or see this<br /><a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/aturing.pdf" rel="nofollow">review</a><br />of it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52256069867635236432011-01-06T09:54:32.277-06:002011-01-06T09:54:32.277-06:00THe ACM's What is Computation? series is terri...THe ACM's <i>What is Computation?</i> series is terrific, and Lance's <i> Enduring Legacy of the Turing Machine</i> is one of many excellent articles.<br /><br />Particularly enjoyable was the <i>disagreement</i> among the various eminent authors ... this discord is evidence that Great Truths are being discussed. :)<br /><br />In aggregate, these ACM/Ubiquity articles reminded me of the September 04, 2007 post here on <i>Computational Complexity</i>, in which GASARCH drew attention to a now-classic 1997 article by De Millo, Lipton, and Perlis, titled <i>Social processes and proofs of theorems and programs</i>.<br /><br />In essence, if one substitutes throughout the De Milo/ Lipton/ Perlis 1979 article the word "computation" for the word "theorem", the result can be read as a remarkably foresighted summary of the aggregated ACM/Ubiquity <i>What is Computation?</i> 2010 series. <br /><br /> In this respect the Milo/ Lipton/ Perlis article was at least thirty-two years ahead of its time. :)<br /><br />From this we may infer ... uhh ... or can we?... that the <a href="http://ngrams.googlelabs.com/graph?content=proof+technology%2C+computation+technology&year_start=1920&year_end=20008" rel="nofollow">merging of the notion of "proof technology" with the notion of "computation technology"</a> is likely to continue ... and even accelerate ... in coming decades.<br /><br />My thanks and appreciation are extended to <i>Computational Complexity</i> for pointing us toward these thought-provoking essays.John Sidleshttp://www.mrfm.orgnoreply@blogger.com