Hipercomputación
Modelos de computación

La hipercomputación o computación super-Turing es un conjunto de modelos hipotéticos de computación que pueden proporcionar resultados que no son computables mediante el método de Turing . Por ejemplo, una máquina que pudiera resolver el problema de la detención sería una hipercomputadora; también lo sería una que pudiera evaluar correctamente cada enunciado de la aritmética de Peano .

La tesis de Church-Turing afirma que cualquier función "computable" que pueda ser calculada por un matemático con lápiz y papel utilizando un conjunto finito de algoritmos simples, puede ser calculada por una máquina de Turing. Las hipercomputadoras calculan funciones que una máquina de Turing no puede y que, por lo tanto, no son computables en el sentido de Church-Turing.

Técnicamente, la salida de una máquina de Turing aleatoria es incomputable; sin embargo, la mayor parte de la literatura sobre hipercomputación se centra en el cálculo de funciones deterministas, en lugar de funciones aleatorias e incomputables.

Historia

Alan Turing introdujo un modelo computacional que iba más allá de las máquinas de Turing en su tesis doctoral de 1938, Sistemas de lógica basados ​​en ordinales . [1] En este trabajo se investigaron sistemas matemáticos en los que había un oráculo disponible que podía calcular una única función arbitraria (no recursiva) de números naturales a números naturales. Turing utilizó este dispositivo para demostrar que incluso en esos sistemas más potentes, la indecidibilidad sigue estando presente. Las máquinas oráculo de Turing son abstracciones matemáticas y no son físicamente realizables. [2]

Espacio de estados

En cierto sentido, la mayoría de las funciones son incomputables: hay funciones computables, pero hay un número incontable ( ) de posibles funciones super-Turing. [3] ℵ 0 estilo de visualización {\aleph _{0}} 2 ℵ 0 {\displaystyle 2^{\aleph _ {0}}}

Modelos

Los modelos de hipercomputadoras varían desde los útiles pero probablemente irrealizables (como las máquinas oráculo originales de Turing) hasta los generadores de funciones aleatorias menos útiles que son más plausiblemente "realizables" (como una máquina de Turing aleatoria ).

Entradas no computables o componentes de caja negra

Un sistema al que se le conceda el conocimiento de la constante de Chaitin (un número con una secuencia infinita de dígitos que codifican la solución al problema de la detención) como entrada, que no se puede calcular, puede resolver una gran cantidad de problemas indecidibles útiles; un sistema al que se le conceda un generador de números aleatorios no computables como entrada puede crear funciones aleatorias no computables, pero en general no se cree que sea capaz de resolver de manera significativa funciones incomputables "útiles", como el problema de la detención. Existe una cantidad ilimitada de tipos diferentes de hipercomputadoras concebibles, entre ellos:

  • Máquinas oráculo originales de Turing, definidas por Turing en 1939.
  • Una computadora real (una especie de computadora analógica idealizada ) puede realizar hipercomputación [4] si la física admite variables reales generales (no solo reales computables ), y estas son de alguna manera "aprovechables" para cálculos útiles (en lugar de aleatorios). Esto podría requerir leyes de física bastante extrañas (por ejemplo, una constante física medible con un valor oracular, como la constante de Chaitin ), y requeriría la capacidad de medir el valor físico de valor real con precisión arbitraria, aunque la física estándar hace que tales mediciones de precisión arbitraria sean teóricamente inviables. [5]
    • De manera similar, una red neuronal que de alguna manera tuviera la constante de Chaitin exactamente incorporada en su función de peso sería capaz de resolver el problema de detención, [6] pero está sujeta a las mismas dificultades físicas que otros modelos de hipercomputación basados ​​en computación real.
  • Ciertas "máquinas de Turing difusas" basadas en lógica difusa pueden, por definición, resolver accidentalmente el problema de detención, pero sólo porque su capacidad para resolver el problema de detención se asume indirectamente en la especificación de la máquina; esto tiende a verse como un "error" en la especificación original de las máquinas. [7] [8]
    • De manera similar, un modelo propuesto conocido como no determinismo justo puede permitir accidentalmente el cálculo oracular de funciones no computables, porque algunos de esos sistemas, por definición, tienen la capacidad oracular de identificar entradas rechazadas que harían "injustamente" que un subsistema funcionara para siempre. [9] [10]
  • Dmytro Taranovsky ha propuesto un modelo finitista de ramas de análisis tradicionalmente no finitistas, construido alrededor de una máquina de Turing equipada con una función de rápido crecimiento como su oráculo. Mediante este y otros modelos más complicados fue capaz de dar una interpretación de la aritmética de segundo orden. Estos modelos requieren una entrada no computable, como un proceso físico de generación de eventos donde el intervalo entre eventos crece a una tasa incomputablemente grande. [11]
    • De manera similar, una interpretación poco ortodoxa de un modelo de no determinismo ilimitado postula, por definición, que el tiempo que un "Actor" necesita para asentarse es fundamentalmente incognoscible y, por lo tanto, no se puede demostrar, dentro del modelo, que no lleva un período de tiempo incalculablemente largo. [12]

Modelos de “pasos computacionales infinitos”

Para funcionar correctamente, ciertos cálculos realizados por las máquinas que se indican a continuación requieren literalmente espacio físico y recursos infinitos, en lugar de simplemente ilimitados pero finitos; en contraste, con una máquina de Turing, cualquier cálculo que se detenga requerirá solo espacio físico y recursos finitos.

Una máquina de Turing que puede completar una cantidad infinita de pasos en un tiempo finito, una hazaña conocida como supertarea . Simplemente ser capaz de ejecutar un número ilimitado de pasos no es suficiente. Un modelo matemático es la máquina de Zenón (inspirada en la paradoja de Zenón ). La máquina de Zenón realiza su primer paso de cálculo en (digamos) 1 minuto, el segundo paso en ½ minuto, el tercer paso en ¼ de minuto, etc. Sumando 1 + ½ + ¼ + ... (una serie geométrica ) vemos que la máquina realiza una cantidad infinita de pasos en un total de 2 minutos. Según Oron Shagrir , las máquinas de Zenón introducen paradojas físicas y su estado es lógicamente indefinido fuera del período abierto de un lado de [0, 2), por lo que es indefinido exactamente a los 2 minutos después del comienzo del cálculo. [13]

Parece natural que la posibilidad de viajar en el tiempo (existencia de curvas temporales cerradas (CTC)) haga posible por sí misma la hipercomputación. Sin embargo, esto no es así, ya que una CTC no proporciona (por sí misma) la cantidad ilimitada de almacenamiento que requeriría una computación infinita. No obstante, existen espacios-tiempos en los que la región CTC puede utilizarse para la hipercomputación relativista. [14] Según un artículo de 1992, [15] una computadora que opere en un espacio-tiempo de Malament-Hogarth o en órbita alrededor de un agujero negro giratorio [16] podría, en teoría, realizar cálculos no Turing para un observador dentro del agujero negro. [17] [18] El acceso a una CTC puede permitir la solución rápida de problemas PSPACE-completos , una clase de complejidad que, si bien es decidible por Turing, generalmente se considera computacionalmente intratable. [19] [20]

Modelos cuánticos

Algunos académicos conjeturan que un sistema mecánico cuántico que de alguna manera utiliza una superposición infinita de estados podría calcular una función no computable . [21] Esto no es posible utilizando el modelo estándar de computadora cuántica qubit , porque está demostrado que una computadora cuántica regular es reducible por PSPACE (una computadora cuántica que funciona en tiempo polinomial puede ser simulada por una computadora clásica que funciona en espacio polinomial ). [22]

Sistemas "eventualmente correctos"

Algunos sistemas físicamente realizables siempre convergerán eventualmente hacia la respuesta correcta, pero tienen el defecto de que a menudo generarán una respuesta incorrecta y permanecerán en ella por un período de tiempo incalculablemente grande antes de finalmente volver atrás y corregir el error.

A mediados de los años 1960, E. Mark Gold y Hilary Putnam propusieron de forma independiente modelos de inferencia inductiva (los "funcionales recursivos limitantes" [23] y los "predicados de ensayo y error", [24] respectivamente). Estos modelos permiten que algunos conjuntos no recursivos de números o idiomas (incluidos todos los conjuntos de idiomas recursivamente enumerables ) se "aprendan en el límite"; mientras que, por definición, una máquina de Turing solo podría identificar conjuntos recursivos de números o idiomas. Si bien la máquina se estabilizará en la respuesta correcta en cualquier conjunto aprendible en un tiempo finito, solo puede identificarla como correcta si es recursiva; de lo contrario, la corrección solo se establece ejecutando la máquina para siempre y notando que nunca revisa su respuesta. Putnam identificó esta nueva interpretación como la clase de predicados "empíricos", afirmando: "si siempre 'postulamos' que la respuesta generada más recientemente es correcta, cometeremos un número finito de errores, pero eventualmente obtendremos la respuesta correcta. (Obsérvese, sin embargo, que incluso si hemos llegado a la respuesta correcta (el final de la secuencia finita) nunca estamos seguros de tener la respuesta correcta.)" [24] El artículo de LK Schubert de 1974 "Iterated Limiting Recursion and the Program Minimization Problem" [25] estudió los efectos de iterar el procedimiento de limitación; esto permite calcular cualquier predicado aritmético . Schubert escribió: "Intuitivamente, la identificación iterada de limitación podría considerarse como una inferencia inductiva de orden superior realizada colectivamente por una comunidad cada vez mayor de máquinas de inferencia inductiva de orden inferior".

Una secuencia de símbolos es computable en el límite si hay un programa finito, posiblemente sin detención, en una máquina de Turing universal que genera de forma incremental cada símbolo de la secuencia. Esto incluye la expansión diádica de π y de todos los demás números reales computables , pero aún excluye todos los números reales no computables. Las "máquinas de Turing monótonas" utilizadas tradicionalmente en la teoría del tamaño de descripción no pueden editar sus salidas anteriores; las máquinas de Turing generalizadas, según la definición de Jürgen Schmidhuber , sí pueden. Define las secuencias de símbolos descriptibles de forma constructiva como aquellas que tienen un programa finito, sin detención, ejecutándose en una máquina de Turing generalizada, de modo que cualquier símbolo de salida finalmente converge; es decir, no cambia más después de un intervalo de tiempo inicial finito. Debido a las limitaciones exhibidas por primera vez por Kurt Gödel (1931), puede ser imposible predecir el tiempo de convergencia en sí mismo mediante un programa con detención, de lo contrario, el problema de la detención podría resolverse. Schmidhuber ( [26] [27] ) utiliza este enfoque para definir el conjunto de universos formalmente descriptibles o constructivamente computables o teorías constructivas del todo . Las máquinas de Turing generalizadas pueden eventualmente converger a una solución correcta del problema de detención mediante la evaluación de una secuencia de Specker .

Análisis de capacidades

Muchas propuestas de hipercomputación equivalen a formas alternativas de leer un oráculo o una función de asesoramiento incrustada en una máquina que de otro modo sería clásica. Otras permiten el acceso a un nivel superior de la jerarquía aritmética . Por ejemplo, las máquinas de Turing con supertarea, bajo los supuestos habituales, podrían calcular cualquier predicado en el grado de la tabla de verdad que contenga o . La recursión limitante, por el contrario, puede calcular cualquier predicado o función en el grado de Turing correspondiente , que se sabe que es . Gold demostró además que limitar la recursión parcial permitiría el cálculo de precisamente los predicados. Σ 1 0 {\displaystyle \Sigma _{1}^{0}} P 1 0 Estilo de visualización: Pi _{1}^{0}} Δ 2 0 {\displaystyle \Delta _{2}^{0}} Σ 2 0 {\displaystyle \Sigma _{2}^{0}}

ModeloPredicados computablesNotasReferencias
supertarea El o ⁡ ( Σ 1 0 , P 1 0 ) {\displaystyle \operatorname {tt} \izquierda(\Sigma _{1}^{0},\Pi _{1}^{0}\derecha)} dependiente del observador externo[28]
Limitación/ensayo y error Δ 2 0 {\displaystyle \Delta _{2}^{0}} [23]
límite iterado ( k veces) Δ a + 1 0 {\displaystyle \Delta _ {k+1}^{0}} [25]
Máquina Blum–Shub–SmaleIncomparable con las funciones reales computables tradicionales[29]
Espacio-tiempo de Malament-HogarthHipertensióndepende de la estructura del espacio-tiempo[30]
red neuronal recurrente analógica Δ 1 0 [ F ] {\displaystyle \Delta _{1}^{0}[f]} f es una función de asesoramiento que proporciona pesos de conexión; el tamaño está limitado por el tiempo de ejecución[31] [32]
máquina de Turing de tiempo infinito A Q I {\displaystyle ICA} Conjuntos cuasi-inductivos aritméticos[33]
máquina de Turing difusa clásica Σ 1 0 ∪ P 1 0 {\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}} para cualquier norma t computable[8]
función creciente oráculo Δ 1 1 {\displaystyle \Delta _ {1}^{1}} para el modelo de una secuencia; son re P 1 1 Estilo de visualización: Pi _{1}^{1}} [11]

Crítica

Martin Davis , en sus escritos sobre hipercomputación, [34] [35] se refiere a este tema como "un mito" y ofrece contraargumentos a la viabilidad física de la hipercomputación. En cuanto a su teoría, argumenta en contra de las afirmaciones de que se trata de un campo nuevo fundado en la década de 1990. Este punto de vista se basa en la historia de la teoría de la computabilidad (grados de irresolubilidad, computabilidad sobre funciones, números reales y ordinales), como también se mencionó anteriormente. En su argumento, hace una observación de que toda la hipercomputación es poco más que: " si se permiten entradas no computables, entonces se pueden lograr salidas no computables " . [36]

Véase también

Referencias

  1. ^ Turing, AM (1939). "Sistemas de lógica basados ​​en ordinales†". Actas de la London Mathematical Society . 45 : 161–228. doi :10.1112/plms/s2-45.1.161. hdl : 21.11116/0000-0001-91CE-3 .
  2. ^ "Supongamos que se nos proporciona algún medio no especificado para resolver problemas de teoría de números; una especie de oráculo, por así decirlo. No profundizaremos más en la naturaleza de este oráculo, salvo decir que no puede ser una máquina" (Undecidable, p. 167, una reimpresión del artículo de Turing Systems of Logic Based On Ordinals )
  3. ^ J. Cabessa; HT Siegelmann (abril de 2012). "El poder computacional de las redes neuronales recurrentes interactivas" (PDF) . Neural Computation . 24 (4): 996–1019. CiteSeerX 10.1.1.411.7540 . doi :10.1162/neco_a_00263. PMID  22295978. S2CID  5826757. 
  4. ^ Arnold Schönhage , "Sobre el poder de las máquinas de acceso aleatorio", en Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP) , páginas 520–529, 1979. Fuente de la cita: Scott Aaronson , "NP-complete Problems and Physical Reality"[1] p. 12
  5. ^ Andrew Hodges. "Los profesores y las tormentas de ideas". Página de inicio de Alan Turing . Consultado el 23 de septiembre de 2011 .
  6. ^ HT Siegelmann; ED Sontag (1994). "Computación analógica mediante redes neuronales". Ciencias de la computación teórica . 131 (2): 331–360. doi : 10.1016/0304-3975(94)90178-3 .
  7. ^ Biacino, L.; Gerla, G. (2002). "Lógica difusa, continuidad y efectividad". Archivo de Lógica Matemática . 41 (7): 643–667. CiteSeerX 10.1.1.2.8029 . doi :10.1007/s001530100128. ISSN  0933-5846. S2CID  12513452. 
  8. ^ ab Wiedermann, Jiří (2004). "Caracterización de la potencia de cálculo super-Turing y la eficiencia de las máquinas de Turing difusas clásicas". Ciencias de la computación teórica . 317 (1–3): 61–69. doi : 10.1016/j.tcs.2003.12.004 . Su (capacidad para resolver el problema de detención) se debe a su criterio de aceptación en el que se asume indirectamente la capacidad para resolver el problema de detención.
  9. ^ Edith Spaan; Leen Torenvliet; Peter van Emde Boas (1989). "No determinismo, equidad y una analogía fundamental". Boletín EATCS . 37 : 186-193.
  10. ^ Ord, Toby (2006). "Las múltiples formas de hipercomputación". Matemáticas Aplicadas y Computación . 178 : 143–153. doi :10.1016/j.amc.2005.09.076.
  11. ^ por Dmytro Taranovsky (17 de julio de 2005). "Finitismo e hipercomputación" . Consultado el 26 de abril de 2011 .
  12. ^ Hewitt, Carl. "¿Qué es el compromiso?". Coordinación, organizaciones, instituciones y normas en sistemas de agentes II: AAMAS (2006).
  13. ^ Estos modelos han sido desarrollados de forma independiente por muchos autores diferentes, incluido Hermann Weyl (1927). Philosophie der Mathematik und Naturwissenschaft .; el modelo se analiza en Shagrir, O. (junio de 2004). "Supertareas, máquinas de Turing aceleradas e incomputabilidad". Theoretical Computer Science . 317 (1–3): 105–114. doi : 10.1016/j.tcs.2003.12.007 ., Petrus H. Potgieter (julio de 2006). "Máquinas Zeno e hipercomputación". Ciencias Informáticas Teóricas . 358 (1): 23–33. arXiv : cs/0412022 . doi :10.1016/j.tcs.2005.11.040. S2CID  6749770.y Vincent C. Müller (2011). "Sobre las posibilidades de hipercomputar supertareas". Mentes y máquinas . 21 (1): 83–96. CiteSeerX 10.1.1.225.3696 . doi :10.1007/s11023-011-9222-6. S2CID  253434. 
  14. ^ Andréka, Hajnal; Németi, István; Székely, Gergely (2012). "Curvas temporales cerradas en computación relativista". Cartas de procesamiento paralelo . 22 (3). arXiv : 1105.0047 . doi :10.1142/S0129626412400105. S2CID  16816151.
  15. ^ Hogarth, Mark L. (1992). "¿Permite la relatividad general a un observador ver una eternidad en un tiempo finito?". Fundamentos de Física Letters . 5 (2): 173–181. Bibcode :1992FoPhL...5..173H. doi :10.1007/BF00682813. S2CID  120917288.
  16. ^ István Neméti; Hajnal Andréka (2006). "¿Pueden los ordenadores relativistas generales romper la barrera de Turing?". Enfoques lógicos para las barreras computacionales, Segunda Conferencia sobre Computabilidad en Europa, CiE 2006, Swansea, Reino Unido, 30 de junio-5 de julio de 2006. Actas . Apuntes de clase en Ciencias de la Computación. Vol. 3988. Springer. doi :10.1007/11780342. ISBN . 978-3-540-35466-6.
  17. ^ Etesi, Gabor; Nemeti, Istvan (2002). "Cálculos no Turing a través de los espacios-tiempos de Malament-Hogarth". Revista Internacional de Física Teórica . 41 (2): 341–370. arXiv : gr-qc/0104023 . doi :10.1023/A:1014019225365. S2CID  17081866.
  18. ^ Earman, John; Norton, John D. (1993). "La eternidad es un día: supertareas en los espacio-tiempos de Pitowsky y Malament-Hogarth". Filosofía de la ciencia . 60 : 22–42. doi :10.1086/289716. S2CID  122764068.
  19. ^ Brun, Todd A. (2003). "Las computadoras con curvas temporales cerradas pueden resolver problemas difíciles". Encontrado. Phys. Lett . 16 (3): 245–253. arXiv : gr-qc/0209061 . doi :10.1023/A:1025967225931. S2CID  16136314.
  20. ^ S. Aaronson y J. Watrous. Las curvas temporales cerradas hacen que la computación cuántica y clásica sean equivalentes [2]
  21. ^ Se han hecho algunas afirmaciones en este sentido; véase Tien Kieu (2003). "Algoritmo cuántico para el décimo problema de Hilbert" . Int. J. Theor. Phys . 42 (7): 1461–1478. arXiv : quant-ph/0110136 . doi :10.1023/A:1025780028846. S2CID  6634980.o M. Ziegler (2005). "Poder computacional del paralelismo cuántico infinito". Revista internacional de física teórica . 44 (11): 2059–2071. arXiv : quant-ph/0410141 . Código Bibliográfico :2005IJTP...44.2059Z. doi :10.1007/s10773-005-8984-0. S2CID  9879859.y la literatura resultante. Para una réplica, véase Warren D. Smith (2006). "Tres contraejemplos que refutan el plan de Kieu para la "hipercomputación adiabática cuántica"; y algunas tareas mecánicas cuánticas no computables". Matemáticas Aplicadas y Computación . 178 (1): 184–193. doi :10.1016/j.amc.2005.09.078..
  22. ^ Bernstein, Ethan; Vazirani, Umesh (1997). "Teoría de la complejidad cuántica". Revista SIAM de informática . 26 (5): 1411–1473. doi :10.1137/S0097539796300921.
  23. ^ ab EM Gold (1965). "Limiting Recursion" (Limitación de la recursión). Revista de lógica simbólica . 30 (1): 28–48. doi :10.2307/2270580. JSTOR  2270580. S2CID  33811657., E. Mark Gold (1967). "Identificación del lenguaje en el límite". Información y Control . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
  24. ^ por Hilary Putnam (1965). "Predicados de ensayo y error y la solución a un problema de Mostowksi". Journal of Symbolic Logic . 30 (1): 49–57. doi :10.2307/2270581. JSTOR  2270581. S2CID  44655062.
  25. ^ ab LK Schubert (julio de 1974). "Recursión iterada limitante y el problema de minimización del programa". Revista de la ACM . 21 (3): 436–445. doi : 10.1145/321832.321841 . S2CID  2071951.
  26. ^ Schmidhuber, Juergen (2000). "Teorías algorítmicas del todo". arXiv : quant-ph/0011122 .
  27. ^ J. Schmidhuber (2002). "Jerarquías de complejidades de Kolmogorov generalizadas y medidas universales no numerables computables en el límite". Revista Internacional de Fundamentos de la Ciencia de la Computación . 13 (4): 587–612. arXiv : quant-ph/0011122 . Código Bibliográfico :2000quant.ph.11122S. doi :10.1142/S0129054102001291.
  28. ^ Petrus H. Potgieter (julio de 2006). "Máquinas Zeno e hipercomputación". Ciencias Informáticas Teóricas . 358 (1): 23–33. arXiv : cs/0412022 . doi :10.1016/j.tcs.2005.11.040. S2CID  6749770.
  29. ^ Lenore Blum , Felipe Cucker, Michael Shub y Stephen Smale (1998). Complejidad y computación real . Springer. ISBN 978-0-387-98281-6.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  30. ^ PD Welch (2008). "El alcance de la computación en los espaciotiempos de Malament-Hogarth". British Journal for the Philosophy of Science . 59 (4): 659–674. arXiv : gr-qc/0609035 . doi :10.1093/bjps/axn031.
  31. ^ HT Siegelmann (abril de 1995). "Computación más allá del límite de Turing" (PDF) . Science . 268 (5210): 545–548. Bibcode :1995Sci...268..545S. doi :10.1126/science.268.5210.545. PMID  17756722. S2CID  17495161.
  32. ^ Hava Siegelmann ; Eduardo Sontag (1994). "Computación analógica mediante redes neuronales". Ciencias de la computación teórica . 131 (2): 331–360. doi : 10.1016/0304-3975(94)90178-3 .
  33. ^ PD Welch (2009). "Características de los modelos de máquinas de Turing de tiempo transfinito discreto: tiempos de detención, tiempos de estabilización y teoremas de forma normal". Ciencias de la computación teórica . 410 (4–5): 426–442. doi : 10.1016/j.tcs.2008.09.050 .
  34. ^ Davis, Martin (2006). "Por qué no existe una disciplina llamada hipercomputación". Matemáticas Aplicadas y Computación . 178 (1): 4–7. doi :10.1016/j.amc.2005.09.066.
  35. ^ Davis, Martin (2004). "El mito de la hipercomputación". Alan Turing: vida y legado de un gran pensador . Springer.
  36. ^ Martín Davis (enero de 2003). "El mito de la hipercomputación". En Alexandra Shlapentokh (ed.). Minitaller: Décimo problema de Hilbert, conjetura de Mazur y secuencias de divisibilidad (PDF) . Informe MFO. vol. 3. Mathematisches Forschungsinstitut Oberwolfach. pag. 2.

Lectura adicional

  • Aoun, Mario Antoine (2016). «Avances en tres modelos de hipercomputación» (PDF) . Revista electrónica de física teórica . 13 (36): 169–182. Archivado desde el original (PDF) el 2017-02-06 . Consultado el 2023-07-28 .
  • Burgin, MS (1983). "Máquinas de Turing inductivas". Avisos de la Academia de Ciencias de la URSS . 270 (6): 1289–1293.
  • Burgin, Mark (2005). Algoritmos superrecursivos . Monografías en informática. Springer. ISBN 0-387-95569-0.
  • Cockshott, P.; Michaelson, G. (2007). "¿Existen nuevos modelos de computación? Respuesta a Wegner y Eberbach". The Computer Journal . doi :10.1093/comjnl/bxl062.
  • Cooper, SB; Odifreddi, P. (2003). "Incomputability in Nature" (PDF) . En Cooper, SB; Goncharov, SS (eds.). Computability and Models: Perspectives East and West . Nueva York, Boston, Dordrecht, Londres, Moscú: Plenum Publishers. págs. 137–160. Archivado desde el original (PDF) el 24 de julio de 2011. Consultado el 16 de junio de 2011 .
  • Cooper, SB (2006). "Definibilidad como efecto hipercomputacional". Matemáticas Aplicadas y Computación . 178 : 72–82. CiteSeerX  10.1.1.65.4088 . doi :10.1016/j.amc.2005.09.072. S2CID  1487739.
  • Copeland, J. (2002). "Hipercomputación" (PDF) . Mentes y máquinas . 12 (4): 461–502. doi :10.1023/A:1021105915386. S2CID  218585685. Archivado desde el original (PDF) el 14 de marzo de 2016.
  • Hagar, A.; Korolev, A. (2007). "Hipercomputación cuántica: ¿exageración o computación?*" (PDF) . Filosofía de la ciencia . 74 (3): 347–363. doi :10.1086/521969. S2CID  9857468.
  • Ord, Toby (2002). "Hipercomputación: calcular más de lo que la máquina de Turing puede calcular: un artículo de revisión sobre diversas formas de hipercomputación". arXiv : math/0209332 .
  • Piccinini, Gualtiero (16 de junio de 2021). «Computación en sistemas físicos». Stanford Encyclopedia of Philosophy . Consultado el 31 de julio de 2023 .
  • Sharma, Ashish (2022). "Algoritmos inspirados en la naturaleza con perspectiva hipercomputacional aleatoria". Ciencias de la información . 608 : 670–695. doi :10.1016/j.ins.2022.05.020. S2CID  248881264.
  • Stannett, Mike (1990). "Máquinas X y el problema de la detención: construcción de una supermáquina de Turing". Aspectos formales de la computación . 2 (1): 331–341. doi : 10.1007/BF01888233 . S2CID  7406983.
  • Stannett, Mike (2006). "El caso de la hipercomputación" (PDF) . Applied Mathematics and Computation . 178 (1): 8–24. doi :10.1016/j.amc.2005.09.067. Archivado desde el original (PDF) el 4 de marzo de 2016.
  • Syropoulos, Apostolos (2008). Hipercomputación: computación más allá de la barrera de Church-Turing . Springer. ISBN 978-0-387-30886-9.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Hipercomputación&oldid=1242561379"