A consequence of the notional existence of an effectively calculable yet non-recursive function

Authors

DOI:

https://doi.org/10.15633/acr.5306

Abstract

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 Historyczno­Filozoficzny. 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

2021-12-31

Issue

Vol. 53 (2021)

Section

Filozofia

License

Copyright (c) 2022 Adam Olszewski

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The author declares that he owns the copyright to the work (article) and that it is not limited in the scope covered by the above declaration and that the work (article) is an original work and does not infringe the copyright of other persons.

The author allows the Pontifical University of John Paul II in Krakow to use the paper free of charge, non-exclusive and unlimited in time by, i.e.:

– keeping in records and reproduction of the copies of the work using printing, reprography, magnetic recording and digital technology;


– trade in the original or copies on which the work has been recorded (introduction to the market, lending or rental of the original or copies, public exhibition, display, as well as making the work available to the public in such a way that everyone can have access to it in a place and at a time chosen by them);


– inclusion of the work in a collective work;

– granting by the Pontifical University of John Paul II in Krakow a Creative Commons Sub-licence Authorship Recognition-Non-commercial Use-No Subsidiaries 3.0 Poland
The Pontifical University of John Paul II in Krakow makes the work available on the Magazine Platform of the university under the Creative Commons Attribution-Non-commercial Use-No Subsidiary Works 3.0 Poland license.

Thus, it entitles all interested parties to use the work under the following conditions:

  • the author and the title of the work will be given, 
  • the place of publication (journal title and internet address of the originally published work) will be indicated, 
  • the work will be distributed in a non-commercial manner, 
  • no dependent works will be created.