Conceptual Confluence in 1936: Post and Turing

Martin Davis () and Wilfried Sieg
Additional contact information
Martin Davis: New York University, Department of Computer Science, Courant Institute of Mathematical Sciences
Wilfried Sieg: Carnegie Mellon University, Department of Philosophy

A chapter in Turing’s Revolution, 2015, pp 3-27 from Springer

Abstract: Abstract In 1936, Post and Turing independently proposed two models of computation that are virtually identical. Turing refers back to these models in his (The word problem in semi-groups with cancellation. Ann. Math. 52, 491–505) and calls them “the logical computing machines introduced by Post and the author”. The virtual identity is not to be viewed as a surprising coincidence, but rather as a natural consequence of the way in which Post and Turing conceived of the steps in mechanical procedures on finite strings. To support our view of the underlying conceptual confluence, we discuss the two 1936 papers, but explore also Post’s work in the 1920s and Turing’s paper (Solvable and unsolvable problems. Sci. News 31, 7–23). In addition, we consider their overlapping mathematical work on the word-problem for semigroups (with cancellation) in Post’s (Recursive unsolvability of a problem of Thue. J. Symb. Log. 12, 1–11) and Turing’s (The word problem in semi-groups with cancellation. Ann. Math. 52, 491–505). We argue that the unity of their approach is of deep significance for the theory of computability.

Keywords: Ackermann; Bernays; Canonical system; Church; Computor; Correspondence decision problem; Davis; Dedekind; Dershowitz; Gandy; Gödel; Gurevich; Herbrand; Hilbert; Kleene; Kolmogorov; Mechanical procedure; Normal system; Post; Principia mathematica; Production; Recursive functions; Representation theorem; Sieg; Skolem; Tag; Thue; Turing; Turing’s central thesis; Unsolvability; Uspenski; Word problem (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-22156-4_1

Ordering information: This item can be ordered from
http://www.springer.com/9783319221564

DOI: 10.1007/978-3-319-22156-4_1

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().