CODEWITHSUNDEEP
turing-machines
PTN
PTN

Reputation: 1692

Classify a language as Turing-recognizable or co-Turing-recognizable

I have this language

L = {<M> | M is a TM that accepts w whenever it accepts w^R}

I was able to prove that this language is undecidable.

But is this language Turing-recognizable or co-Turing-recognizable?

Upvotes: 1

Views: 863

Answers (1)

Patrick87
Patrick87

Reputation: 28302

A language is RE if a TM can halt-accept on all strings in the language. A language is coRE if a TM can halt-reject on all strings not in the language. For L to be RE, we would need to be able to tell that TM always accepts w^R when it accepts w. For L to be coRE, we would need to be able to tell that TM accepts some w but not the corresponding w^R. It is neither RE nor coRE.

  • It is not RE because if a particular TM happens to accept the empty language, and therefore belongs to L, there is no way to recognize this fact. A recognizer for our language would allow us to recognize TMs that accept the empty language, an impossibility.

  • It is not coRE because if a particular TM happens to accept a language consisting of a single non-palindromic string, and therefore doesn't belong to L, there is no way to recognize this fact. A recognizer for our language would allow us to recognize TMs that accept a single non-palindromic string, an impossibility.

Upvotes: 1

Related Questions