tag:blogger.com,1999:blog-3722233.post4623205365455882954..comments2016-04-30T06:01:27.725-04:00Comments on Computational Complexity: Recursion Theorem follows from Church-TuringLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-17310006779261083252012-12-19T01:44:50.320-05:002012-12-19T01:44:50.320-05:00The difficulties can be fixed with a bit more of f...The difficulties can be fixed with a bit more of formalization. E.g., that we have a random access machine where the code of the program is stored at the address 0. This machine model still captures the partial recursive functions. (This does not appeal to the CTT, but can be proved.) Then a program can read out the code with just one command. It does not refer to itself, it speaks only about the access of addresses. So there is no paradox involved here.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29485154735906376722012-12-18T09:59:17.900-05:002012-12-18T09:59:17.900-05:00I think the argument of Lance is slippery and the ...I think the argument of Lance is slippery and the TA was correct. The CTT says that any intuitively computable funnction is partial recursive. Now, how do you intuively define and compute the function that accesses its own code? Where does this code come from? Out of the blue? You also have to argue that it is finite. There is no escape here from the very hen-egg problem that only one of the standard non-trivial proofs of the recursion theorem resolves.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17827445043300743092012-11-26T15:15:56.249-05:002012-11-26T15:15:56.249-05:00Hi Lance,
Maybe I am missing something, but I thi...Hi Lance,<br /><br />Maybe I am missing something, but I think there is a problem in the argument.<br /><br />As I understand, CCT tells us only that if a function $f$ over natural numbers is computable then there is a TM computing it. It doesn't say that we can transfer an arbitrary mathematical statement in some machine model to the TM model. So there is a need for an argument.<br /><br />RT says that if we have a machine $F(x,y)$ then there is machine with code $\langle G \rangle$ s.t. $G(x) = F(x, \langle G \rangle)$. We need to assume that we can simulate these machines with TMs and vice versa (a similar argument would not hold in a model where we have RT but is not Turing-complete). Moreover it seems to me that in the end we will get a TM which has access to the code of a *similar* TM (computing the same function) and not to its own code.Kavehnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21864221800954691552012-11-26T05:40:30.906-05:002012-11-26T05:40:30.906-05:00The existence of acceptable numberings is the Chur...The existence of acceptable numberings <i>is</i> the Church-Turing Thesis. Most computability theorists now call the Church-Turing Thesis the "s-m-n Theorem," however changing the name for this statement does not make it any more true. Nevertheless, the s-m-n Theorem remains the most widely used result in computability theory, and results like the Recursion Theorem rely on it. Go get your points back, Lance.<br /><br />NB: Computability theory is still interesting without the s-m-n Theorem. See for example <a href="http://people.cs.uchicago.edu/~teutsch/papers/numberings.pdf" rel="nofollow">this paper</a>.Teutschhttp://www.blogger.com/profile/04848264673734802964noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87840585333220685632012-11-26T00:03:54.197-05:002012-11-26T00:03:54.197-05:00You are clearly outside the average to genius leve...You are clearly outside the average to genius level IQ150+ so you have to get used to most people failing to understand things that seem blindingly obvious to you. You also need to get over what was probably your one low grade in how many assignments? We all had one you know some of us had more, I even failed an exam in a course where I averaged 78% but I passed the retake.Jo Kirkpatrickhttp://healaddiction.blogspot.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10767620798145066352012-11-24T05:03:52.963-05:002012-11-24T05:03:52.963-05:00@KWRegan, thank you for the reference to Friedberg...@KWRegan, thank you for the reference to Friedberg numbering. I was not aware of it.<br /><br />However, I think the word "entails" is overly strong. I would say that the Church-Turing thesis presupposes universal computing machines exist (which, by their nature, support APS's), in much the same way "all crows are black" presupposes black crows exist. The C-T thesis was formulated only after several such systems were observed to be able to simulate themselves and each other.<br /><br />If, tomorrow, someone exhibited a "white crow" which falsified the C-T thesis, would that say anything at all about the recursion theorem? I don't think so, because the theorem follows from what we already know to exist, and the C-T thesis is essentially a statement about what does *not* exist, i.e., effectively calculable functions that can't be expressed as Turing machines (or any of their many equivalents.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79608659503656158572012-11-23T13:45:13.855-05:002012-11-23T13:45:13.855-05:00In course notes I wrote for our grad intro theory ...In <a href="http://www.cse.buffalo.edu/~regan/cse596/CSE596pgthms.pdf" rel="nofollow">course notes</a> I wrote for our grad intro theory course, I present the Recursion Theorem as a consequence of having <b>eval</b> (same as universal-sim in comments above) and <b>subst</b>itution. A student asked why can't we simply have a program read its own code stored in a file, which let me emphasize the point that RT follows in <i>any</i> programming language that has these two properties (which define "acceptable programming system", APS), even if it has no idea of file-reading or even direct support for strings. <br /><br />An example of a non-APS system is a <a href="http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jsl/1183733349" rel="nofollow">"Friedberg numbering"</a>. Here every partial recursive function has a unique code, so no RT. This does not gainsay Bill's answer, since the C-T Thesis entails that APS exist. My notes go further by presenting the RT construction in programming-y terms.KWReganhttp://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9043861238680415052012-11-23T06:20:20.858-05:002012-11-23T06:20:20.858-05:00Indeed, Turing machines can be thought of a "...Indeed, Turing machines can be thought of a "Harvard architecture" of sorts, with a "program" hard-coded in inaccessible "ROM".<br /><br />@NP Slagle, the more I think about it, the more I think what you say is incorrect, or at least quite misleading. Adding "the proper steps to the machine" requires that you already *know* the makeup of the machine -- ask anyone who's tried writing a quine.<br /><br />Example: Say I have a 6502-based computer in front of me. In 6502, I can write a 6502 emulator. In 6502, I can also devise a program which prints itself out without examining itself in memory. But in no way can I write a 6502 program which, when run on my computer, tells me how the processor is constructed from logic gates, *and* when run on my 6502 emulator, tells me what instructions I used in my 6502 emulator.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26300770859870820462012-11-22T07:33:21.895-05:002012-11-22T07:33:21.895-05:00So, what about Harvard architecture computers? Or ...So, what about Harvard architecture computers? Or a program that does not live in a modifiable piece of memory? Many, many computers do not conform to the classic von Neumann architecture in all aspects. Apart from the problem you noted, there is also the omission of stating which particular machine model your assume. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75134213478491294762012-11-21T13:27:29.778-05:002012-11-21T13:27:29.778-05:00@NP Slagle, @Anonymous 3:52AM: can you be more spe...@NP Slagle, @Anonymous 3:52AM: can you be more specific? I don't see anything in that Wikipedia article that comes out and says that a TM can obtain its own description.<br /><br />Of course, a TM can be *devised* that writes out its own description onto the tape, but there's nothing *obliging* one to do so.<br /><br />Are you suggesting the existence of a "subroutine" of sorts that could be added to an arbitrary TM, that would cause it to write a description of the (entire) TM to the tape? If so, I have a very hard time imagining this subroutine.<br /><br />Anything more involved than that (e.g. adding "debugging prints" to the state transition rules, then deducing a description of the machine from the execution trace) would seem to require some knowledge of the structure of the machine in the first place, which in some sense defeats the point.<br /><br />Of course, I may be completely misunderstanding what you are suggesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42465540947910104702012-11-21T13:12:50.367-05:002012-11-21T13:12:50.367-05:00I was just about to post a comment saying "I ...I was just about to post a comment saying "I don't see how this intuition comes from the Church-Turing thesis; it seems to come instead from the idea that Turing machines can simulate themselves" -- then I saw the first sentence of your comment :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59887403924462694472012-11-21T10:46:09.127-05:002012-11-21T10:46:09.127-05:00TA = Teaching Assistant. TA = Teaching Assistant. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7662477947884271622012-11-21T04:52:50.242-05:002012-11-21T04:52:50.242-05:00@Anonymous: It can. Go read the Wikipedia article...@Anonymous: It can. Go read the Wikipedia article on 'Universal Turing machine'.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28686271726095582822012-11-21T00:22:30.987-05:002012-11-21T00:22:30.987-05:00As it turns out, a Turing machine can, in fact, ob...As it turns out, a Turing machine can, in fact, obtain its own description, then use the description for some task, such as printing the description or recursively calling itself in simulation. The recursion theorem guarantees this. One need only add the proper steps into the machine.NP Slaglehttp://www.blogger.com/profile/06322388966706601689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3458557662767736242012-11-20T19:42:00.315-05:002012-11-20T19:42:00.315-05:00I don't think this requires the Church-Turing ...I don't think this requires the Church-Turing thesis, merely the existence of universal Turing machines.<br /><br />Suppose you have a universal Turing machine. It accepts the program M as input, and simulates its execution --- but the original program is still sitting in the input buffer. The UTM simulation will not allow the simulated program M to access this data. At a certain point, you could imagine that the UTM has a special instruction which "breaks out" of the simulation and grants access to the input.<br /><br />This is essentially your argument, it has nothing to do with physical machines, only with the interaction between the Universal Turing Machine and the program it is simulating.Davidhttp://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45287335996681839642012-11-20T19:19:13.946-05:002012-11-20T19:19:13.946-05:00Sure, a PC has something called "RAM" wh...Sure, a PC has something called "RAM" which it can look at (disregard concerns about the OS enforcing that only certain memory is readable etc.)<br /><br />But a Turing machine does not!<br /><br />A Turing machine has a tape, yes, but the particular instructions of a particular Turing machine program are not written anywhere on that tape.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13277867205186379662012-11-20T18:09:29.638-05:002012-11-20T18:09:29.638-05:00I just got back from giving a lecture covering the...I just got back from giving a lecture covering the Y-combinator and saw this. While the Y-combinator is definitely also mysterious, perhaps it is easier to check that it spits out fixed points for any lambda expression F, and may be the intuition of applying F to itself infinitely many times to converge to a fixed point can be suggested as some vague intuition for coming up with such a combinator.<br /><br />Venkathttp://www.cs.cmu.edu/~venkatgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65970377109651632532012-11-20T17:02:24.020-05:002012-11-20T17:02:24.020-05:00The really interesting question is: Who is this in...The really interesting question is: Who is this infamous TA ? ;-)Anonymousnoreply@blogger.com