Do Accelerating Turing Machines Exist?

Paradoxes and Logical Possibilites

Authors

  • José Alejandro Fernández Cuesta Complutense University of Madrid

DOI:

https://doi.org/10.37467/revtechno.v13.5005

Keywords:

Accelerating Turing Machines, Super-task, Paradoxes, Existence, Logical Possibility, Modal Analysis, Philosophy of Computation

Abstract

Accelerating Turing Machines (ATMs) are devices capable of executing super-tasks. However, the mere exercise of definition has generated several paradoxes. This paper will define the notions of super-task and ATM in a comprehensive way and will clarify what should be understood in a formal-logical context when asking about the existence of an object. Following the distinction between logical and physical possibilities, the paradoxes will be dissolved and it will be concluded that ATMs are possible and exist as abstract objects.

References

Achtner, W. (2005). Infinity in science and religion. The creative role of thinking about infinity. Neue Zeitschrift für systematische Theologie und Religionsphilosophie, 47, 392-411. DOI: https://doi.org/10.1515/nzst.2005.47.4.392

Allis, V. y Koetsier, T. (1991). On some paradoxes of the infinite I. The British Journal for the Philosophy of Science, 42, p. 187-194. DOI: https://doi.org/10.1093/bjps/42.2.187

Allis, V. y Koetsier, T. (1995). On some paradoxes of the infinite II. The British Journal for the Philosophy of Science, 46, 235-247. DOI: https://doi.org/10.1093/bjps/46.2.235

Alonso, J. A. et al. (2007). Curso práctico de teoría de conjuntos. Repositorio de la Universidad de Sevilla: <http://www.cs.us.es/~jalonso/publicaciones/2007-LibroTeoriaConjuntos.pdf>.

Ambrose, A. (1935). Finitism in Mathematics (I y II). Mind, 35, 186-203 y 317-340. DOI: https://doi.org/10.1093/mind/XLIV.175.317

Benacerraf, P. (1962). Tasks, Super-Tasks, and the Modern Eleatics. Journal of Philosophy 59, 765-784. DOI: https://doi.org/10.2307/2023500

van Bendegem, (1994). Ross’ Paradox is an Impossible Super-task. British Journal of Philosophy of Science, 45, 743-748:

Benítez, A. (2022). Inteligencia Artifical en perspectiva. Madrid.

Black, M (1951). Achilles and the Tortoise, Analysis 11, 91–101. DOI: https://doi.org/10.1093/analys/11.5.91

Blake, R. M. (1926). The Paradox of Temporal Process, Journal of Philosophy 23, 645–654. DOI: https://doi.org/10.2307/2013813

Boolos, G. S. y Jeffrey, R. C. (1980). Computability and Logic, 2nd edition, Cambridge: Cambridge University Press

Carnap, R. (1932). Überwindung der Metaphysik durch Logische Analyse der Sprache. Erkenntnis, II. DOI: https://doi.org/10.1007/BF02028153

Chihara, C. S. (1965). On the Possibility of Completing an Infinite Process, Philosophical Review 74, 74–87. DOI: https://doi.org/10.2307/2183531

Copeland, B. J. (2002). Accelerating Turing Machines. Minds and Machines 12, 281-300. DOI: https://doi.org/10.1023/A:1015607401307

Copeland, B.J. and Sylvan, R. (1999). Beyond the Universal Turing Machine, Australasian Journal of Philosophy 77, 46–66. DOI: https://doi.org/10.1080/00048409912348801

Diels, H. y Krantz, W. (1952). Die Fragmente der Vorsokratiker. Sexta Edición. Cambridge.

Doyle, J. (1982). What is Church's Thesis? Laboratory of Computer Science, MIT, Cambridge, MA.

Drake, F. (1974). Set Theory. North Holland.

Earman, J. y Norton, J. D. (1993). Forever Is a Day: Supertasks in Pitowsky and Malament– DOI: https://doi.org/10.1086/289716

Hogarth Spacetimes. Philosophy of Science 60, 22–42.

Earman, J. y Norton, J. D. (1996). Infinite Pains: The Trouble with Supertasks, en A. Morton and S.P. Stich, eds., Benacerraf and his Critics, Oxford: Blackwell.

Fernández Cuesta, J. A. (2022). La lógica modal como herramienta metodológica en epistemología: notas para (otra) posible superación de los argumentos escépticos. Human Review. International Humanities Review, 11, 71-79. DOI: https://doi.org/10.37467/gkarevhuman.v11.3016

Fernández Cuesta, J. A. y Sánchez Ovcharov, C. (2023). Contrafácticos Cuánticos: aproximación lógico-filosófica a las medidas cuánticas sin interacción. Revista Colombiana de Filosofía de la Ciencia, 23 [aceptado y pendiente de publicación].

Fernández Mateo, J. (2022). Realidad artificial. Un análisis de las potenciales amenazas de la inteligencia Artificial. VISUAL REVIEW. International Visual Culture Review / Revista Internacional De Cultura Visual, 9(2), 235–247. DOI: https://doi.org/10.37467/revvisual.v9.5004

Fernández Prida, J. (2004). Teorías inseparables. Madrid: Trotta.

Frápolli Sanz, M. J. (2014). Cuerpos y números ¿Qué significa existir? En Villar Ezcurra, A. y Sánchez Orantos, A. (eds.), Una ciencia humana: libro homenaje a Camino Cañón Loyes (pp. 59-72). Universidad Pontificia de Comillas.

Frápolli Sanz, M. J. (2023). The Priority of Propositions. A Pragmatist Philosophy of Logic. Springer: Synthese Library, 475. DOI: https://doi.org/10.1007/978-3-031-25229-7

French, A. P. (1968). Special Relativity. MIT Introductory Physics.

Gherab Martín, K. (2022). Mentes contra Máquinas: revisión histórica y lógico-filosófica del argumento gödeliano de Lucas-Penrose. Human Review. International Humanities Review, 11, 185-195. DOI: https://doi.org/10.37467/revhuman.v11.4503

Gherab Martín, K. y Sánchez Ovcharov, C. (2010). Conociendo el efecto Zenón cuántico en experimentos contrafácticos: una aproximación filosófica. Ontology Studies 10, 115-130.

Gold, E. M. (1965). Limiting Recursion. Journal of Symbolic Logic 30, 28–48. DOI: https://doi.org/10.2307/2270580

Grünbaum, A. (1968). Modern Science and Zeno’s Paradoxes, London: Allen and Unwin.

Hamilton (1982). Numbers, Sets and Axioms: The Apparatus of Mathematics. New York: Cambridge University Press. DOI: https://doi.org/10.1017/CBO9781139171618

Hamkins (2002). Infinite Time Turing Machines. Minds and Machines, 12, 521-539. DOI: https://doi.org/10.1023/A:1021180801870

Hamkins, J. D. y Lewis, A. (2000). Infinite Time Turing Machines. Journal of Symbolic Logic, 65, 567–604. DOI: https://doi.org/10.2307/2586556

Hinton, J.M and Martin, C.B. (1954). Achilles and the Tortoise. Analysis 14, 56–68. DOI: https://doi.org/10.1093/analys/14.3.56

Hofstadter, D.R. (1980). Gödel, Escher, Bach: An Eternal Golden Braid, Harmondsworth: Penguin.

Hogarth, M.L. (1992). Does General Relativity Allow an Observer to View an Eternity in a Finite Time?. Foundations of Physics Letters 5, 173–181. DOI: https://doi.org/10.1007/BF00682813

Holgate, J. (1994). Mathematical Notes on Ross' Paradox. British Journal for the Philosophy of Science, 45,302-4. DOI: https://doi.org/10.1093/bjps/45.1.302

Kripke (1982). Wittgenstein on Rules and Private Language. Harvard: Harvard University Press. Leblac (1993). Infinity in theology and mathematics. Religious Studies 29, 51-62.

Littlewood (1953). A Mathematician's Miscellany. London: Methuen.

Malík, J. (2022). Wrestling with the Posthuman: Understanding the Relationship between Human Autonomy and Technology. TECHNO REVIEW. International Technology, Science and Society Review /Revista Internacional De Tecnología, Ciencia Y Sociedad, 11(2), 141–158. DOI: https://doi.org/10.37467/gkarevtechno.v11.3252

Manzano, M. y Aranda, V. (2022). Many-Sorted Logic. The Stanford Encyclopedia of Philosophy. Edward N. Zalta and Uri Nodelman eds. < https://plato.stanford.edu/archives/win2022/entries/logic-many-sorted/>.

Ordóñez Pinilla, C. A. (2006). Monismo anómalo, intencionalidad, falacias mentales e inteligencia artificial. Bajo Palabra, (1), 38–54. DOI: https://doi.org/10.15366/bp2006.1.004

Post, E.L. (1936). Finite Combinatory Processes – Formulation 1. Journal of Symbolic Logic 1, 103–105. DOI: https://doi.org/10.2307/2269031

Priest, G. (2012). An Introduction to Non-Classical Logic. Segunda edición. Cambridge University Press.

Priest, G. (2014). One: Being an Investigation Into the Unity of Reality and of its Parts. New York: Oxford University Press. DOI: https://doi.org/10.1093/acprof:oso/9780199688258.001.0001

Putnam, H. (1965). Trial and Error Predicates and the Solution of a Problem of Mostowski. Journal of Symbolic Logic 30, 49–57. DOI: https://doi.org/10.2307/2270581

Rayo, A. y Williamson, T. (2003). A Completeness Theorem for Unrestricted First-Order Languages. En J. C. Beall ed. Liars and Heaps: New Essays on Paradox, Oxford: Oxford University Press.

Ross (1988). A First Course in Probability. Tercera edición. New York & London: Macmillan.

Royce (1899). The World and the Individual. Macmillan.

Russell, B.A.W. (1915). Our Knowledge of the External World as a Field for Scientific Method in Philosophy. Chicago: Open Court. DOI: https://doi.org/10.5962/bhl.title.2067

Russell, B.A.W. (1918). The Philosophy of Logical Atomism. En Logic and Knowledge, R. C. Marsh ed. London: Allen & Unwin, 177-281. DOI: https://doi.org/10.5840/monist19182843

Russell, B.A.W. (1924). Logical Atomism. En Logic and Knowledge, R. C. Marsh ed. London: Allen & Unwin, 160–179.

Russell, B.A.W. (1936). The Limits of Empiricism. Proceedings of the Aristotelian Society 36, 131–150. DOI: https://doi.org/10.1093/aristotelian/36.1.131

Schlick, M. (1930). Die Wende der Philosophie. Erkenntnis I. DOI: https://doi.org/10.1007/BF00208605

Shagrir, O. (2004). Super-tasks, accelerating Turing machines and uncomputability. Theoretical Computer Science, 317, 105-114. DOI: https://doi.org/10.1016/j.tcs.2003.12.007

Shagrir, O. (2007). Physical computation: How general are Gandy’s principles for mechanisms? Minds and Machines 17, 217-231. DOI: https://doi.org/10.1007/s11023-007-9058-2

Steinhart (2007). Infinitely complex machines. Intelligent Computing Everywhere. London: Springer, 25-43. DOI: https://doi.org/10.1007/978-1-84628-943-9_2

Stewart (1991). Deciding the Undecidable. Nature 352, 664–665. DOI: https://doi.org/10.1038/352664a0

Taylor (1951). Mr. Black on Temporal Paradoxes. Analysis 12, 38–44. DOI: https://doi.org/10.1093/analys/12.2.38

Thomson (1954). Tasks and Super-Tasks. Analysis 15, 1–13. DOI: https://doi.org/10.1093/analys/15.1.1

Turing (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42 (1936–37), 230–265. DOI: https://doi.org/10.1112/plms/s2-42.1.230

Turing (1950). ‘Programmers’ Handbook for Manchester Electronic Computer. University of Manchester Computing Laboratory. Un facsimile digital del original se puede consultar en The Turing Archive for the History of Computing: <http://www.AlanTuring.net/programmers_handbook>.

Tymoczko y Henle (1995). Sweet Reason: A Field Guide to Modern Logic. Freeman Press.

Van Bendegem (1994). Ross’ Paradox is an Impossible Super-task. British Journal of Philosophy of Science, 45, 743-748. DOI: https://doi.org/10.1093/bjps/45.2.743

Watling (1952). The Sum of an Infinite Series. Analysis 13, 39–46. DOI: https://doi.org/10.1093/analys/13.2.39

Weyl, H. (1927). Philosophie der Mathematik und Naturwissenschaft. Munich: R. Oldenbourg. Traducción inglesa citada siguiendo Weyl, H. (1963). Philosophy of Mathematics and Natural Science. New York: Atheneum.

Downloads

Published

2023-05-29

How to Cite

Fernández Cuesta, J. A. (2023). Do Accelerating Turing Machines Exist? Paradoxes and Logical Possibilites. TECHNO REVIEW. International Technology, Science and Society Review /Revista Internacional De Tecnología, Ciencia Y Sociedad, 13(1), 49–74. https://doi.org/10.37467/revtechno.v13.5005

Issue

Vol. 13 No. 1 (2023)

Section

Research articles

License

Those authors who publish in this journal accept the following terms:

  1. Authors will keep the moral right of the work and they will transfer the commercial rights.
  2. After 1 year from publication, the work shall thereafter be open access online on our website, but will retain copyright.
  3. In the event that the authors wish to assign an Creative Commons (CC) license, they may request it by writing to publishing@eagora.org