0

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?

Julian
  • 133
  • 4
  • 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. – chi Jun 28 '18 at 13:13
  • 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. – Julian Jun 28 '18 at 14:33

0 Answers0