Re: Halting problem undecidable or semidecidable?

devriese@xxxxxxxxx wrote: 

The halting problem is often listed as "undecidable". However, surely
this is a semi-decidable problem? If a program halts, I could simply
run the program and wait until it halts. Thus, questions with answer
"yes" can be answered.

It seems to be that even the converse, "does a given program _not_
halt", is semi-decidable. Again, simply run the program. If it halts,
then the answer is "no". Thus, question with answer "no" can be
answered.

The naming conventions here are somewhat misleading. This is how the labels correspond:

language problem
--------------------------------
recursive decidable
recursively enumerable semidecidable\ --- | undecidable
not r.e. /

So:
languages that are not recursive correspond to undecidable problems.
a decidable problem is also semidecidable (but not the other way around).
and to your specific question surely this is a semi-decidable problem?", yes, it is both semi- and un-decidable.

The vocabulary choice is annoying because if it is semi- meaning partially decidable, then one might informally infer that it is not totally un- decidable, and so not undecidable. That is unfortunately
not how the vocabulary works, so you shouldn't infer that.


Are there simple examples of problems that are _actually_ undecidable? 

totality of a TM (Jan's example) is the "simplest" undecidable but not r.e.
problem ..er.. language ... er ..thingy. See "arithmetic hierarchy".

--
Mitch Harris
(remove q to reply)

.