CODEWITHSUNDEEP
turing-machines
Dragos Iancu
Dragos Iancu

Reputation: 85

Proving a language is in RE/R/coRE

Lets say we have a function for a Turing Machine like this one:

𝑓(𝑀) = { 1, for any 𝑤 where 𝑀(𝑤) halts only if w is a palindrome of even length
          0, otherwise

How can one prove that it belongs (or not) to RE, R, coRE.

I mean, I know we can use a turing reduction using the f-halt to prove that it is not belonging to R. But what about RE/coRE?

Upvotes: 1

Views: 3327

Answers (1)

Patrick87
Patrick87

Reputation: 28312

A language is RE if we can halt-accept for any string in the language. A language is coRE if we can halt-reject for any string not in the language. R is the intersection of RE and coRE; a language is R if we can halt-accept on strings in the language and halt-reject on strings not in the language.

You already know that the language isn't R. This can also be seen by Rice's theorem: halting only on palindromes of even length is a semantic property of the accepted language (subset of EPAL), so the inclusion problem isn't decidable. This tells you that the language cannot be both RE and coRE, though it might be neither.

Given a machine M, can we determine that it does only accept strings which are even-length palindromes? This seems unlikely. We would need a way to be sure that all strings - maybe infinitely many - are even-length palindromes. We can't just find a counterexample and be done.

Given a machine M, can we determine that it doesn't only accept strings which are even-length palindromes? We sure can! We can interleave executions of copies of this machine such that arbitrarily many possible input strings get arbitrarily much computing time; if M accepts any particular string, we can eventually find out, and if it accepts one that isn't an even-length palindrome, we can eventually tell.

So, this language:

  • is coRE
  • is not RE
  • is not R

Upvotes: 1

Related Questions