Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!turpin From: turpin@cs.utexas.edu (Russell Turpin) Newsgroups: comp.theory Subject: Re: Question on halting problem Summary: Terminology sometimes confuses the issue. Message-ID: <19592@cs.utexas.edu> Date: 30 Apr 91 02:14:41 GMT References: <1991Apr26.135918.8607@m.cs.uiuc.edu> <1161@creatures.cs.vt.edu> <2283@oravax.UUCP> <1991Apr29.154023.18594@math.ucla.edu> Organization: U. Texas CS Dept., Austin, Texas Lines: 31 ----- In article <1991Apr29.154023.18594@math.ucla.edu> hbe@math.ucla.edu (H. Enderton) writes: > 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. ... I have found that the terminology involved also confuses some people. In logic, one calls a theory undecidable if there is a proposition P such that neither P nor ~P is provable in the theory. By extension, such a sentence is sometimes said to be undecidable in the concerned theory. Thus, there is a natural kind of question many students ask: Might Fermat's Last Theorem (or some other proposition) be undecidable in first-order arithmetic (or whatever theory is concerned)? If this question is asked of someone whose natural framework is complexity theory, where decidability refers to a problem class, the answer is: of course it is decidable, because it only has one problem instance. In this framework, people don't refer to propositions as decidable or not, but rather as provable or not. The confusion is compounded because there are undecidable (sense 1) propositions in a theory iff the question of whether an arbitrary proposition is provable in a theory is is undecidable (sense 2). I know, this is not any great issue, it is just a matter of terminology. I thought it was worth mentioning only because I have seen people confused over it on several occasions. Russell