Reversible machines and Post’s correspondence problem for biprefix morphisms. (English) Zbl 0604.68057

The existence of universal reversible Turing machines and the consequent undecidability of Post’s correspondence problem for injective morphisms have been known for a long time. It is easy to see that the undecidability holds true even for bounded delay morphisms, a subclass of injective morphisms. In the present paper this result is further strengthened by constructing a universal reversible Turing machine which can be simulated by biprefix morphisms, a subclass of bounded delay morphisms. As a consequence, Post’s correspondence problem is undecidable even for biprefix morphisms. This holds true both for ordinary words (finite index sequences) and for \(\omega\)-words (infinite index sequences). As a matter of fact, even a somewhat stronger result is obtained since the morphisms used in the simulation turn out to be of particularly simple type among biprefix morphisms: they are of the so- called totally synchronized type.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata