Recursive Unsolvability of a problem of Thue

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 α₁, α₂, …, αμ, 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.