Recursive Unsolvability of a problem of Thue

Thue's problem is the problem of determining for arbitrarily given strings A, B on al, whether, or no, A and B are equivalent, and this problem is more readily placed if it is restated in terms of a special form of the canonical systems of [3].

Abstract

Alonzo Church suggested to the writer that a certain problem of Thue [6] might be proved unsolvable by the methods of [5]. We proceed to prove the problem recursively unsolvable, that is, unsolvable in the sense of Church [1], but by a method meeting the special needs of the problem. Thue's (general) problem is the following. Given a finite set of symbols α 1 , α 2 , …, αμ, we consider arbitrary strings (Zeichenreihen) on those symbols, that is, rows of symbols each of which is in the given set. Null strings are included.