Recursive Unsolvability of a problem of Thue

Emil L. Post

doi:10.2307/2267170

Extract

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.

Information

References

[1]

[1]Church, Alonzo, An unsolvable problem of elementary number theory, American journal of mathematics, vol. 58 (1936), pp. 345–363.CrossRef Google Scholar

[2]

[2]Post, Emil L., Finite combinatory processes—formulation 1, this Journal, vol. 1 (1936), pp. 103–105.Google Scholar

[3]

[3]Post, Emil L., Formal reductions of the general combinatorial decision problem, American journal of mathematics, vol. 65 (1943), pp. 197–215.CrossRef Google Scholar

[4]

[4]Post, Emil L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRef Google Scholar

[5]

[5]Post, Emil L., A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, vol. 52 (1946), pp. 264–268.CrossRef Google Scholar

[6]

[6]Thue, Axel, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-naturvidenskabelig Klasse 1914, no. 10 (1914), 34 pp.Google Scholar

[7]

[7]Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, ser. 2 vol. 42 (1937), pp. 230–265.CrossRef Google Scholar

[8]

[8]Turing, A. M., Computability and λ-definability, this Journal, vol. 2 (1937), pp. 153–163.Google Scholar

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Evans, Trevor 1951. On multiplicative systems defined by generators and relations. Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 47, Issue. 4, p. 637.

Kalmár, László 1952. Another proof of the Markov—Post theorem. Acta Mathematica Academiae Scientiarum Hungaricae, Vol. 3, Issue. 1-2, p. 1.

Boone, William W. 1954. Certain Simple, Unsolvable Problems of Group Theory. I1)1)Unless otherwise indicated, the results and proofs of this and subsequent related papers are as given (in somewhat more detail) in Several simple unsolvable problems of group theory related to the word problem, a doctoral dissertation accepted by Princeton University in April, 1952. The proof of the unsolvability of the quasi-MAGNUS problem was presented to a meeting of The Association for Symbolic Logic, April 28, 1951. (Abstract, Journal of Symbolic Logic, 16, 237.)Our thanks are due to Professors Alonzo Church and Roger Lyndon for their constructive suggestions regarding this dissertation; to Professor Wilhelm Magnus, for stimulating discussions regarding possible extensions.. Indagationes Mathematicae (Proceedings), Vol. 57, Issue. , p. 231.

Tamari, Dov 1955. Une contribution aux theories modernes de communication: machines de Turing et problemes de mot. Synthese, Vol. 9, Issue. 1, p. 205.

Hohn, F. E. Seshu, S. and Aufenkamp, D. D. 1957. The Theory of Nets. IEEE Transactions on Electronic Computers, Vol. EC-6, Issue. 3, p. 154.

1959. A Study in the Philosophy of Science. Vol. 25, Issue. , p. 682.

Shepherdson, J. C. and Sturgis, H. E. 1963. Computability of Recursive Functions. Journal of the ACM, Vol. 10, Issue. 2, p. 217.

Stahl, Walter R. and Goheen, Harry E. 1963. Molecular algorithms. Journal of Theoretical Biology, Vol. 5, Issue. 2, p. 266.

Richard Büchi, J. 1964. Regular canonical systems. Archiv für Mathematische Logik und Grundlagenforschung, Vol. 6, Issue. 3-4, p. 91.

Fischer, Patrick C. 1964. On formalisms for turing machines. p. 68.

Shepherdson, J. C. 1965. Machine Configuration and Word Problems of Given Degree of Unsolvability. Mathematical Logic Quarterly, Vol. 11, Issue. 2, p. 149.

Knuth, Donald E. 1965. On the translation of languages from left to right. Information and Control, Vol. 8, Issue. 6, p. 607.

FOSTER, J.M. 1966. Advances in Programming and Non-Numerical Computation. p. 83.

Yasuhara, Ann 1967. A Remark on Post Normal Systems. Journal of the ACM, Vol. 14, Issue. 1, p. 167.

Aanderaa, Stål and Fischer, Patrick C. 1967. The Solvability of the Halting Problem for 2-State Post Machines. Journal of the ACM, Vol. 14, Issue. 4, p. 677.

1967. Algebra. p. 799.

Singletary, W. E. 1967. The equivalence of some general combinatorial decision problems. Bulletin of the American Mathematical Society, Vol. 73, Issue. 3, p. 446.

Greibach, Sheila A. 1967. A note on pushdown store automata and regular systems. Proceedings of the American Mathematical Society, Vol. 18, Issue. 2, p. 263.

Cudia, Dennis F. and Singletary, Wilson E. 1968. Degrees of Unsolvability in Formal Grammars. Journal of the ACM, Vol. 15, Issue. 4, p. 680.

1968. Contributions to Mathematical Logic - Proceedings of the Logic Colloquium, Hannover 1966. Vol. 50, Issue. , p. 37.

Download full list

Article contents

Recursive Unsolvability of a problem of Thue

Extract

Information

Access options

Article purchase

Temporarily unavailable

References

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Article contents

Recursive Unsolvability of a problem of Thue

Extract

Information

Access options

Article purchase

Temporarily unavailable

References

Cited by

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests