Re: Halting problem undecidable or semidecidable?

In comp.theory, Jym wrote:
> There is a fundamental difference between saying yes and saying no. If you
> considered it in terms of languages, you can tell if a given program
> belongs to the language HALT (after a finite unbounded and unknown time).
> You will *never* be able to tell that a given program *does not* belong to
> HALT (that is belongs to co-HALT).
>
> Semi-decidable is really "halt on 'yes' or run forever", not "halt on 'no'
> or run forever.
>
> Notice that if both a problem and its co-problem are semi-decidable, then
> the problem is decidable : just run 'in parallel' both TMs, one day one of
> the two will answer 'yes' and you'll have your final answer.

I think a good follow-up question, and perhaps even the intended
question, could be: are there problems that are undecidable, and whose
converses are also undecidable (so not semi-decidable).

The problem "given a TM M, decide wether it halts on all possible
inputs", is such a problem: if the answer is yes, you will still have
to check all possible inputs, if the answer is no, you will have to
solve the converse of the halting problem (find a program that does
not halt).


Jan

.

Relevant Pages

  • Re: As a programmer of both languages...
    ... Your example struct is equally valid in both languages, ... C++ treats it exactly the same as C. Saying you can't write anything ... overloading) amounts to nothing..... ... jacob at jacob point remcomp point fr ...
    (comp.lang.c)
  • Re: Peter Olcotts Source of Confusion
    ... Actually when the one mistake is saying that the halting ... >were redefining what the Halting Problem was. ... >the link will halt or not. ... odd nor even. ...
    (sci.logic)
  • Re: As a programmer of both languages...
    ... Your example struct is equally valid in both languages, ... C++ treats it exactly the same as C. Saying you can't write anything ... I have never written anything serious in C without using data types and structures. ... aren't objects but just integer error codes, ...
    (comp.lang.c)
  • Re: IDEs, syntactic vs. semantic highlighting, etc.
    ... That's really saying some awful things about Java -- not that I'm ... Perl's OO is ugly as sin (and I'm a fan of Perl, ... languages, I really do find statements like this cute (not ...
    (comp.lang.ruby)
  • Re: Halting problem undecidable or semidecidable?
    ... > There is a fundamental difference between saying yes and saying no. ... > considered it in terms of languages, you can tell if a given program ... > belongs to the language HALT. ...
    (comp.theory)
Loading