Decidability of the binary infinite Post Correspondence Problem

AbstractWe shall show that it is decidable for binary instances of the Post Correspondence Problem whether the instance has an infinite solution. In this context, a binary instance (h,g) consists of two morphisms h and g with a common two element domain alphabet. An infinite solution ω is an infinite word ω=a1a2… such that h(ω)=g(ω). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem