0
$\begingroup$

Is the Halting problem in the class of undecidable problems, or it is just in the set of unrecognizable problems?

I understand that if it is undecidable, then it is also unrecognizable. I have seen the two being used interchangeably, however I believe it is possible for a language to be recognizable but not decidable, so was hoping for clarification

$\endgroup$
  • $\begingroup$ Could you tell us the textbook you are using or the online course you are attending? I have never seen undecidable and unrecognizable are used interchangeably, although the latter implies the former. $\endgroup$ – Apass.Jack Jul 4 at 3:23
0
$\begingroup$

Encode a Turing machine $M$ and an input string $I$ into a single string $(M,I)$. Create a Turing machine $U$ that behaves as follows:

  • $U$ rejects any input that is not a valid encoding

  • When given valid input $(M,I)$, $U$ emulates the behavior of $M$ with input $I$

  • If $M$ eventually halts when given input $I$ then $U$ halts and accepts input $(M,I)$

If $M$ eventually halts when given input $I$ then $U$ will (eventually) accept input $(M,I)$. So $U$ recognizes the language

$L=\{(M,I) : M \text{ eventually halts when given input } I \}$

Note, however, that $U$ does not decide $L$ because it does not explicitly reject $(M,I)$ if $M$ never halts given input $I$ - in this case $U$ will also never halt when given input $(M,I)$.

The Halting Theorem tells us that $L$ is undecideable (over Turing machines) but we have just shown that $L$ is recognizeable.

$\endgroup$

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