9
$\begingroup$

This is what is known about the halting problem and semi-decidability :-

The 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 the 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.

Improve this question
$\endgroup$
6
  • $\begingroup$ "Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language" Why not? Machine has to halt in order to accept the word. Also I am not sure there is any such thing as semi-decidable. I only know decidable or undecidable. Halting problem is undecidable. $\endgroup$
    – User Not Found
    Jul 15, 2017 at 8:17
  • 2
    $\begingroup$ Note that this has nothing at all to do with the Turing test. $\endgroup$
    – Raphael ♦
    Jul 15, 2017 at 8:19
  • $\begingroup$ @ArghyaChakraborty Semi-decidable means that for any given problem, there exists a Turing machine for that problem that will always terminate for accepted input, but will either terminate or not terminate for all other input. (Oops,I just noticed OP wrote it in), it is a thing though. $\endgroup$
    – Micrified
    Jul 15, 2017 at 11:28
  • $\begingroup$ @Owatch Ok now you are confusing me...is the next statement true? "Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language" $\endgroup$
    – User Not Found
    Jul 15, 2017 at 13:38
  • $\begingroup$ @ArghyaChakraborty I'm only telling you that the term "Semi-Decidable" is valid, and echoing what the OP defined it as. If you want to ask me about the halting problem with relation to this word, then I can answer that too I guess. "Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language": False. Any machine in the halting language will always terminate for input belonging to the language. $\endgroup$
    – Micrified
    Jul 15, 2017 at 16:37

1 Answer 1

Reset to default
15
$\begingroup$

Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity.

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.

No, that's not what it says. The halting problem is the computational problem of deciding whether $H$ halts on $x$, given $x$ and $H$ as input. It is important to note that "decide" here means "say yes if it is so, and say no if it is not".

The undecidability of the halting problem states that there is no single algorithm (Turing machine) that solves the halting problem for all $H$ and $x$.

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?

After the above clarification, your confusion here should be clear. It doesn't matter what "we can say". The "semi halting problem" is relaxed: the algorithm still has to say "yes" if $H$ halts on $x$, but it can do whatever it please if it does not (except answer "yes").

This is trivial to implement: just run $H$ on $x$. If it halts, answer "yes". If not, it doesn't matter since we're allowed to loop.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So the statement which I wrote about halting problem was actually about the undecidability of halting problem ? According to you semi-halting problem is recursively enumerable and hence Semi-decidable. So is the actual halting problem undecidable and not Semi-decidable ? I am sorry if I am asking trivial questions, I am new to this. $\endgroup$
    – Zephyr
    Jul 15, 2017 at 8:40
  • $\begingroup$ "So the statement which I wrote about halting problem was actually about the undecidability of halting problem ?" -- yes. In TCS, "problem" is a technical, not to be confused with the normal English word. See also here. "So is the actual halting problem undecidable and not Semi-decidable ?" -- No. I went a little informal there (hence the quotation marks): it's the halting problem but expressed in terms of semi-decidability. The halting problem is undecidable but semi-decidable. $\endgroup$
    – Raphael ♦
    Jul 15, 2017 at 9:37
  • $\begingroup$ According to what you said about undecidability , there is no algorithm that solves the halting problem for all H and x, which means no algorithm can decide whether H halts on x, given x and H as an input. So even if we give an input belonging to the language the algorithm can't decide whether it will halt so it should be completely undecidable. $\endgroup$
    – Zephyr
    Jul 15, 2017 at 10:19
  • 1
    $\begingroup$ There is no such thing as "completely undecidable". And no, no algorithm can decide, but it can still semi-decide. These are different notions; you should check out the formal definitions. Intuitive analogy: until after your death, you can never say with confidence "never will a mole poop on my head". But if it happens, you can state with absolute certainty, "a mole pooped on my head". $\endgroup$
    – Raphael ♦
    Jul 15, 2017 at 11:13
  • 4
    $\begingroup$ If the question of halting is undecidable, that doesn't mean that I can't decide sometimes whether it halts. For halting instances, I can decide that they halt by just waiting until they halt. For non-halting instances, I may sometimes be able to provide a proof that they don't halt, and that decides them. $\endgroup$
    – gnasher729
    Jul 15, 2017 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.