Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T03:15:07.793Z Has data issue: false hasContentIssue false
  • English
  • Français

Closing the Circle: An Analysis of Emil Post's Early Work

Published online by Cambridge University Press:  15 January 2014

Liesbeth de Mol
Liesbeth de Mol*
Affiliation:
Centre for Logic and Philosophy of Science, Blandijnberg 2, 9000 Gent, BelgiumE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In 1931 Kurt Gödel published his incompleteness results, and some years later Church and Turing showed that the decision problem for certain systems of symbolic logic has a negative solution. However, already in 1921 the young logician Emil Post worked on similar problems which resulted in what he called an “anticipation” of these results. For several reasons though he did not submit these results to a journal until 1941. This failure ‘to be the first’, did not discourage him: his contributions to mathematical logic and its foundations should not be underestimated. It is the purpose of this article to show that an interest in the early work of Emil Post should be motivated not only by this historical fact, but also by the fact that Post's approach and method differs substantially from those offered by Gödel, Turing and Church. In this paper it will be shown how this method evolved in his early work and how it finally led him to his results.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 2 , June 2006 , pp. 267 - 289
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Chomsky, Noam, On certain formal properties of grammars, Information and Control, vol. 2 (1959), pp. 137–167.Google Scholar
[2] Church, Alonzo, An unsolvable problem of elementary number theory, American Journal of Mathematics, vol. 58 (1936), pp. 345–363.Google Scholar
[3] Church, Alonzo, The calculi of lambda-conversion, Annals of Mathematics Studies, vol. 6, Princeton University Press, 1941.Google Scholar
[4] Davis, Martin (editor), The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Raven Press, New York, 1965, Corrected republication (2004), Dover publications, New York.Google Scholar
[5] Davis, Martin (editor), Why Gödel didn't have Church's thesis, Information and Control, vol. 54 (1982), pp. 3–24.Google Scholar
[6] Davis, Martin (editor), Influences of mathematical logic on computer science, in [10], 1988, pp. 315–326.CrossRefGoogle Scholar
[7] Davis, Martin (editor), Emil L. Post. His life and work, Solvability, provability, definability: The collected works of Emil L. Post, [25], Birkhäuser, 1994, pp. xi–xviii.Google Scholar
[8] Davis, Martin (editor), Logic in the twenties, this Bulletin, vol. 1 (1995), no. 3, pp. 273–278.Google Scholar
[9] Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.Google Scholar
[10] Herken, Rolf (editor), The Universal Turing machine, Oxford University Press, Oxford, 1988, Republication (1994), Springer Verlag, New York.Google Scholar
[11] Lucas, J. R., Minds, machines and Gödel, Philosophy, vol. 36 (1961), pp. 112–127.Google Scholar
[12] Minsky, Marvin, Recursive unsolvability of Post's problem of tag and other topics in the theory of Turing machines, Annals of Mathematics, vol. 74 (1961), pp. 437–455.Google Scholar
[13] Murawski, Roman, E. L. Post and the development of mathematical logic and recursion theory, Studies in Logic, Grammar and Rhetoric, vol. 2 (1998), no. 15, pp. 17–30.Google Scholar
[14] Penrose, Roger, Shadows of the mind. A search for the missing science of consciousness., Oxford University Press, Oxford, 1994.Google Scholar
[15] Post, Emil Leon, Introduction to a general theory of elementary propositions, American Journal of Mathematics, vol. 43 (1921), pp. 163–185.Google Scholar
[16] Post, Emil Leon, Finite combinatory processes—Formulation 1, The Journal of Symbolic Logic, vol. 1 (1936), no. 3, pp. 103–105.Google Scholar
[17] Post, Emil Leon, Polyadic groups, Transactions of the American mathematical society, vol. 48 (1940), pp. 208–350.Google Scholar
[18] Post, Emil Leon, Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, vol. 65 (1943), pp. 197–215.Google Scholar
[19] Post, Emil Leon, Recursively enumerable sets of positive integers and their decision problems, Bulletin of The American Mathematical Society, vol. 50 (1944), pp. 284–316.Google Scholar
[20] Post, Emil Leon, A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, vol. 52 (1946), pp. 264–268.Google Scholar
[21] Post, Emil Leon, Recursive unsolvability of a problem of Thue, The Journal of Symbolic Logic, vol. 12 (1947), pp. 1–11.Google Scholar
[22] Post, Emil Leon, A necessary condition for definability for transfinite von neumann-gĺodel set theory sets, with an application to the problem of the existence of a definable well-ordering of the continuum, Bulletin of the American Mathematical Society, vol. 59 (1953), p. 246.Google Scholar
[23] Post, Emil Leon, Solvability, definability, provability; history of an error, Bulletin of the American Mathematical Society, vol. 59 (1953), pp. 245–246.Google Scholar
[24] Post, Emil Leon, Absolutely unsolvable problems and relatively undecidable propositions — account of an anticipation, in [4], 1965, pp. 340–433.Google Scholar
[25] Post, Emil Leon, Solvability, provability, definability: The collected works of Emil L. Post, Birkhäuser, Boston, 1994, edited by Martin Davis.Google Scholar
[26] Sadowski, Zenon, On the development of Emil Post's ideas in structural complexity theory, Studies in Logic, Grammar and Rhetoric, vol. 2 (1998), no. 15, pp. 55–59.Google Scholar
[27] Stillwell, John, Emil Post and his anticipation of Gödel and Turing, Mathematics Magazine, vol. 77 (2004), no. 1, pp. 3–14.Google Scholar
[28] Turing, Alan, On computable numbers with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230–265.Google Scholar