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

Autor

DOI:

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

Abstrakt

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.

Bibliografia

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.

Pobrania

Opublikowane

2021-12-31

Numer

Tom 53 (2021)

Dział

Filozofia

Licencja

Prawa autorskie (c) 2022 Adam Olszewski

Creative Commons License

Utwór dostępny jest na licencji Creative Commons Uznanie autorstwa 4.0 Międzynarodowe.

Twórca oświadcza, że przysługują mu prawa autorskie do utworu i że nie są ograniczone w zakresie objętym niniejszym oświadczeniem oraz że utwór jest dziełem oryginalnym i nie narusza praw autorskich innych osób.

Twórca zezwala Uniwersytetowi Papieskiemu Jana Pawła II w Krakowie na nieodpłatne, niewyłączne i nieograniczone w czasie korzystanie z utworu, to jest:

  • utrwalanie i zwielokrotnianie: wytwarzanie egzemplarzy utworu techniką drukarską, reprograficzną, zapisu magnetycznego oraz techniką cyfrową;
  • obrotu oryginałem albo egzemplarzami, na których utwór utrwalono (wprowadzanie do obrotu, użyczenie lub najem oryginału albo egzemplarzy, publiczne wystawienie, wyświetlenie, a także publiczne udostępnianie utworu w taki sposób, aby każdy mógł mieć do niego dostęp w miejscu i w czasie przez siebie wybranym);
  • włączenie utworu w skład utworu zbiorowego;
  • udzielanie przez Uniwersytet Papieski Jana Pawła II w Krakowie sublicencji Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0)

Uniwersytet Papieski Jana Pawła II w Krakowie udostępnia utwór na Platformie Czasopism należącej do uczelni, na licencji Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0). Tym samym uprawnia wszystkich zainteresowanych do korzystania z utworu pod następującymi warunkami:

  • zostanie podany autor i tytuł utworu,
  • zostanie podane miejsce publikacji (tytuł czasopisma i identyfikator DOI oryginalnie opublikowanego utworu).