Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!usc!ucla-cs!ucla-ma!sonia!hbe From: hbe@sonia.math.ucla.edu (H. Enderton) Newsgroups: comp.theory Subject: Re: Question on halting problem Message-ID: <1991Apr29.154023.18594@math.ucla.edu> Date: 29 Apr 91 15:40:23 GMT References: <1991Apr26.135918.8607@m.cs.uiuc.edu> <1161@creatures.cs.vt.edu> <2283@oravax.UUCP> Sender: news@math.ucla.edu Reply-To: hbe@math.ucla.edu (H. Enderton) Organization: UCLA Mathematics Department Lines: 17 Ian Sutherland has made an interesting point. On the one hand, for a particular (fixed) Turing machine and a particular (fixed) input, the *truth* of its halting does not qualify as a "decision problem"--either it does or it doesn't. On the other hand, the *provability* of its halting can be an interesting question. For a related example, take Rado's sigma function (in the Busy Beaver problem). This grows faster than any recursive function. Sure, there is some machine that can write sigma(5) on its output tape. But would we know that *that* was what it had done? Only if we can prove an equation "sigma(5) = xxx" (where xxx is the right answer, whatever it is). And (under reasonable assumptions) we can prove in ZFC equations of the form "sigma(m)=n" for only finitely many m's. And it may well be that m = 5 is not one of them. Moral: It's one thing to know that a Turing machine *exists* that has the answers you seek; it's quite another to know what that machine is.