tag:blogger.com,1999:blog-3722233.post116187351265515561..comments2020-10-22T06:46:11.232-05:00Comments on Computational Complexity: Whose Thesis is it Anyway?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-1161982587666983752006-10-27T15:56:00.000-05:002006-10-27T15:56:00.000-05:00This is 100% false. I know a professor active in r...<I>This is 100% false. I know a professor active in recursion theory. In a graduate course he taught, he defined which functions were recursive by saying it was the least sets closed under universal functions, projections, a certain sort of recurison property, and perhaps one or two other simple things I've forgotten. I also saw heard of it being taught from the point of view of what's defined by certain types of bounded quantifier formulas.</I><BR/><BR/>What you've hinted at is Kleene's mu-recursive functions-based definition of the computable functions. This is still computability theory as everyone knows it, and equivalent to TMs. Nobody requires that TMs be the only expression of computability; lambda-calculus is also equivalent. They are all part of the same objective, describing what things can be built/computed by an algorithmic process, i.e. computability theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161973887497923102006-10-27T13:31:00.000-05:002006-10-27T13:31:00.000-05:00Computability Theory is descriptive- it isthe stud...<I>Computability Theory is descriptive- it is<BR/>the study of what is computable and also<BR/>what is not computable. It may be tied<BR/>to one model, but it is the way 100% of<BR/>all computability theorists thing about<BR/>things.</I><BR/><BR/>This is 100% false. I know a professor active in recursion theory. In a graduate course he taught, he defined which functions were recursive by saying it was the least sets closed under universal functions, projections, a certain sort of recurison property, and perhaps one or two other simple things I've forgotten. I also saw heard of it being taught from the point of view of what's defined by certain types of bounded quantifier formulas.<BR/><BR/>In my experience, recursion theorists are also rarely talking about computation. Usually they seem to be busy constructing functions or sets which step by step avoid or include certain situations.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161959048894691182006-10-27T09:24:00.000-05:002006-10-27T09:24:00.000-05:00''Recursion Theory' is a much stupidername. It al...''Recursion Theory' is a much stupider<BR/>name. It already has a meaning in CS and<BR/>math. What is by historical accident we<BR/>called Computability Theory<BR/>``Calculus'' because we Calculate things.<BR/>That would be as stupid since Calculus<BR/>already means something else.<BR/><BR/>Computability Theory is descriptive- it is<BR/>the study of what is computable and also<BR/>what is not computable. It may be tied<BR/>to one model, but it is the way 100% of<BR/>all computability theorists thing about<BR/>things.<BR/><BR/>bill gasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161925467837040132006-10-27T00:04:00.000-05:002006-10-27T00:04:00.000-05:00Computability theory is a stupid name. It just sou...Computability theory is a stupid name. It just sounds better for selling on research grants. In reality, it ties us to a particular abstraction. Recursion theory can be described nicely in terms of closure under certain function, and this approach avoids all the chrome of turing machines or whatever your other favorite equivalent model is. Ideally, one doesn't want to get stuck on anyone one way of explaining things, because different problems are easier to think about in different models.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161904951780735372006-10-26T18:22:00.000-05:002006-10-26T18:22:00.000-05:00The most important thing in getting your thesis we...The most important thing in getting your thesis well known is who is your supervisor?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161897198369499812006-10-26T16:13:00.000-05:002006-10-26T16:13:00.000-05:00Thanks for the reference. I construe the letter as...Thanks for the reference. I construe the letter as indicating that he might well have been aware of Turing machines, which are a first step towards stored program computers. However there is very little of the RAM (von Neumann) architecture in Turing's work. IMHO his contributions are more of a theoretical kind (but no less relevant). <BR/><BR/>p.s. a bit of trivia: Turing's PhD is from Princeton, not Cambridge as one could naturally expect.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161896830022492532006-10-26T16:07:00.000-05:002006-10-26T16:07:00.000-05:00My impression was that only a few logicians ever t...My impression was that only a few logicians <I>ever</I> thought Church deserved equal credit with Turing. (Sure, Church might've gotten the Thesis, but Turing got the machines!) So if we accept Soare's argument, this might be one of the few instances where the general public (OK, the general <I>nerd</I> public) got it right and the specialists got it wrong.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161894472033181042006-10-26T15:27:00.000-05:002006-10-26T15:27:00.000-05:00Here's the von Neumann letter.Here's <A HREF="http://www.turing.org.uk/sources/vonneumann.html" REL="nofollow"> the von Neumann letter. </A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161889150808998232006-10-26T13:59:00.000-05:002006-10-26T13:59:00.000-05:00To anon 2: I hadn't heard about the Turing connect...To anon 2: I hadn't heard about the Turing connection with the von Neumann architecture (do you have a reference?) but certainly the architecture itself was invented by Eckert, and in this case Johnny was just the guy who happened to write the key technical report on the subject. On the other hand George Dantzig often stated that linear programming and the simplex algorithm had substantial contributions from von Neumann and that Johnny selflessly declined joint authorship.<BR/><BR/>This only reinforces my point that objects are all too often not named after their discoverers, so we should stop pretending they are.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161883088446006102006-10-26T12:18:00.000-05:002006-10-26T12:18:00.000-05:00Don't feel so sorry for von Neumann: he is usuall...Don't feel so sorry for von Neumann: he is usually given full credit for the stored-program computer, though there apparently is a letter from him to Turing making it clear that the main idea came from Turing's universal TM. As part of the consulting for which he is given credit for the idea, he did develop circuitry for implementing random-access memory so maybe it should be called the "Turing-von Neumann architecture".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161874888588076222006-10-26T10:01:00.000-05:002006-10-26T10:01:00.000-05:00This just highlights that naming is rather arbitra...This just highlights that naming is rather arbitrary. Von Neumann predates Yao by three decades or so and gets no credit. Church and Levin postdate their corresponding names and they get full co-credit. There are many other examples. <BR/><BR/>So lets stop pretending that results are named after their discoverers. In the process lets also stop the pretense that we "fix" attributions by adding or substracting names from the list of supposed creators. <BR/><BR/>We should all just agree that results are named to honor famous researchers which had done good (often pioneering) work in the area. Nothing more, nothing less.Anonymousnoreply@blogger.com