Turing-unrecognizable language - what TM does?

Problem Detail: 

I have a problem giving "intuitive" explanation to turing-unrecognizable languages.

We can prove that, say, ${\overline{A_{TM}}}$ is not turing-recognizable, because that would make ${{A_{TM}}}$ decidable, but what would the $TM$ do if it doesn't accept, reject of loop?

Asked By : alex440

Answered By : Louis

You might be a little confused by a definition somewhere. A TM $M$ is a recognizer for a language $L$ if it

• Accepts every string in $L$
• Either rejects or loops on every string not in $L$

Now let's think about the language ${\overline{A_{TM}}}$. An input $\langle N,x\rangle$ is in ${\overline{A_{TM}}}$ if either:

• $N$ rejects on $x$.
• $N$ loops on $x$

So any recognizer will need to figure out (in finite time) that $N$ is going to loop on some input, which is just the halting problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24550