# Is the halting problem undecidable or unrecognizable? [duplicate]

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

• 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. – John L. Jul 4 '19 at 3:23

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.