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

Section

Filozofia