Computadora humana e hipercomputabilidad relativista: una discusión de la Tesis de Turing física

Carlos Villacís

doi:10.5007/1808-1711.2025.e96501

Authors

Carlos Villacís Universidad Complutense de Madrid https://orcid.org/0000-0003-2339-4463

DOI:

https://doi.org/10.5007/1808-1711.2025.e96501

Keywords:

Turing Machine, Human Computer, Physical Turing Thesis, Hypercomputability, Relativistic Hypercomputer

Abstract

The Turing Thesis states that any effectively computable function is Turing-computable or computable by some Turing machine. Analogously, the physical Turing Thesis states that any physically computable function is Turing-computable. This thesis involves a notion of physical computation distinct from the mathematical version of the definition of computation. First, we discuss the distinction based on the condition of the medium-independent vehicle and Turing's idea of the human computer. Secondly, we discuss the physical Turing Thesis based on the thought experiment of Andréka et al. (2018) in which a relativistic hypercomputer can be built operating in the context of a slowly rotating black hole. With this we obtain a counterexample to the physical Turing Thesis since there would be a computer capable of physically computing non-Turing-computable functions.

References

Alonso, E. 2004. Lógica y computabilidad. Summa Logicae en el siglo XXI. http://logicae.usal.es.

Alonso, E. 2006. De la computabilidad a la hipercomputación. Azafea 8: 121-146.

Andréka, H.; Madarász, J.; Németi, I.; Németi, P.; Székely, G. 2018. Relativistic Computation. In: M. Cuffaro; S. Fletcher (ed.), Physical Perspectives on Computation, Computational Perspectives on Physics, p.195-216. Cambridge: Cambridge University Press.

Copeland, B. J. 2002. Accelerating Turing Machines. Minds and Machines 12(2): 281-301.

Copeland, B. J. 2004. Hypercomputation: philosophical issues. Theoretical Computer Science 317: 251-267.

Copeland, B. J. & Shagrir, O. 2007. Physical Computation: How General are Gandy’s Principles for Mechanisms?. Minds & Machines 17: 217-231.

Copeland, B. J. & Shagrir, O. 2011. Do Accelerating Turing Machines Compute the Uncomputable?. Minds and Machines 21(2): 221-239.

Davies, E.B. 2001. Building infinite machines. British Journal for the Philosophy of Science 52(4): 671-682.

Davis, M. 1982. Computability and unsolvability. Nueva York: Dover.

Davis, M. 2006. Why there is no such discipline as hypercomputation. Applied Mathematics and Computation 178(1): 4-7.

Deutsch, D. 1985. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London 400: 97-117.

Earman, J. 1995. Bangs, Crunches, Whimpers, and Shrieks: Singularities and Acausalities in Relativistic Spacetimes. Oxford: Oxford University Press.

Earman, J. & Norton, J. 1993. Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes. Philosophy of Science 60(1): 22-42.

Etesi, G. & Németi, I 2002. Non-Turing Computations via Malament-Hogarth Spacetimes. International Journal of Theoretical Physics 41: 342-70.

Gandy, R. 1980. Church’s thesis and the principles for mechanisms. In: J. Barwise,; H. J. Keisler; K. Kunen (ed.), The Kleene symposium. Ámsterdam: North-Holland.

Hogarth, M. 1994. Non-Turing computers and non-Turing computability. Proceedings of the Biennial Meeting of the Philosophy of Science Association 1: 126-138.

Kripke, S. 2013. The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In: B. J. Copeland; C. Posy; O. Shagrir (ed.), Computability: Turing, Gödel, Church, and Beyond, p.77-104. Cambridge: The MIT Press.

Manchak, J. 2010. On the Possibility of Supertasks in General Relativity. Foundations of Physics 40(3): 276-288.

Manchak, J. 2020. Malament-Hogarth Machines. British Journal for the Philosophy of Science 71(3): 1143-1153.

Piccinini, G. 2015. Physical Computation. A Mechanistic Account. Oxford: Oxford University Press.

Piccinini, G. & Maley, C. 2021. Computation in Physical Systems. In: E. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Edición de verano 2021. https://plato.stanford.edu/archives/sum2021/entries/computation-physicalsystems.

Pitowsky, I. 1990. The Physical Church Thesis and Physical Computational Complexity. Iyyun 39: 81-99.

Shagrir, O. & Pitowsky, I. 2003. Physical hypercomputation and the church-turing thesis. Minds and Machines 13(1): 87-101.

Sieg, W. 2002. Calculations by man and machine: Mathematical presentation. In: P. Gardenfors; J. Wolenski; K. Kijania-Placek (ed.), In the Scope of Logic, Methodology and Philosophy of Science, vol.I, p.247-262. Países Bajos: Kluwer Academic Publishers.

Sieg, W. 2008. Church Without Dogma: Axioms for Computability. In: S. B. Cooper; B. Löwe; A. Sorbi (ed.), New Computational Paradigms, p.139-152. Nueva York: Springer.

Thomson, J. F. 1954 Tasks and super-tasks. Analysis 15(1): 1-13.

Turing, A. 1936. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the Mathematical Society 42: 230-265.

Wolfram, S. 1985. Undecidability and Intractability in Theoretical Physics. Physical Review Letters 54: 735-738.