Recursive Unsolvability of a problem of Thue
- 12 March 1947
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 12 (1) , 1-11
- https://doi.org/10.2307/2267170
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.Keywords
This publication has 5 references indexed in Scilit:
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946
- Recursively enumerable sets of positive integers and their decision problemsBulletin of the American Mathematical Society, 1944
- Formal Reductions of the General Combinatorial Decision ProblemAmerican Journal of Mathematics, 1943
- On Computable Numbers, with an Application to the EntscheidungsproblemProceedings of the London Mathematical Society, 1937
- An Unsolvable Problem of Elementary Number TheoryAmerican Journal of Mathematics, 1936