tag:blogger.com,1999:blog-3722233.post4448906480931578928..comments2023-10-04T18:51:56.938-05:00Comments on Computational Complexity: Complexity and ComputabilityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-41247141507722136002010-06-04T14:48:02.324-05:002010-06-04T14:48:02.324-05:00perhaps complexiy guys also lost touch with realit...perhaps complexiy guys also lost touch with reality?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89830369800798845732010-05-31T18:45:04.551-05:002010-05-31T18:45:04.551-05:00c.e. = computably enumerable, also known as semi-d...c.e. = computably enumerable, also known as semi-decidable or recursively enumerable. IOW, questions a Turing machine can answer in the affirmative.Mark Reitblatthttps://www.blogger.com/profile/02844686872298320790noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21658745108493387332010-05-27T17:12:55.443-05:002010-05-27T17:12:55.443-05:00ce?ce?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59770135093544985522010-05-27T11:13:26.559-05:002010-05-27T11:13:26.559-05:00The field-splitting that Lance describes is only a...The field-splitting that Lance describes is only a moderate issue for theorem-provers, but it poses a <i>severe</i> problem for systems engineering.<br /><br />When Lance says of the conference attendees: <i>"We all like Turing machines, complexity has drawn many of its concepts from computability theory and this crowd all study randomness"</i>, this amounts to saying that the folks at the conference have reasonably overlapping notions of naturality.<br /><br />But increasingly nowadays, systems engineers find that they sometimes don't even share even the most basic notions of naturality ... a lacuna that makes communication infeasible.<br /><br />These naturality-splits start early in the undergraduate education ... a student who learns from Schey's textbook <i>Div, Grad, Curl and All That</i> will ever-after have a different notion of naturality from a student who learns from Bill Burke's (semi-legendary) <i>Div, Grad, and Curl Are Dead</i>.<br /><br />So, should colleges set undergraduate standards for mathematical naturality ... and if so, what should those standards be? ... or is that choice best left to the individual students/professors? <br /><br />If yah want to start an argument, just ask that question!<br /><br />The Introduction to Bill Burke's book is a lively polemic about field-splitting and mathematical naturality ... it is well-worth readingâ€”and contemplatingâ€”by any undergraduate student IMHO.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4900581480938962442010-05-27T10:55:18.453-05:002010-05-27T10:55:18.453-05:00I guess Computability was always part of math, it ...I guess Computability was always part of math, it has not changed. This is the Complexity that has changed over the decades, by moving away from techniques in recursion theory, like diagnalization, probably because people felt that they are not going to help in solving P vs NP as Lance said.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48027342175380089622010-05-27T10:49:10.387-05:002010-05-27T10:49:10.387-05:00http://www.amazon.com/New-Kind-Grammars-generative...http://www.amazon.com/New-Kind-Grammars-generative-grammars/dp/1452828687/<br /><br />A New Kind of Grammars: A new kind of generative grammars that can produce the empty language is designed in this book.Milind "Milz" Bandekarhttp://www.amazon.com/New-Kind-Grammars-generative-grammars/dp/1452828687/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36904607933255899192010-05-27T10:48:08.914-05:002010-05-27T10:48:08.914-05:00Seems to me that computability research (or at lea...Seems to me that computability research (or at least this FRG on Algorithmic Randomness) has become "too much" like math in the sense that it has lost touch with reality. One can make that case with some complexity research also, but I think the difference is that complexity research is (usually) at least <em>motivated</em> by questions of practical interest. If you (or anyone else) can make this case for the problems being studied by this grant, I'd be interested to hear it.<br /><br />So maybe that's why there's not so much interaction between the two fields.Anonymousnoreply@blogger.com