Question

This is what is know about halting problem and semi-decidability :-

Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

A language is said to be Semi-decidable if there exists a Turing machine which halts if a word belongs to the language (YES cases) and may reject or go into infinite loop if the word doesn't belong to the language (NO case).

Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable? I think it should be non recursively enumerable or undecidable.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top