Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Turing machines to word problems
Published online by Cambridge University Press: 05 June 2014
Edited by
Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Summary
Abstract. We trace the emergence of unsolvable problems in algebra and topology from the unsolvable halting problem for Turing machines.
§1. Introduction. Mathematicians have always been interested in being able to calculate with or about the things they study. For instance early developers of number theory and the calculus apparently did extensive calculations. By the early 1900s a number of problems were introduced asking for general algorithms to do certain calculations. In particular the tenth problem on Hilbert's influential list asked for an algorithm to determine whether an integer polynomial in several variables has an integer solution.
The introduction by Poincaré of the fundamental group as an invariant of a topological space which can often be finitely described by generators and relations led to Dehn's formulation of the word and isomorphism problem for groups. To make use of such group invariants we naturally want to calculate them and determine their properties. It turns out many of these problems do not have algorithmic solutions and we will trace the history and some of the ideas involved in showing these natural mathematical problems are unsolvable.
In the 1930s several definitions of computable functions emerged together with the formulation of the Church-Turing Thesis that these definitions captured intuitive notions of computability. Church and independently Turing showed that there is no algorithm to determine which formulas of first-order logic are valid, that is, the Entscheidungsproblem is unsolvable.
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 329 - 385Publisher: Cambridge University PressPrint publication year: 2014
References
[1] , A proof of Higman's embedding theorem using Britton extensions of groups, Word problems, Studies in Logic and the Foundations of Mathematics, vol. 71, 1973, pp. 1-18.Google Scholar
[2] , Algorithmic unsolvability of problems of recognition of certain properties of groups, Doklady Akademii Nauk SSSR. New Series, vol. 103 (1955), pp. 533-535, (Russian).Google Scholar
[3] , Finitely presented groups and algorithms, Doklady Akademii Nauk SSSR. New Series, vol. 117 (1957), pp. 9-12, (Russian).Google Scholar
[4] , Unsolvability of some algorithmic problems in the theory of groups, Trudy Moskovskogo Matematischeskogo Obshchestva, vol. 6 (1957), pp. 231-298, (Russian).Google Scholar
[5] and , Decision problems for groups and semigroups, Uspekhi Matematicheskikh Nauk, vol. 55 (2000), pp. 3-94, translated in Russian Mathematical Surveys, vol. 55 (2000), pp. 207–296.Google Scholar
[6] , , and , Some unsolvableproblems about elements and subgroups of groups, Mathematica Scandinavica, vol. 7 (1959), pp. 191-201.Google Scholar
[7] and , Subgroups of direct products of free groups, Journal of the London Mathematical Society. Second Series, vol. 30 (1984), pp. 44-52.Google Scholar
[8] and , Some two-generator one-relator non-hopfian groups, Bulletin of the American Mathematical Society, vol. 68 (1962), pp. 199-201.Google Scholar
[10] , On a property of the Boone groups II, Algebra i Logika, vol. 6 (1967), pp. 15-24.Google Scholar
[12] , Degrees of unsolvability of the conjugacy problem for finitely presented groups, Algebra i Logika, vol. 7(1968), pp. 4-70.Google Scholar
[13] , Mal'cev's problem and groups with a normal form, Word problems II (Conference on Decision Problems in Algebra, Oxford, 1976), Studies in Logic and the Foundations of Mathematics, vol. 95, North-Holland, Amsterdam-New York, 1980, with the collaboration of , pp. 29-53.
[14] and , Algorithmic and combinatorial algebra, Mathematics and Its Applications, vol. 255, Kluwer Academic Publishers, Dordrecht-Boston-London, 1994.
[15] , Certain simple unsolvable problems in group theory, I, II, III, IV, V, VI, Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae. Series A, vol. 57 (1954) (= Indagationes Mathematicae, vol. 16) pp. 231–237 and 492–497; vol. 58 (1955) (=Indagationes Mathematicae, vol. 17) pp. 252–256 and 571–577; vol. 60 (1957) (= Indagationes Mathematicae, vol. 19) pp. 22–27 and 227–232.Google Scholar
[18] , An analysis of Turing's “The Word Problem in Semi-Groups with Cancellation”, Annals of Mathematics, vol. 67 (1958), pp. 195-202.Google Scholar
[20] , Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups, Annals of Mathematics, vol. 84 (1966), pp. 49-84.Google Scholar
[21] , , and , On recursively unsolvable problems in topology and their classification, Contributions to mathematical logic (, editor), North-Holland, Amsterdam, 1968, pp. 13-74.
[22] and , An algebraic characterization of the solvability of the word problem, Journal of the Australian Mathematical Society, vol. 18 (1974), pp. 41-53.Google Scholar
[23] and , On a problem of J. H. C. Whitehead and a problem of Alonzo Church, Mathematica Scandinavica, vol. 19 (1966), pp. 185-192.Google Scholar
[24] , Simple examples of groups with unsolvable word problem, Matematicheskie Zametki, vol. 6(1969), pp. 521-532, translatedin Mathematical Notes, vol. 6, pp. 768–775.Google Scholar
[25] and , Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften, vol. 319, Springer-Verlag, Heidelberg-Berlin, 1999.
[26] , Solution to the word problem for certain types of groups, I, II, Proceedings of the Glasgow Mathematical Association, vol. 3 (1956), pp. 45-54, vol. 3 (1957), pp. 68-90.Google Scholar
[29] , The word problem for groups, Proceedings of the London Mathematical Society, vol. 8 (1958), pp. 493-506.Google Scholar
[31] and , Unrecognizability of manifolds, Annals of Pure and Applied Logic, vol. 141 (2006), pp. 325-335.Google Scholar
[32] , , and , Aspherical group presentations, Mathematische Zeitschrift, vol. 178 (1981), pp. 1-36.Google Scholar
[33] , Finitely presented groups with word problems of arbitrary degrees of insolubility, Proceedings of the London Mathematical Society. Third Series, vol. 14(1964), pp. 633-676.Google Scholar
[34] , An embedding theorem for finitely generated groups, Proceedings of the London Mathematical Society. Third Series, vol. 17 (1967), pp. 419-430.Google Scholar
[35] , Recursively enumerable degrees and the conjugacy problem, Acta Mathematica, vol. 122 (1969), pp. 115-160.Google Scholar
[36] , Representation of Turing deducibility by word and conjugacy problems in finitely presented groups, Acta Mathematica, vol. 128 (1972), pp. 73-90.Google Scholar
[37] , Obituary of William Werner Boone, Bulletin of the London Mathematical Society, vol. 17 (1985), pp. 168-174.Google Scholar
[38] , A simple presentation of a group with unsolvable word problem, Illinois Journal of Mathematics, vol. 30 (1986), pp. 230-234.Google Scholar
[39] and , The wordproblem in groups of cohomological dimension 2, Group St. Andrews 1997 in Bath, I (, , , and , editors), London Mathematical Society Lecture Notes, vol. 260, Cambridge University Press, 1999, pp. 211-218.
[40] (editor), Solvability, provability, definability: The collected works of Emil L. Post, Birkhauser, Boston, 1994.
[41] , Über unendliche diskontinuerliche Gruppen, Mathematische Annalen, vol. 69 (1911), pp. 116-144.Google Scholar
[42] , The word problem and residually finite groups, Notices of the American Mathematical Society, vol. 11 (1964), p. 734.Google Scholar
[43] , On the relation between the word problem and the conjugacy problem in finitely defined groups, Trudy Moskovskogo Matematischeskogo Obshchestva, vol. 9 (1960), pp. 329-356, (Russian).Google Scholar
[44] , Degrees of unsolvability of theword problem for finitely presented groups, Doklady Akademii Nauk SSSR, vol. 147 (1962), pp. 805-808, (Russian).Google Scholar
[45] , Degrees of unsolvability of the word problem for finitely defined groups, Izdatel'stvo “Nauka”, Moscow, 1967.
[46] , Hyperbolic groups, Essays on group theory (, editor), Mathematical Sciences Research Institute series, vol. 8, Springer-Verlag, 1987, pp. 75-263.
[47] , On some groups which cannot be finitely presented, Journal of the London Mathematical Society. Second Series, vol. 17 (1978), pp. 427-436.Google Scholar
[48] , A finitely relatedgroup with an isomorphic proper factor, Journal of the London Mathematical Society, vol. 26 (1951), pp. 59-61.Google Scholar
[49] , Subgroups of finitely presented groups, Proceedings of the Royal Society of London. Series A, vol. 262 (1961), pp. 455-475.
[50] , , and , Embedding theorems for groups, Journal of the London Mathematical Society, vol. 24(1949), pp. 247-254.Google Scholar
[51] , Review of [74], Mathematical Reviews, (1953), MR0052436 (14,618h) 20.0X.
[52] , Review of[75], Mathematical Reviews, (1956), MR0075196 (17,706a) 20.0X.
[53] and , Generic computability, turing degrees, and asymptotic density, Journal of the London Mathematical Society. Second Series, vol. 85 (2012), pp. 472-490.Google Scholar
[54] , , , and , Generic-case complexity, decision problems in group theory, and random walks, Journal of Algebra, vol. 264(2003), pp. 665-694.Google Scholar
[55] and , Word problems solvable in logspace, Journal of the Association for Computing Machinery, vol. 24 (1977), pp. 522-526.Google Scholar
[56] and , Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 89, Springer, Berlin-Heidleberg-New York, 1977.
[57] , Über diskontinuierliche Gruppen mit einer definierenden Relation (Der Freiheitssatz), Journal für die Reine und Angewandte Mathematik, vol. 163 (1930), pp. 141-165.Google Scholar
[58] , Das Identitàitsproblem für Gruppen mit einer definierenden Relation, Mathematische Annalen, vol. 106 (1932), pp. 295-307.Google Scholar
[59] , , and , Combinatorial group theory, Wiley, New York, 1966, (also corrected Dover reprint 1976).
[60] , On isomorphic matrix representations of infinite groups, Matcmatichesi Sbornik, vol. 8 (1940), pp. 405-422, translated as On the faithful representation of infinite groups by matrices, Translations of the American Mathematical Society. Second Series, vol. 45 (1965), pp. 1–18.Google Scholar
[61] , On the impossibility of certain algorithms in the theory of associative systems, Doklady Akademii Nauk SSSR. New Series, vol. 55 (1947), pp. 587-590.Google Scholar
[62] , The impossibility of certain algorithms in the theory of associative systems, Doklady Akademii Nauk SSSR. New Series, vol. 77 (1951), pp. 19-20.Google Scholar
[63] , Review of[76], Mathematical Reviews, (1956), MR0075197 (17,706b) 20.0X.
[64] , The insolubility of the problem ofhomeomorphy, Doklady Akademii Nauk SSSR. New Series, vol. 121 (1958), pp. 218-220.Google Scholar
[65] , Unsolvability of certain problems in topology, Doklady Akademii Nauk SSSR. New Series, vol. 123 (1958), pp. 978-980.Google Scholar
[66] , Insolubility of the problem of homeomorphy, Proceedings of the International Congress of Mathematicians, Cambridge 1958, Cambridge University Press, Cambridge, 1960, pp. 300-306.
[67] , Simple examples of undecidable associative calculi, Doklady Akademii Nauk SSSR. New Series, vol. 173 (1967), pp. 555-557.Google Scholar
[68] , The decision problem for some classes of sentences without quantifiers, The Journal of Symbolic Logic, vol. 8 (1943), pp. 61-76.Google Scholar
[69] , The occurrence problem for direct products of groups, Doklady Akademii Nauk SSSR, vol. 119(1958), pp. 1103-1105.Google Scholar
[70] , On group-theoretic decision problems and their classification Annals of Mathematics Studies, vol. 68, Princeton University Press, 1971.
[71] , The word problem in quotients of a group, Aspects of effective algebra (, editor), Upside Down A Book Company, Steel's Creek, 1981, Proceedings of a conference at Monash University August 1979, pp. 246-250.
[72] , Decision problems for groups—survey and reflections, Algorithms and classification in combinatorial group theory ( and , editors), MSRI Publications, vol. 23, Springer-Verlag, 1992, pp. 1-59.
[73] and , Algorithmically finite groups, Journal of Pure and Applied Algebra, vol. 215 (2011), pp. 2789-2796.Google Scholar
[74] , On the algorithmic unsolvability of the problem of identity, Doklady Akademii Nauk SSSR, vol. 85 (1952), pp. 709-712.Google Scholar
[75] , Unsolvability of the conjugacy problem in the theory of groups, Izvestiya Akademii Nauk SSSR Seriya Matematicheskaya, vol. 18 (1954), pp. 485-524.Google Scholar
[76] , On the algorithmic unsolvability of the word problem in group theory, Trudy Matematischeskogo Instituta Imeni V. A. Steklov, vol. 44 (1955), pp. 1-143, translated as American Mathematical Society Translations. Second Series, vol. 9 (1958), pp. 1-122.Google Scholar
[77] and , Das Wortproblem für Halbgruppen mit einseitiger Kürzungsregel, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 4 (1958), pp. 66-88, (Russian. German summary).Google Scholar
[78] , Almost every group is hyperbolic, International Journal of Algebra and Computation, vol. 2 (1992), pp. 1-17.Google Scholar
[79] , Finite combinatory processes—Formulation 1, The Journal of Symbolic Logic, vol. 1 (1936), pp. 103-105.Google Scholar
[80] , Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, vol. 65 (1943), pp. 197-215.Google Scholar
[81] , Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 281-316.Google Scholar
[82] , A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, vol. 54 (1946), pp. 264-268.Google Scholar
[83] , Recursive unsolvability of a problem of Thue, The Journal of Symbolic Logic, vol. 12 (1947), pp. 1-11.Google Scholar
[84] , Recursive unsolvability of group theoretic problems, Annals of Mathematics. Second Series, vol. 67(1958), pp. 172-194.Google Scholar
[85] , Computable algebra, general theory and theory of computable fields, Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341-360.Google Scholar
[86] Theory of recursive functions and effective computability, McGraw-Hill, 1967.
[87] , An introduction to the theory of groups, fourth ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, Berlin-Heidelberg-New York, 1995.
[88] , A short recursively unsolvable problem (abstract), The Journal of Symbolic Logic, vol. 21 (1956), pp. 111-112.Google Scholar
[89] and , Lehrbuch der Topologie, B. G. Teubner, Leipzig and Berlin, 1934, (Since WWII this book has been reprinted by Chelsea Publishing Company and is nowin the AMS–Chelsea book series published by the American Mathematical Society.).
[90] , Mathematical logic, Addison-Wesley, Reading, MA, 1967.
[91] , Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987.
[92] , Emil Post and his anticipation of Gödel and Turing, Mathematics Magazine, vol. 77 (2004), pp. 3-14.Google Scholar
[93] , The sieve method in group theory, Matematicheski Sbornik, vol. 25 (1949), pp. 3-50.Google Scholar
[94] , Application of the sieve method to the solution of the word problem for certain types of groups, Matematicheski Sbornik, vol. 25 (1949), pp. 251-274.Google Scholar
[95] , Solution of the word problem for groups with a k-reduced basis for k > 6, Izvestiya Akademii Nauk SSSR Seriya Matematicheskaya, vol. 13 (1949), pp. 483-494.Google Scholar
[96] , Probleme üher Veränderungen von Zeichenreihen nach gegeben Regeln, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Mathematisk-naturvidenskabelig klasse 1914, no. 10, 1914.
[97] , Üher die topologischen Invarienten mehrdimensionalen Mannigfaltigkeiten, Monatshefte für Mathematik und Physik, vol. 19 (1908), pp. 1-118.Google Scholar
[98] , Associative calculus with insoluble equivalence problem, Doklady Akademii Nauk SSSR, vol. 107 (1956), pp. 370-371.Google Scholar
[99] , The word problem in semi-groups with cancellation, Annals of Mathematics, vol. 52 (1950), pp. 491-505.Google Scholar
- 1
- Cited by