Is Post's correspondence problem recognizable? 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.
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.