This was an old exam question. I think, though, that it is some sort of trick question. Isn't this simply decidable and therefore also trivially co-semidecidable?

Because I wouldn't know how to prove that it is co-semidecidable for itself. Being co-semidecidable means that there is a chance that the algorithm (that checks whether it is a palindrome or not) never stops, even if the solution is a palindrome indeed. But I don't see why this should be the case. An algorithm should always be able to check the condition and give a clear answer, right?

  • $\begingroup$ I would tend to agree with your first paragraph. Whether it is a PCP solution it does not matter: being a palindrome is decidable hence RE and co-RE. Double check that the question is not considering the different problem: given a word, determine whether it is a palindromic PCP solution. $\endgroup$ – chi Jun 28 '18 at 13:13
  • $\begingroup$ No, the question clearly states that we already have a PCP solution and that it has to be determined whether this solution is a palindrome or not. $\endgroup$ – Julian Jun 28 '18 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.