Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!cornell!oravax!ian From: ian@oravax.UUCP (Ian Sutherland) Newsgroups: comp.theory Subject: The word "undecidable" (WAS: Question on halting problem) Message-ID: <2285@oravax.UUCP> Date: 2 May 91 02:02:56 GMT References: <1991Apr26.135918.8607@m.cs.uiuc.edu> <1161@creatures.cs.vt.edu> <2283@oravax.UUCP> <1991Apr29.154023.18594@math.ucla.edu> <19592@cs.utexas.edu> Reply-To: ian@oravax.odyssey.UUCP (Ian Sutherland) Organization: ORA Corporation, Ithaca, New York Lines: 21 In article <19592@cs.utexas.edu> turpin@cs.utexas.edu (Russell Turpin) writes: >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. Perhaps some people use "undecidable" this way, but that was not what I was taught. The notion you call "undecidable" above, I was taught to call "incomplete", and an "undecidable" theory was one whose set of theorems is not recursive. I believe this usage is standard; most logicians I know use the same terminology I do. >By extension, such a sentence is sometimes said to be >undecidable in the concerned theory. I was taught to call such sentences "independent of" the theory in question. -- Ian Sutherland ian@cambridge.oracorp.com Sans peur