Reverse Post Correspondence Problem and Undecidability of $5^{\prime }\to 3^{\prime }$ String Assembly Systems

Benedek Nagy

The Post Correspondence Problem is as follows: having a set of dominoes, is there any (maybe repeating) sequence of them such that the words formed by the upper parts and the lower…