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

Improve this question
$\endgroup$
1
  • $\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$
    – John L.
    Jul 4, 2019 at 3:23

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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