Skip to main content
Top
Published in:
Cover of the book

2015 | OriginalPaper | Chapter

Conceptual Confluence in 1936: Post and Turing

Authors : Martin Davis, Wilfried Sieg

Published in: Turing’s Revolution

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
The broader history of computability has been described in a number of publications, partly by the participants in the early development in Princeton, for example, [43, 57]. Good discussions are found in, among others [9, 14, 26, 58, 62, 68].
There are many excellent books on recursion/computability theory, but not many that take Post’s approach as fundamental. We just mention [13, 47, 56, 67].
 
2
Machines that are deterministic are Turing’s a-machines; if a-machines operate only on 0s and 1s they are called computing machines; see [71], p. 232.
 
3
There are other commonalities in their approaches, e.g., in connection with relative computability, which first appeared in Turing’s dissertation and which played such a key role in Post’s later work. However, here we are focusing on their fundamental conceptual analysis.
 
4
In the same year, Church established the unsolvability of the Entscheidungsproblem—having identified \(\lambda\)-definability and general recursiveness with effective calculability; [6, 7].
 
5
In the early evolution of recursion theory, Gödel’s definition was viewed as being a modification of a proposal of Herbrand’s—because Gödel presented it that way in his Princeton Lectures. In a letter to Jean van Heijenoort in 1964, Gödel reasserted that Herbrand had suggested, in a letter, a definition very close to the one actually presented in [28]. However, the connection of Gödel’s definition to Herbrand’s work is much less direct; that is clear from the two letters that were exchanged between Gödel and Herbrand in 1931. John Dawson found the letters in the Gödel Nachlass in 1986; see [17]. The letters are published in [36]; their intellectual context is discussed in [61].
 
6
How far removed the considerations of Turing (and Post) were from those of Bernays, who actually wrote Supplement II of Hilbert and Bernays [39], should be clear from two facts: (i) In a letter to Church of 22 April 1937, Bernays judged Turing as “very talented” and his concept of computability as “very suggestive”; (ii) Bernays did not mention Turing’s paper in Supplement II, though he knew Turing’s work very well. Indeed, in his letter to Church Bernays pointed out a few errors in [71]; Church communicated the errors to Turing and, in a letter of 22 May 1937 to Bernays, Turing acknowledged them and suggested that he would write a Correction, [72]!
 
7
In a very informative letter Church wrote on 8 June 1937 to the Polish logician Pepis, the absoluteness of general recursive functions is indirectly argued for. (Church’s letter and its analysis is found in [59].) Gödel’s claim, with “formality” sharpened in the way we indicated, is an almost immediate consequence of the considerations in Supplement II of Hilbert and Bernays [39].
 
8
Gödel argues at the bottom of p. 166 that the expressions and finite classes of expressions can be mapped to integers (“Gödel numbering”). Thus, he asserts, a “procedure in the sense we want is nothing else but a function f(x1, , xr) whose arguments as well as its values are integers and which is such that for any system of integers n1, , nr the value can actually be calculated”. So a “satisfactory definition of calculable functions” is needed, and that’s what the definition of computable function yields for Gödel.
 
9
In [10], p. 10 and [69], p. 214, Gödel’s remark “That this really is the correct definition of mechanical [our emphasis] computability was established beyond any doubt by Turing.” is taken as showing that computability of functions is defined here by reference to Turing machines, i.e., that Gödel at this point had taken already Turing’s perspective. That view can be sustained only, if the context we sketched is left completely out of consideration.
 
10
As to Post’s biography, see [15].
The mathematical and philosophical part of Post’s contributions is discussed with great clarity in [26], pp. 92–98. The unity of their approaches is, however, not recognized; it is symptomatic that neither [75] nor the overlapping work in [54, 74] is even mentioned.
A very comprehensive and illuminating account of Post’s work is found in [79].
 
11
His work was published belatedly and only partially in [3]. In addition to the completeness question, Bernays also investigated the independence of the axioms of PM. He discovered that the associativity of disjunction is actually provable from the remaining axioms (that were then shown to be independent of each other).
 
12
Tag systems may be characterized as normal systems in which for its productions \(gP \Rightarrow P\bar{g}\):
1.
All of the gs are of the same length;
 
2.
the \(\bar{g}\) s corresponding to a given g depend only on its initial symbol;
 
3.
if a given g occurs on the left in one of the productions, then so do all other strings of the same length having the same initial symbol as that g.
 
Post discusses Tag in the introductory section of Post [51] and in Sect. 3 of Post [50].
 
13
Davis [15], DeMol [20], DeMol [21], and Post [50].
 
14
Post [50]: p. 408 in [12]; p. 387 in [16]; p. 422 in [55].
 
15
Gödel [36] pp. 169, 171.
The notes that were exchanged between Gödel and Post are in this volume of Gödel’s Collected Works.
 
16
We neglect in our discussion “states of mind” of the computor. Here is the reason why. Turing argues in Sect. 9.I that the number of these states is bounded, and Post calls this Turing’s “finite number of mental states” assumption. However, in Sect. 9,III Turing argues that the computor’s state of mind [“mental state”] can be replaced in favor of “a more physical and definite counterpart of it”. In a sense then, the essential components of a computation have been fully externalized; see [13], p. 6, how this is accomplished through the concept of an “instantaneous description”.
 
17
In footnote 8, p. 105 of Post [49], he criticizes masking the identification of recursiveness and effective calculability under a definition as Church had done. This, Post continues, “hides the fact that a fundamental discovery in the limitations of the mathematizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.”
 
18
Post pointed this out in a number of different places: (1) Urquhart on p. 643 of Urquhart [79] quotes from Post’s 1938 notebook and discusses, with great sensitivity, “an internal reason for Post’s failure to stake his claim to the incompleteness and undecidability results in time” on pp. 630–633; (2) in [50], p. 377, Post refers to the last paragraph of [49] and writes: “However, should Turing’s finite number of mental states hypothesis... bear under adverse criticism, and an equally persuasive analysis be found for all humanly possible modes of symbolization, then the writer’s position, while still tenable in an absolute sense, would become largely academic.”
 
19
This problem later turned out to be a useful tool for obtaining unsolvability theorems regarding Noam Chomsky’s hierarchy of formal languages, which by the way, was itself based quite explicitly on Post production systems. See also the extended discussion of the correspondence problem in [79], p. 648.
 
20
It is interesting that Markov’s proof [46] of the unsolvability of Thue’s problem, which was quite independent of Post’s, did use normal systems.
 
21
Of course this is to be understood in relation to the Church-Turing Thesis.
 
22
In the formulation of Turing [71], the tape is infinite in only one direction and a machine’s operations are specified by quintuples allowing for a change of symbol together with a motion to the left or right as a single step. Of course this difference is not significant.
 
23
Post works with the closely related unsolvability of the problem of whether a particular distinguished symbol will ever appear on the tape, because unlike the halting problem, it appears explicitly in [71]. But dissatisfied with the rigor of Turing’s treatment, Post outlines his own proof of that fact. He also includes a careful critique pointing out how a convention that Turing had adopted for convenience in constructing examples had been permitted to undermine some of the key proofs. Anyhow, for the present application to Thue’s problem, Post begins by deleting all quadruples for which the distinguished symbol is the third symbol of the four, thus changing the unsolvability to one of halting.
 
24
Turing’s proof was published in the prestigious Annals of Mathematics. Eight years later an analysis and critique of Turing’s paper [4] was published in the same journal. Boone found the proof to be essentially correct, but needing corrections and expansions in a number of the details.
 
25
Gandy, in [25], uses particular discrete dynamical systems to analyze “machines”, i.e., discrete mechanical devices, and “proves” a mechanical thesis (M) corresponding to Turing’s thesis. Dershowitz and Gurevich in [22] give an axiomatization and claim to prove Church’s Thesis. (For a discussion of this claim, see [63].) In the context of our discussion here, one can say that Gandy and Dershowitz & Gurevich introduce very general models of computations—“Gandy Machines” in Gandy’s case, “Abstract State Machines” in Dershowitz and Gurevich’s case—and reduce them to Turing machine computations.
 
26
A cut in O (determined by x) is a partition of O into two non-empty parts O1 and O2, such that all the elements of O1 stand in the relation R to all the elements of O2 (and x is taken to be in O1).
 
Literature
1.
go back to reference P. Bernays, Beiträge zur axiomatischen Behandlung des Logik-Kalküls; Habilitationsschrift. Presented to the Georg-August-Universität zu Göttingen on 9 July 1918 [Reprinted [24], pp. 222–268] P. Bernays, Beiträge zur axiomatischen Behandlung des Logik-Kalküls; Habilitationsschrift. Presented to the Georg-August-Universität zu Göttingen on 9 July 1918 [Reprinted [24], pp. 222–268]
2.
go back to reference P. Bernays, Logical Calculus. Lecture Notes at the Institute for Advanced Study (1935/1936) [Notes by P. Bernays, with the assistance of F.A. Ficken; Princeton 1936. The notes can be found in the Bernays Nachlass of the ETH Zürich, HS973:6] P. Bernays, Logical Calculus. Lecture Notes at the Institute for Advanced Study (1935/1936) [Notes by P. Bernays, with the assistance of F.A. Ficken; Princeton 1936. The notes can be found in the Bernays Nachlass of the ETH Zürich, HS973:6]
3.
go back to reference P. Bernays, Axiomatische Untersuchung des Aussagen-Kalküls der Principia Mathematica. Math. Z. 25, 305–320 P. Bernays, Axiomatische Untersuchung des Aussagen-Kalküls der Principia Mathematica. Math. Z. 25, 305–320
4.
go back to reference W.W. Boone, An analysis of Turing’s ‘The word problem in semi-groups with cancellation’. Ann. Math. 67, 195–202 [Reprinted [76], pp. 175–182] W.W. Boone, An analysis of Turing’s ‘The word problem in semi-groups with cancellation’. Ann. Math. 67, 195–202 [Reprinted [76], pp. 175–182]
5.
go back to reference A. Church, An unsolvable problem of elementary number theory (abstract). Bull. Am. Math Soc. 41, 333 A. Church, An unsolvable problem of elementary number theory (abstract). Bull. Am. Math Soc. 41, 333
6.
go back to reference A. Church, An unsolvable problem of elementary number theory. Am. J. Math. 58, 345–363 [Reprinted [12, 16], pp. 89–107] A. Church, An unsolvable problem of elementary number theory. Am. J. Math. 58, 345–363 [Reprinted [12, 16], pp. 89–107]
7.
go back to reference A. Church, A note on the Entscheidungsproblem. J. Symb. Log. 1, 40–41 [Correction, vol. 1, pp. 101–102. Reprinted with the correction incorporated in the text, [12, 16], pp. 110–115] A. Church, A note on the Entscheidungsproblem. J. Symb. Log. 1, 40–41 [Correction, vol. 1, pp. 101–102. Reprinted with the correction incorporated in the text, [12, 16], pp. 110–115]
8.
go back to reference B. Cooper, J. van Leeuwen (eds.), Alan Turing: His Work and Impact (Elsevier, Amsterdam, 2013)MATH B. Cooper, J. van Leeuwen (eds.), Alan Turing: His Work and Impact (Elsevier, Amsterdam, 2013)MATH
9.
go back to reference J. Copeland (ed.), The Essential Turing (Clarendon Press, Oxford, 2004)MATH J. Copeland (ed.), The Essential Turing (Clarendon Press, Oxford, 2004)MATH
10.
go back to reference J. Copeland, O. Shagrir, Turing versus Gödel on computability and the mind, in [11], pp. 1–33 J. Copeland, O. Shagrir, Turing versus Gödel on computability and the mind, in [11], pp. 1–33
11.
go back to reference J. Copeland, C. Posy, O. Shagrir (eds.), Computability: Turing, Gödel, Church and Beyond (MIT Press, Cambridge) J. Copeland, C. Posy, O. Shagrir (eds.), Computability: Turing, Gödel, Church and Beyond (MIT Press, Cambridge)
12.
go back to reference M.D. Davis (ed.), The Undecidable (Raven Press, Hewlett, 1965) M.D. Davis (ed.), The Undecidable (Raven Press, Hewlett, 1965)
13.
go back to reference M.D. Davis, Computability and Unsolvability (McGraw-Hill) [Reprinted with an additional appendix, Dover 1983] M.D. Davis, Computability and Unsolvability (McGraw-Hill) [Reprinted with an additional appendix, Dover 1983]
14.
go back to reference M.D. Davis, Why Gödel didn’t have Church’s thesis. Inf. Control 54, 3–24 M.D. Davis, Why Gödel didn’t have Church’s thesis. Inf. Control 54, 3–24
15.
go back to reference M.D. Davis, Emil L. Post: His Life and Work, [55], pp. xi-xxviii M.D. Davis, Emil L. Post: His Life and Work, [55], pp. xi-xxviii
16.
17.
go back to reference J. Dawson, Prelude to recursion theory: the Gödel-Herbrand correspondence, in First International Symposium on Gödel’s Theorems, ed. by Z.W. Wolkowski (World Scientific Publishing Co.) pp. 1–13 J. Dawson, Prelude to recursion theory: the Gödel-Herbrand correspondence, in First International Symposium on Gödel’s Theorems, ed. by Z.W. Wolkowski (World Scientific Publishing Co.) pp. 1–13
18.
go back to reference R. Dedekind, Stetigkeit und irrationale Zahlen (Vieweg) [Translated in [23] pp. 765–779] R. Dedekind, Stetigkeit und irrationale Zahlen (Vieweg) [Translated in [23] pp. 765–779]
19.
go back to reference R. Dedekind, Was sind und was sollen die Zahlen? (Vieweg) [Translated in [23] pp. 787–833] R. Dedekind, Was sind und was sollen die Zahlen? (Vieweg) [Translated in [23] pp. 787–833]
20.
go back to reference L. DeMol, Closing the circle. An analysis of Emil Post’s early work. Bull. Symb. Log. 12, 267–289 L. DeMol, Closing the circle. An analysis of Emil Post’s early work. Bull. Symb. Log. 12, 267–289
21.
go back to reference L. DeMol, Generating, solving and the mathematics of Homo Sapiens. Emil Post’s views on computation, in A Computable Universe: Understanding and Exploring Nature as Computation, ed. by H. Zenil, World Scientific Publishing, Singapore, 2013, pp. 45–62 L. DeMol, Generating, solving and the mathematics of Homo Sapiens. Emil Post’s views on computation, in A Computable Universe: Understanding and Exploring Nature as Computation, ed. by H. Zenil, World Scientific Publishing, Singapore, 2013, pp. 45–62
22.
go back to reference N. Dershowitz, Y. Gurevich, A natural axiomatization of computability and proof of Church’s thesis. Bull. Symb. Log. 14, 299–350 N. Dershowitz, Y. Gurevich, A natural axiomatization of computability and proof of Church’s thesis. Bull. Symb. Log. 14, 299–350
23.
go back to reference W.B. Ewald (ed.), From Kant to Hilbert: A Source Book in the Foundations of Mathematics, vol. II (Oxford University Press, Oxford) W.B. Ewald (ed.), From Kant to Hilbert: A Source Book in the Foundations of Mathematics, vol. II (Oxford University Press, Oxford)
24.
go back to reference W.B. Ewald, W. Sieg (eds.), David Hilbert’s Lectures on the Foundations of Arithmetic and Logic, 1917–1933 (Springer, Berlin) W.B. Ewald, W. Sieg (eds.), David Hilbert’s Lectures on the Foundations of Arithmetic and Logic, 1917–1933 (Springer, Berlin)
25.
go back to reference R. Gandy, Church’s thesis and principles for mechanisms, in The Kleene Symposium, ed. by J. Barwise, H.J. Keisler, K. Kunen (North-Holland Publishing Company, Amsterdam), pp. 123–148 R. Gandy, Church’s thesis and principles for mechanisms, in The Kleene Symposium, ed. by J. Barwise, H.J. Keisler, K. Kunen (North-Holland Publishing Company, Amsterdam), pp. 123–148
26.
go back to reference R. Gandy, The confluence of ideas in 1936, in The Universal Turing Machine: A Half-Century Survey, ed. by R. Herken (Oxford University Press, Oxford), pp. 55–111 R. Gandy, The confluence of ideas in 1936, in The Universal Turing Machine: A Half-Century Survey, ed. by R. Herken (Oxford University Press, Oxford), pp. 55–111
27.
go back to reference K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38, 173–198. [Reprinted [33] pp. 144–194 (even numbered pages). Translated in: [80] pp. 596–628; [12, 16] pp. 5–38; [33] pp. 145–195 (odd numbered pages)] K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38, 173–198. [Reprinted [33] pp. 144–194 (even numbered pages). Translated in: [80] pp. 596–628; [12, 16] pp. 5–38; [33] pp. 145–195 (odd numbered pages)]
28.
go back to reference K. Gödel, On Undecidable Propositions of Formal Mathematical Systems. Notes on Lectures at the Institute for Advanced Study, Princeton, ed. by S.C. Kleene, J.B. Rosser [Reprinted [12, 16] pp. 41–74; [33] pp. 346–369] K. Gödel, On Undecidable Propositions of Formal Mathematical Systems. Notes on Lectures at the Institute for Advanced Study, Princeton, ed. by S.C. Kleene, J.B. Rosser [Reprinted [12, 16] pp. 41–74; [33] pp. 346–369]
29.
go back to reference K. Gödel, Über die Länge von Beweisen, Ergebnisse eines mathematischen Kolloquiums Heft, vol. 7, pp. 23–24 [Reprinted [33] pp. 396–398 (even numbered pages) Translated in: [12, 16] pp. 82–83; [33] pp. 397–399 (odd numbered pages)] K. Gödel, Über die Länge von Beweisen, Ergebnisse eines mathematischen Kolloquiums Heft, vol. 7, pp. 23–24 [Reprinted [33] pp. 396–398 (even numbered pages) Translated in: [12, 16] pp. 82–83; [33] pp. 397–399 (odd numbered pages)]
30.
go back to reference K. Gödel, Undecidable diophantine propositions, in [35], pp. 164–175 K. Gödel, Undecidable diophantine propositions, in [35], pp. 164–175
31.
go back to reference K. Gödel, Remarks before the Princeton bicentennial conference on problems in mathematics, in [34], pp. 150–153 K. Gödel, Remarks before the Princeton bicentennial conference on problems in mathematics, in [34], pp. 150–153
32.
go back to reference K. Gödel, Postscriptum to [28], in [12, 16], pp. 71–73; [33] pp. 369–371 K. Gödel, Postscriptum to [28], in [12, 16], pp. 71–73; [33] pp. 369–371
33.
go back to reference K. Gödel, Collected Works, vol. I, ed. by S. Feferman et al. (Oxford University Press, Oxford) K. Gödel, Collected Works, vol. I, ed. by S. Feferman et al. (Oxford University Press, Oxford)
34.
go back to reference K. Gödel, Collected Works, vol. II, ed. by S. Feferman et al. (Oxford University Press, Oxford) K. Gödel, Collected Works, vol. II, ed. by S. Feferman et al. (Oxford University Press, Oxford)
35.
go back to reference K. Gödel, Collected Works, vol. III, ed. by S. Feferman et al. (Oxford University Press, Oxford) K. Gödel, Collected Works, vol. III, ed. by S. Feferman et al. (Oxford University Press, Oxford)
36.
go back to reference K. Gödel, Collected Works, vol. V, ed. by S. Feferman et al. (Oxford University Press, Oxford) K. Gödel, Collected Works, vol. V, ed. by S. Feferman et al. (Oxford University Press, Oxford)
37.
go back to reference J. Herbrand, Sur la non-contradiction de l’arithmétique. Crelles Journal für die reine und angewandte Mathematik 166, 1–8 [Translated in [80], pp. 618–628] J. Herbrand, Sur la non-contradiction de l’arithmétique. Crelles Journal für die reine und angewandte Mathematik 166, 1–8 [Translated in [80], pp. 618–628]
38.
go back to reference D. Hilbert, Grundlagen der Geometrie, in Festschrift zur Feier der Enthüllung des Gauss-Weber-Denkmals in Göttingen (Teubner, Leipzig), pp. 1–92 D. Hilbert, Grundlagen der Geometrie, in Festschrift zur Feier der Enthüllung des Gauss-Weber-Denkmals in Göttingen (Teubner, Leipzig), pp. 1–92
39.
go back to reference D. Hilbert, P. Bernays, Grundlagen der Mathematik, vol. II (Springer, Berlin) D. Hilbert, P. Bernays, Grundlagen der Mathematik, vol. II (Springer, Berlin)
40.
go back to reference S.C. Kleene, General recursive functions of natural numbers. Mathematische Annalen 112, 727–742 [Reprinted [12, 16], pp. 236–253] S.C. Kleene, General recursive functions of natural numbers. Mathematische Annalen 112, 727–742 [Reprinted [12, 16], pp. 236–253]
41.
go back to reference S.C. Kleene, Recursive predicates and quantifiers. Trans. Am. Math. Soc. 53, 41–73 S.C. Kleene, Recursive predicates and quantifiers. Trans. Am. Math. Soc. 53, 41–73
42.
go back to reference S.C. Kleene, Introduction to Metamathematics (Wolters-Noordhoff Publishing, Amsterdam) S.C. Kleene, Introduction to Metamathematics (Wolters-Noordhoff Publishing, Amsterdam)
43.
go back to reference S.C. Kleene, Origins of recursive function theory. Ann. Hist. Comput. 3, 52–67 S.C. Kleene, Origins of recursive function theory. Ann. Hist. Comput. 3, 52–67
44.
go back to reference A. Kolmogorov, V. Uspensky, On the definition of an algorithm. AMS Transl. 21(2), 217–245 A. Kolmogorov, V. Uspensky, On the definition of an algorithm. AMS Transl. 21(2), 217–245
45.
go back to reference C.I. Lewis, A Survey of Symbolic Logic (University of California Press, Berkeley) C.I. Lewis, A Survey of Symbolic Logic (University of California Press, Berkeley)
46.
go back to reference A.A. Markov, On the impossibility of certain algorithms in the theory of associative systems. Doklady Akademii Nauk S.S.S.R., n.s., 1951, 77, 19–20 (Russian); C. R.. Acad. Sci. de l’U.R.S.S., n.s., 55, 583–586 (English translation) A.A. Markov, On the impossibility of certain algorithms in the theory of associative systems. Doklady Akademii Nauk S.S.S.R., n.s., 1951, 77, 19–20 (Russian); C. R.. Acad. Sci. de l’U.R.S.S., n.s., 55, 583–586 (English translation)
47.
go back to reference P. Martin-Löf, Notes on Constructive Mathematics (Almqvist & Wiksell, Stockholm) P. Martin-Löf, Notes on Constructive Mathematics (Almqvist & Wiksell, Stockholm)
48.
go back to reference E.L. Post, Introduction to a general theory of elementary propositions. Am. J. Math. 43, 163–165 [Reprinted [80], pp. 265–283. Reprinted [55], pp. 21–43] E.L. Post, Introduction to a general theory of elementary propositions. Am. J. Math. 43, 163–165 [Reprinted [80], pp. 265–283. Reprinted [55], pp. 21–43]
49.
go back to reference E.L. Post, Finite combinatory processes. Formulation I. J. Symb. Log. 1, 103–105 [Reprinted [12, 16], pp. 289–291. Reprinted [55], pp.103–105] E.L. Post, Finite combinatory processes. Formulation I. J. Symb. Log. 1, 103–105 [Reprinted [12, 16], pp. 289–291. Reprinted [55], pp.103–105]
50.
go back to reference E.L. Post, Absolutely unsolvable problems and relatively undecidable propositions: account of an anticipation, in [12], pp. 340–433, [16], pp. 340–406, [55], pp. 375–441 E.L. Post, Absolutely unsolvable problems and relatively undecidable propositions: account of an anticipation, in [12], pp. 340–433, [16], pp. 340–406, [55], pp. 375–441
51.
go back to reference E.L. Post, Formal reductions of the general combinatorial decision problem. Am. J. Math. 65, 197–215 [Reprinted [55], pp. 442–460] E.L. Post, Formal reductions of the general combinatorial decision problem. Am. J. Math. 65, 197–215 [Reprinted [55], pp. 442–460]
52.
go back to reference E.L. Post, Recursively enumerable sets of positive integers and their decision problems. Bull. Am. Math Soc. 50, 284–316 [Reprinted [12, 16], pp.305–337; [55], pp.461–494] E.L. Post, Recursively enumerable sets of positive integers and their decision problems. Bull. Am. Math Soc. 50, 284–316 [Reprinted [12, 16], pp.305–337; [55], pp.461–494]
53.
go back to reference E.L. Post, A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52, 264–268 [Reprinted [55], pp. 495–500] E.L. Post, A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52, 264–268 [Reprinted [55], pp. 495–500]
54.
go back to reference E.L. Post, Recursive unsolvability of a problem of thue. J. Symb. Log. 12, 1–11 [Reprinted [12, 16], pp. 293–303; [55], pp. 503–513] E.L. Post, Recursive unsolvability of a problem of thue. J. Symb. Log. 12, 1–11 [Reprinted [12, 16], pp. 293–303; [55], pp. 503–513]
55.
go back to reference E.L. Post, Solvability, Provability, Definability: The Collected Works of Emil L. Post, ed. by D. Martin (Birkhäuser, Basel) E.L. Post, Solvability, Provability, Definability: The Collected Works of Emil L. Post, ed. by D. Martin (Birkhäuser, Basel)
56.
go back to reference P. Rosenbloom, The Elements of Mathematical Logic (Dover Publications, New York) P. Rosenbloom, The Elements of Mathematical Logic (Dover Publications, New York)
57.
go back to reference J.B. Rosser, Highlights of the history of the Lambda-Calculus. Ann. Hist. Comput. 6(4), 337–349 J.B. Rosser, Highlights of the history of the Lambda-Calculus. Ann. Hist. Comput. 6(4), 337–349
58.
go back to reference W. Sieg, Mechanical procedures and mathematical experience, in Mathematics and Mind, ed. by A. George (Oxford University Press, Oxford), pp. 71–117 W. Sieg, Mechanical procedures and mathematical experience, in Mathematics and Mind, ed. by A. George (Oxford University Press, Oxford), pp. 71–117
59.
go back to reference W. Sieg, Step by recursive step: Church’s analysis of effective calculability. Bull. Symb. Log. 3, 154–180 [Reprinted (with a long Postscriptum) in Turing’s Legacy: Developments from Turing’s Ideas in Logic, ed. by R. Downey. Lecture Notes in Logic (Cambridge University Press), to appear in 2013] W. Sieg, Step by recursive step: Church’s analysis of effective calculability. Bull. Symb. Log. 3, 154–180 [Reprinted (with a long Postscriptum) in Turing’s Legacy: Developments from Turing’s Ideas in Logic, ed. by R. Downey. Lecture Notes in Logic (Cambridge University Press), to appear in 2013]
60.
go back to reference W. Sieg, Calculations by man and machine: mathematical presentation, in In the Scope of Logic, Methodology and Philosophy of Science. Volume one of the 11th International Congress of Logic, Methodology and Philosophy of Science, Cracow, August 1999; P. Gärdenfors, J. Wolenski, K. Kijania-Placek (eds.), Synthese Library, vol. 315 (Kluwer), pp. 247–262 W. Sieg, Calculations by man and machine: mathematical presentation, in In the Scope of Logic, Methodology and Philosophy of Science. Volume one of the 11th International Congress of Logic, Methodology and Philosophy of Science, Cracow, August 1999; P. Gärdenfors, J. Wolenski, K. Kijania-Placek (eds.), Synthese Library, vol. 315 (Kluwer), pp. 247–262
61.
go back to reference W. Sieg, Only two letters: the correspondence between Herbrand and Gödel. Bull. Symb. Log. 11, 172–184 [Reprinted in K. Gödel - Essays for His Centennial, ed. by S. Feferman, C. Parsons, S.G. Simpson. Lecture Notes in Logic (Cambridge University Press, 2010) pp. 61–73] W. Sieg, Only two letters: the correspondence between Herbrand and Gödel. Bull. Symb. Log. 11, 172–184 [Reprinted in K. Gödel - Essays for His Centennial, ed. by S. Feferman, C. Parsons, S.G. Simpson. Lecture Notes in Logic (Cambridge University Press, 2010) pp. 61–73]
62.
go back to reference W. Sieg, On computability, in Philosophy of Mathematics, ed. by A. Irvine (Elsevier, Amsterdam), pp. 535–630 W. Sieg, On computability, in Philosophy of Mathematics, ed. by A. Irvine (Elsevier, Amsterdam), pp. 535–630
63.
go back to reference W. Sieg, Axioms for computability: do they allow a proof of Church’s thesis? in A Computable Universe: Understanding and Exploring Nature as Computation, ed. by H. Zenil, World Scientific Publishing, Singapore, 2013, pp. 99–123 W. Sieg, Axioms for computability: do they allow a proof of Church’s thesis? in A Computable Universe: Understanding and Exploring Nature as Computation, ed. by H. Zenil, World Scientific Publishing, Singapore, 2013, pp. 99–123
64.
go back to reference W. Sieg, Normal forms for puzzles: a variant of Turing’s thesis”, in [8], pp. 332–339 W. Sieg, Normal forms for puzzles: a variant of Turing’s thesis”, in [8], pp. 332–339
65.
go back to reference W. Sieg, J. Byrnes, K-graph machines: generalizing Turing’s machines and arguments, in Gödel ‘96, ed. by P. Hajek. Lecture Notes in Logic, vol. 6 (A.K. Peters, Natick), pp. 98–119 W. Sieg, J. Byrnes, K-graph machines: generalizing Turing’s machines and arguments, in Gödel ‘96, ed. by P. Hajek. Lecture Notes in Logic, vol. 6 (A.K. Peters, Natick), pp. 98–119
66.
go back to reference T. Skolem, Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich. Videnskapsselkapets sktifter, I. Matematisk-naturvidenskabelig klass, no. 6 [Translated in [80] pp. 302–333] T. Skolem, Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich. Videnskapsselkapets sktifter, I. Matematisk-naturvidenskabelig klass, no. 6 [Translated in [80] pp. 302–333]
67.
go back to reference R. Smullyan, Theory of Formal Systems. Annals of Mathematics Studies, vol. 47 (Princeton University Press, Princeton) R. Smullyan, Theory of Formal Systems. Annals of Mathematics Studies, vol. 47 (Princeton University Press, Princeton)
68.
go back to reference R. Soare, Computability and recursion. Bull. Symb. Log. 2(3), 284–321 R. Soare, Computability and recursion. Bull. Symb. Log. 2(3), 284–321
69.
go back to reference R. Soare, Interactive computing and relativized computability, in [11], pp. 203–260 R. Soare, Interactive computing and relativized computability, in [11], pp. 203–260
70.
go back to reference A. Thue, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln. Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-naturvidenskabelig klasse, no. 10 A. Thue, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln. Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-naturvidenskabelig klasse, no. 10
71.
go back to reference A.M. Turing, On computable numbers with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42(2), 230–267 [Reprinted [12, 16] pp. 116–154. Reprinted [78] pp. 18–56. Reprinted [9] pp. 58–90; 94–96. Reprinted [8] pp. 16–43] A.M. Turing, On computable numbers with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42(2), 230–267 [Reprinted [12, 16] pp. 116–154. Reprinted [78] pp. 18–56. Reprinted [9] pp. 58–90; 94–96. Reprinted [8] pp. 16–43]
72.
go back to reference A.M. Turing, Correction to [71]. Proc. Lond. Math. Soc. 43(2), 544–546 A.M. Turing, Correction to [71]. Proc. Lond. Math. Soc. 43(2), 544–546
73.
go back to reference A.M. Turing, Systems of logic based on ordinals. Proc. Lond. Math. Soc. 45(2), 161–228 [Reprinted [12, 16], pp.154–222] A.M. Turing, Systems of logic based on ordinals. Proc. Lond. Math. Soc. 45(2), 161–228 [Reprinted [12, 16], pp.154–222]
74.
go back to reference A.M. Turing, The word problem in semi-groups with cancellation. Ann. Math. 52, 491–505 [Reprinted [77], pp. 63–78. Reprinted [8], pp. 345–357] A.M. Turing, The word problem in semi-groups with cancellation. Ann. Math. 52, 491–505 [Reprinted [77], pp. 63–78. Reprinted [8], pp. 345–357]
75.
go back to reference A.M. Turing, Solvable and unsolvable problems. Sci. News 31, 7–23 [Reprinted [76], pp. 187–203. Reprinted [9], pp. 582–595. Reprinted [8], pp. 322–331] A.M. Turing, Solvable and unsolvable problems. Sci. News 31, 7–23 [Reprinted [76], pp. 187–203. Reprinted [9], pp. 582–595. Reprinted [8], pp. 322–331]
76.
go back to reference A.M. Turing, Mechanical Intelligence: Collected Works of A.M. Turing, ed. by D.C. Ince (North-Holland, Amsterdam) A.M. Turing, Mechanical Intelligence: Collected Works of A.M. Turing, ed. by D.C. Ince (North-Holland, Amsterdam)
77.
go back to reference A.M. Turing, Pure Mathematics: Collected Works of A.M. Turing, ed. by J.L. Britton (North-Holland, Amsterdam) A.M. Turing, Pure Mathematics: Collected Works of A.M. Turing, ed. by J.L. Britton (North-Holland, Amsterdam)
78.
go back to reference A.M. Turing, Mathematical Logic: Collected Works of A.M. Turing, ed. by R.O. Gandy, C.E.M. Yates (North-Holland, Amsterdam) A.M. Turing, Mathematical Logic: Collected Works of A.M. Turing, ed. by R.O. Gandy, C.E.M. Yates (North-Holland, Amsterdam)
79.
go back to reference A. Urquhart, Emil Post, in Handbook of the History of Logic, ed. by D.M. Gabbay, J. Woods. Logic from Russell to Church, vol. 5 (Elsevier, Amsterdam), pp. 617–666 A. Urquhart, Emil Post, in Handbook of the History of Logic, ed. by D.M. Gabbay, J. Woods. Logic from Russell to Church, vol. 5 (Elsevier, Amsterdam), pp. 617–666
80.
go back to reference J. van Heijenoort (ed.), From Frege to Gödel: A Sourcebook in Mathematical Logic, 1879–1931 (Harvard, Cambridge, 1967)MATH J. van Heijenoort (ed.), From Frege to Gödel: A Sourcebook in Mathematical Logic, 1879–1931 (Harvard, Cambridge, 1967)MATH
81.
go back to reference A.N. Whitehead, B. Russell, Principia Mathematica, vol. 1 (Cambridge University Press, Cambridge) A.N. Whitehead, B. Russell, Principia Mathematica, vol. 1 (Cambridge University Press, Cambridge)
Metadata
Title
Conceptual Confluence in 1936: Post and Turing
Authors
Martin Davis
Wilfried Sieg
Copyright Year
2015
Publisher
Springer International Publishing
DOI
https://doi.org/10.1007/978-3-319-22156-4_1

Premium Partner