I want to know whether Post Correspondence Problem (PCP) is recognizable. I learnt how to demonstrate the undecidability of PCP. I thought to use the similar approach for recognizability too i.e. to considering MPCP and show whether it is recognizable. I am not sure if it is a good approach.

  • $\begingroup$ You can not use the approach for showing that something is undecidable for showing that it is decidable. Well, that's not quite true: you can reduce PCP to another recognizable language. That's typically more hassle than describing a recognizer -- just do that. $\endgroup$ – Raphael Feb 20 '16 at 10:50
  • $\begingroup$ @Raphael, no, no hassle at all for some cases. $\endgroup$ – Shreesh Feb 20 '16 at 17:06
  • $\begingroup$ @Raphael The question isn't asking to show that PCP is decidable -- it's asking about it being recognizable (recursively enumerable). $\endgroup$ – David Richerby Feb 20 '16 at 17:09
  • $\begingroup$ @DavidRicherby True. My first sentence remains true if you replace both instances of "decidable" with "semi-decidable". $\endgroup$ – Raphael Feb 21 '16 at 16:58

We can recognize acceptable inputs of PCP by exhaustively checking all valid possibilities (preferably by non-deterministic TM). That is it!. If the input is acceptable then the TM will stop, if it is not then the TM may not stop. Thus PCP is an RE language. Recognizability should not be confused with decidability.

We can do the same with deterministic TM by essentially simulating each thread of NDTM one step at a time.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.