1

I get the fact that due to diagonalization argument number of language is uncountable and since TM are countable, hence there are some language which is not recognized by the Turing machine. I also read this recognizable vs decidable question.The main difference between them is in recognizable language there is a chance of looping which is not present in decidable language. I want to know whether there is a relationship between unrecognizable and undecidable language. A simple example will be helpful.

Thanks.

Community
  • 1
motiur
  • 207
  • 1
  • 3
  • 7

1 Answers1

3

Every unrecognizable language is undecidable, but there are undecidable languages which are recognizable. In fact, the decidable languages are exactly those which are recognizable and co-recognizable (that is, have recognizable complement).

The Halting Problem (the set of codes for machines which halt on their own code as input - $\{e: \Phi_e(e)\downarrow\}$) is an example of a recognizable, but not decidable, language.

Alon Amit
  • 15,286
  • 52
  • 88
Noah Schweber
  • 230,652
  • 21
  • 310
  • 560