patternMinor
Turing-unrecognizable language - what TM does?
Viewed 0 times
whatlanguagedoesunrecognizableturing
Problem
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?
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?
Solution
You might be a little confused by a definition somewhere. A TM $M$ is a recognizer for a language $L$ if it
Now let's think about the language ${\overline{A_{TM}}}$. An input $\langle N,x\rangle$ is in ${\overline{A_{TM}}}$ if either:
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.
- 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.
Context
StackExchange Computer Science Q#24550, answer score: 6
Revisions (0)
No revisions yet.