Uncomputable Numbers and the Limits of Coding in Computer Science

Abstrakt

DOI: http://doi.org/10.26333/stsen.xxx.06

The description of data and computer programs with the use of numbers is epistemologically valuable, because it allows the definition of the limits of different types of computations. This applies in particular to discrete (digital) computations, which can be described by means of computable numbers in the Turing sense. The mathematical fact that there are other types of real numbers, i.e. uncomputable numbers, determines the minimal limitations of digital techniques; on the other hand, however, it points to the possibility of theoretical development and physical implementation of computationally stronger techniques, such as analogue-continuous computations. Analyses presented in this article lead to the conclusion that physical implementations of unconventional (non-digital) computations require the occurrence of actually infinite entities in nature. Although some arguments of theoretical physics support the physical existence of such entities, they are not definitive.

PDF (English)

Bibliografia

Angius, N., Turner, R. (2017). Philosophy of Computer Science. Stanford Encyclopedia of Philosophy. Retrieved from: https://plato.stanford.edu/entries/computer-science/

Chaitin, G. J. (1993). Randomness in Arithmetic and the Decline and Fall of Reductionism in Pure Mathematics. Bulletin of the European Association for Theoretical Computer Science, 50, 314–328.

Chaitin, G. J. (1998). The Limits of Mathematics. Singapore: Springer.

Chaitin, G. J. (2005). Omega and Why Maths Has No TOEs. Retrieved from: https://plus.maths.org/content/os/issue37/features/omega

Colburn, T. R. (2000). Philosophy and Computer Science. Armonk, NY: M.E. Sharpe.

Copeland, J. (2002). Hypercomputation. Mind and Machines, 12(4), 461–502.

Deutsch, D. (1985). Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of The Royal Society of London A, 400, 97–117.

Etesi, G., Nemeti, I. (2002). Non-Turing Computations via Malament-Hogarth Space-Times. International Journal of Theoretic Physics, 41(2), 341–370.

Gödel, K. (1995/2018). O pewnych zasadniczych twierdzeniach dotyczących podstaw matematyki i wnioskach z nich płynących. Studia Semiotyczne, 32(2), 9–32.

Harel, D. (2000). Rzecz o istocie informatyki. Algorytmika. Warsaw: Wydawnictwa Naukowo-Techniczne.

Kari, L., Rozenberg, G. (2008). The Many Facets of Natural Computing, Communications of the ACM, 51(10), 72–83.

Krajewski, S. (2014). Neopitagoreizm współczesny: uwagi o żywotności pitagoreizmu. In: M. Heller, S. Krajewski (Eds.), Czy fizyka i matematyka to nauki humanistyczne? (pp. 348–366). Kraków: Copernicus Center Press.

Leibniz, G. W. (1890). Philosophische Schriften (Vol. VII). Berlin: Weidmann.

Marciszewski, W. (2012). Amor Infiniti. Jakie doń prowadzą intuicje filozoficzne? Retrieved from: http://marciszewski.eu/?p=2955

Marciszewski, W., Stacewicz, P. (2011). Umysł-Komputer-Świat. O zagadce umysłu z informatycznego punktu widzenia. Warsaw: Akademicka Oficyna Wydawnicza EXIT.

Moor, J. H. (1978). Three Myths of Computer Science, The British Journal for the Philosophy of Science, 29(3), 213–222.

Murawski, R. (2014). Nieskończoność w matematyce. Zmagania z potrzebnym, acz kłopotliwym pojęciem. Zagadnienia Filozoficzne w Nauce, 55(2), 5–42.

Mycka, J. M., Piekarz, M. (2004). Przegląd zagadnień obliczalności analogowej. In: S. Grzegórski, M. Miłosz, P. Muryjas (Eds.), Algorytmy, metody i programy naukowe (pp. 125–132). Lublin: Polskie Towarzystwo Informatyczne.

Mycka, J. M., Olszewski A. (2015). Czy teza Churcha ma jeszcze jakieś znaczenie dla informatyki? In: P. Stacewicz (Ed.), Informatyka a filozofia. Od informatyki i jej zastosowań do światopoglądu informatycznego (pp. 53–74). Warsaw: Oficyna Wydawnicza Politechniki Warszawskiej.

Ord, T. (2002). Hypercomputation: Computing More Than the Turing Machine. Retrieved from: https://arxiv.org/ftp/math/papers/0209/0209332.pdf

Ord, T. (2006). The many forms of hypercomputation. Applied Mathematics and Computation, 178(1), 8–24.

Pour-El, M. B., Richards, J. I. (1989). Computability in Analysis and Physics. Berlin: Springer.

Rozenberg, G., Back, T., Kok, J. N. (2012). Handbook of Natural Computing. Berlin-Heidelberg: Springer.

Rubel, L. (1993). The Extended Analog Computer. Advances in Applied Mathematics, 14(1), 39–50.

Shagrir, O. (2004). Super-Tasks, Accelerating Turing Machines and Uncomputability. Theoretical Computer Science, 317(1–3), 105–114.

Shannon, C. (1941). Mathematical Theory of the Differential Analyzer. Journal of Mathematics and Physics. 20(1–4), 337–354.

Stacewicz, P. (2012). Co łączy umysł z teorią liczb? Filozofia Nauki, 79(3), 111–126.

Stacewicz. P. (2015). Informatyczne kłopoty z nieskończonością. In: R. Murawski (Ed.), Filozofia matematyki i informatyki (pp. 310–327). Kraków: Copernicus Center Press.

Stacewicz, P. (2018a). Czy informatykom musi wystarczyć nieskończoność potencjalna? In: R. Murawski, J. Woleński (Eds.), Problemy filozofii matematyki i informatyki (pp. 177–190). Poznań: Wydawnictwo Naukowe Uniwersytetu im. Adama Mickiewicza w Poznaniu.

Stacewicz, P. (2018b). O teoretycznej (nie)zbędności kategorii liczby w informatyce i jej metodologii. Retrieved from: http://marciszewski.eu/?p=999

Stannett, M. (2003). Computation and Hypercomputation. Minds and Machines, 13(1), 115–153.

Trzęsicki, K. (2006). From the Idea of Decidability to the Number Omega. Studies in Logic, Grammar and Rhetoric, 22(1), 73–142.

Trzęsicki, K. (2006). Leibnizjańskie inspiracje informatyki. Filozofia Nauki, 55(3), 21–48.

Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2– 42(1), 230–265.