  We study two modifications of the Post Correspondence Problem (PCP), namely
1) the bi-infinite version, where it is asked whether there exists a
bi-infinite word such that two given morphisms agree on it, and 2) the
conjugate version, where we require the images of a solution for two given
morphisms are conjugates of each other. For the bi-infinite PCP we show that it
is in the class $\Sigma_2^0$ of the arithmetical hierarchy and for the
conjugate PCP we give an undecidability proof by reducing it to the word
problem for a special type of semi-Thue systems.
