A consequence of the notional existence of an effectively calculable yet non-recursive function
DOI:
https://doi.org/10.15633/acr.5306Abstract
The present paper is devoted to a discussion of the role of Church’s thesis in setting limits to the cognitive possibilities of mathematics. The specific aim is to analyse the formalized theory of arithmetic as a fundamental mathematical structure related to the theory of computation. By introducing notional non-standard computational abilities into this theory, a non-trivial enlargement of the set of theorems is obtained. The paper also indicates the connection between the inclusion of new functions through the development of axioms and the potential modification of inference rules. In addition, the paper provides an explanation of the role of inclusion of a certain interpretation of the meaning of the axioms of the theory in that theory.
References
Adams, Rod. 2011. An Early History of Recursive Functions and Computability. Docent Press.
Boolos, George S. 1995. The Logic of Provability. Cambridge University Press.
Copeland, B. Jack. 2020. “The Church-Turing Thesis.” In The Stanford Encyclopedia of Philosophy, edited by Edward N. Zalta, Summer 2020. https://plato.stanford.edu/ archives/sum2020/entries/church-turing/; Metaphysics Research Lab, Stanford University.
Gödel, Kurt. 1930. “Die Vollständigkeit Der Axiome Des Logischen Funktionen- kalküls.” Monatshefte Für Mathematik Und Physik 37 (1): 349–60. https://doi. org/10.1007/BF01696781.
Hilbert, David, and Paul Bernays. 1934. Grundlagen Der Mathematik. Vol. I. Berlin: Springer.
Kleene, Stephen Cole. 1952. Introduction to Metamathematics. Princeton: van Nostrand Company.
Kolmogorov, Andrey N., and Vladimir A. Uspenskii. 1958. “On the Definition of an Algorithm.” Uspekhi Matematicheskikh Nauk 13 (4(82)): 3–28.
Maligranda, Lech, and Prytula, Jaroslaw G. 2013. Lwowscy uczeni wymienieni w przesłuchaniach Banacha z 1944 roku. Wiadomości Matematyczne, 49: 29–66.
Odifreddi, Piergiorgio. 1989. Classical Recursion Theory. Vol. 1. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland Publishing Company.
Olszewski, Adam. 2009. Teza Churcha. Kontekst HistorycznoFilozoficzny. Kraków: Universitas.
Olszewski, Adam, Jan Woleński, and Robert Janusz. 2006. Church’s Thesis After 70 Years. Ontos Verlag.
Peano, Giuseppe. 1889. Arithmetices Principia: Nova Methodo. Torino: Fratres Bocca.
Rescher, Nicholas. 2022. “Reductio ad Absurdum.” In Internet Encyclopedia of Philosophy, edited by Bradley Dowden James Fieser, 12.03.2022 ed. https://iep.utm.edu/ reductio/; Internet Encyclopedia of Philosophy.
Rogers, Hartley. 1987. Theory of Recursive Functions and Effective Computability. Vol. 36. Cambridge: MIT Press.
Sieg, Wilfried. 1997. “Step by Recursive Step: Church’s Analysis of Effective Calcula- bility.” The Bulletin of Symbolic Logic 3 (2): 154–80. https://doi.org/10.2307/421012. Smith, Peter. 2007. An Introduction to Gödel’s Theorems. Cambridge Introductions to Philosophy. Cambridge: Cambridge University Press. https://doi.org/10.1017/CBO9780511800962.
Turing, Alan M. 1937. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society s2-42 (1): 230–65. https://doi.org/10.1112/plms/s2-42.1.230.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Adam Olszewski
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and full publishing rights without restrictions, and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution 4.0 International License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
