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
- 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
- Cited by