La hipercomputación o supercomputación de Turing se refiere a modelos de computación que pueden proporcionar resultados que no son computables por Turing . Por ejemplo, una máquina que podría resolver el problema de la detención sería una hipercomputadora; también lo haría uno que pueda evaluar correctamente cada enunciado en la aritmética de Peano .
La tesis de Church-Turing establece que cualquier función "computable" que pueda ser calculada por un matemático con lápiz y papel usando 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 incuestionable; sin embargo, la mayor parte de la literatura sobre hipercomputación se centra en cambio en el cálculo de funciones deterministas, más que aleatorias, no calculables.
Historia
Alan Turing introdujo un modelo computacional que va más allá de las máquinas de Turing en su tesis doctoral de 1938, Sistemas de lógica basada en ordinales . [1] Este artículo investigó sistemas matemáticos en los que se disponía de un oráculo , que podía calcular una única función arbitraria (no recursiva) de naturales a naturales. Usó este dispositivo para demostrar que incluso en esos sistemas más poderosos, la indecidibilidad todavía está presente. Las máquinas de oráculo de Turing son abstracciones matemáticas y no son realizables físicamente. [2]
Espacio de Estados
En cierto sentido, la mayoría de las funciones son incuestionables: hay funciones computables, pero hay un número incontable () de posibles funciones de Super-Turing. [3]
Modelos
Los modelos de hipercomputadora van desde útiles pero probablemente irrealizables (como las máquinas de oráculo originales de Turing), hasta generadores de funciones aleatorias menos útiles que son más plausiblemente "realizables" (como una máquina de Turing aleatoria ).
Entradas incomputables o componentes de caja negra
Un sistema al que se le concede el conocimiento de la constante oracular de Chaitin (un número con una secuencia infinita de dígitos que codifica la solución al problema que se detiene) como entrada puede resolver una gran cantidad de problemas indecidibles útiles; un sistema al que se le ha concedido un generador de números aleatorios no computable como entrada puede crear funciones aleatorias no computables, pero generalmente no se cree que sea capaz de resolver de manera significativa funciones no computables "útiles" como el problema de la detención. Hay un número ilimitado de tipos diferentes de hipercomputadoras imaginables, que incluyen:
- Las máquinas de 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 "adaptables" para cálculos útiles (en lugar de aleatorios). Esto podría requerir leyes de la 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 real con precisión arbitraria, aunque la física estándar hace que tales valores sean arbitrarios. -medidas de precisión teóricamente inviables. [5]
- De manera similar, una red neuronal que de alguna manera tuviera la constante de Chaitin incrustada exactamente en su función de peso podría resolver el problema de la 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 la detención, pero sólo porque su capacidad para resolver el problema de la 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 estos sistemas, por definición, tienen la capacidad oracular de identificar entradas de rechazo que causarían "injustamente" que un subsistema se ejecute para siempre. [9] [10]
- Dmytro Taranovsky ha propuesto un finitista modelo de ramas tradicionalmente no finitistas de análisis, construido alrededor de una máquina de Turing equipado con una función rápidamente creciente como su oráculo. Mediante este y otros modelos más complicados pudo dar una interpretación de la aritmética de segundo orden. Estos modelos requieren una entrada incontestable, como un proceso de generación de eventos físicos donde el intervalo entre eventos crece a un ritmo increíblemente grande. [11]
- De manera similar, una interpretación poco ortodoxa de un modelo de no determinismo ilimitado postula, por definición, que el período de tiempo requerido para que un "Actor" se establezca es fundamentalmente incognoscible y, por lo tanto, no se puede probar, dentro del modelo, que no requiere un período de tiempo incontestablemente largo. [12]
Modelos de "pasos computacionales infinitos"
Para que funcionen correctamente, ciertos cálculos de las máquinas siguientes requieren literalmente un espacio físico y recursos infinitos, en lugar de simplemente ilimitados pero finitos; en contraste, con una máquina de Turing, cualquier cálculo dado 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 . El simple hecho de poder ejecutar una cantidad ilimitada de pasos no es suficiente. Un modelo matemático es la máquina de Zeno (inspirada en la paradoja de Zeno ). La máquina Zeno realiza su primer paso de cálculo en (digamos) 1 minuto, el segundo paso en ½ minuto, el tercer paso en ¼ de minuto, etc. Al sumar 1 + ½ + ¼ + ... (una serie geométrica ) vemos que la máquina realiza una infinidad de pasos en un total de 2 minutos. Según Shagrir, las máquinas Zeno introducen paradojas físicas y su estado es lógicamente indefinido fuera del período abierto de un lado de [0, 2), por lo tanto indefinido exactamente 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 la hipercomputación por sí misma. Sin embargo, esto no es así, ya que un CTC no proporciona (por sí mismo) la cantidad ilimitada de almacenamiento que requeriría un cálculo infinito. Sin embargo, hay espaciotiempos en los que la región CTC se puede utilizar para hipercomputación relativista. [14] Según un artículo de 1992, [15] una computadora que opera en un espacio-tiempo de Malament-Hogarth o en órbita alrededor de un agujero negro en rotación [16] teóricamente podría realizar cálculos que no sean de Turing para un observador dentro del agujero negro. [17] [18] El acceso a un CTC puede permitir la solución rápida de problemas de PSPACE-completo , una clase de complejidad que, aunque Turing-decidible, generalmente se considera intratable computacionalmente. [19] [20]
Modelos cuánticos
Algunos estudiosos conjeturan que un sistema de mecánica cuántica que de alguna manera utiliza una superposición infinita de estados podría calcular una función no computable . [21] Esto no es posible con el estándar qubit -model ordenador cuántico , porque está comprobado que un ordenador cuántico regular es PSPACE reducible (un ordenador cuántico que se ejecuta en tiempo polinómico se puede simular un ordenador clásico que se ejecuta en el espacio polinomio ). [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 darán una respuesta incorrecta y se quedarán con la respuesta incorrecta durante un período de tiempo incontestablemente grande antes de eventualmente volver atrás y corregir el error.
- A mediados de la década de 1960, E Mark Gold y Hilary Putnam propusieron independientemente modelos de inferencia inductiva (los "funcionales recursivos limitantes" [23] y los "predicados de prueba 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 sólo podría identificar conjuntos recursivos de números o idiomas. Si bien la máquina se estabilizará con la respuesta correcta en cualquier conjunto que se pueda aprender en un tiempo finito, solo puede identificarla como correcta si es recursiva; de lo contrario, la corrección se establece solo ejecutando la máquina para siempre y observando 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. (Tenga en cuenta, 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 1974 de LK Schubert " Iterated Limiting Recursion and el Problema de Minimización del Programa " [25] estudió los efectos de iterar el procedimiento de limitación; esto permite calcular cualquier predicado aritmético . Schubert escribió: "Intuitivamente, la identificación limitante iterada 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 se puede calcular en el límite si hay un programa finito, posiblemente sin interrupciones, en una máquina universal de Turing que genere cada símbolo de la secuencia de forma incremental. Esto incluye la expansión diádica de π y de todos los demás reales computables , pero aún excluye todos los reales no computables. Las 'máquinas monótonas de Turing' utilizadas tradicionalmente en la teoría del tamaño de la descripción no pueden editar sus resultados anteriores; Máquinas de Turing generalizadas, según la definición de Jürgen Schmidhuber , can. Define las secuencias de símbolos que se pueden describir de forma constructiva como aquellas que tienen un programa finito que no se detiene ejecutándose en una máquina de Turing generalizada, de modo que cualquier símbolo de salida eventualmente converge; es decir, no cambia más después de un intervalo de tiempo inicial finito. Debido a las limitaciones mostradas por primera vez por Kurt Gödel (1931), puede ser imposible predecir el tiempo de convergencia en sí mediante un programa de 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 describibles o constructivamente computables o teorías constructivas de todo . Las máquinas de Turing generalizadas pueden eventualmente converger hacia 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 consejo incrustada en una máquina clásica. Otros permiten el acceso a un nivel superior de la jerarquía aritmética . Por ejemplo, las máquinas de Turing que superan la tarea, bajo los supuestos habituales, serían capaces de calcular cualquier predicado en el grado de la tabla de verdad que contenga o . La recursividad limitante, por el contrario, puede calcular cualquier predicado o función en el grado de Turing correspondiente , que se sabe que es. Gold mostró además que limitar la recursividad parcial permitiría el cálculo de predicados.
Modelo | Predicados computables | Notas | Refs |
---|---|---|---|
super pregunta | tt) | dependiente del observador externo | [28] |
limitación / ensayo y error | [23] | ||
limitación iterada ( k veces) | [25] | ||
Máquina Blum – Shub – Smale | incomparable con las funciones reales computables tradicionales | [29] | |
Espacio-tiempo de Malament – Hogarth | HYP | dependiente de la estructura del espacio-tiempo | [30] |
red neuronal recurrente analógica | f es una función de aviso 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 | Conjuntos aritméticos cuasi-inductivos | [33] | |
máquina de Turing borrosa clásica | para cualquier norma t computable | [8] | |
aumento de la función de oráculo | para el modelo de una secuencia; son re | [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 realizabilidad física de la hipercomputación. En cuanto a su teoría, argumenta en contra de las afirmaciones de que este es 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 insolubilidad, 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 obtener salidas no computables " . [36]
Ver también
- Cálculo
- Física digital
- Supertarea
Referencias
- ^ 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 .
- ^ "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 aparte de decir que no puede ser una máquina" (Indecidible p. 167, una reimpresión del artículo de Turing Systems of Logic Based On Ordinals )
- ^ J. Cabessa; HT Siegelmann (abril de 2012). "El poder computacional de las redes neuronales recurrentes interactivas" (PDF) . Computación neuronal . 24 (4): 996–1019. CiteSeerX 10.1.1.411.7540 . doi : 10.1162 / neco_a_00263 . PMID 22295978 .
- ^ Arnold Schönhage , "Sobre el poder de las máquinas de acceso aleatorio", en Proc. Intl. Coloquio sobre autómatas, lenguajes y programación (ICALP) , páginas 520–529, 1979. Fuente de la cita: Scott Aaronson , "NP-complete Problems and Physical Reality" [1] p. 12
- ^ Andrew Hodges. "Los profesores y las lluvias de ideas" . La página de inicio de Alan Turing . Consultado el 23 de septiembre de 2011 .
- ^ HT Siegelmann; ED Sontag (1994). "Computación analógica a través de redes neuronales" . Informática Teórica . 131 (2): 331–360. doi : 10.1016 / 0304-3975 (94) 90178-3 .
- ^ Biacino, L .; Gerla, G. (2002). "Lógica difusa, continuidad y eficacia". Archivo de lógica matemática . 41 (7): 643–667. CiteSeerX 10.1.1.2.8029 . doi : 10.1007 / s001530100128 . ISSN 0933-5846 .
- ^ a b 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" . Informática Teórica . 317 (1-3): 61-69. doi : 10.1016 / j.tcs.2003.12.004 .
Su (capacidad para resolver el problema de la detención) se debe a su criterio de aceptación en el que se asume indirectamente la capacidad de resolver el problema de la detención.
- ^ Edith Spaan; Leen Torenvliet; Peter van Emde Boas (1989). "No determinismo, equidad y una analogía fundamental". Boletín EATCS . 37 : 186-193.
- ^ Ord, Toby (2006). "Las muchas formas de hipercomputación". Matemática Aplicada y Computación . 178 : 143-153. doi : 10.1016 / j.amc.2005.09.076 .
- ^ a b Dmytro Taranovsky (17 de julio de 2005). "Finitismo e hipercomputación" . Consultado el 26 de abril de 2011 .
- ^ Hewitt, Carl. "¿Qué es el compromiso?" Física, Organizacional y Social (Revisada), Coordinación, Organizaciones, Instituciones y Normas en Sistemas de Agentes II: AAMAS (2006).
- ^ Estos modelos han sido desarrollados de forma independiente por muchos autores diferentes, incluidos Hermann Weyl (1927). Philosophie der Mathematik und Naturwissenschaft .; el modelo se discute en Shagrir, O. (junio de 2004). "Supertareas, máquinas de Turing aceleradoras e incomputabilidad" (PDF) . Informática Teórica . 317 (1-3): 105-114. doi : 10.1016 / j.tcs.2003.12.007 . Archivado desde el original (PDF) el 2007-07-09., Petrus H. Potgieter (julio de 2006). "Máquinas Zeno e hipercomputación". Informática Teórica . 358 (1): 23–33. arXiv : cs / 0412022 . doi : 10.1016 / j.tcs.2005.11.040 . y Vincent C. Müller (2011). "Sobre las posibilidades de las supertareas de hipercomputación" . Mentes y Máquinas . 21 (1): 83–96. CiteSeerX 10.1.1.225.3696 . doi : 10.1007 / s11023-011-9222-6 .
- ^ Andréka, Hajnal; Németi, István; Székely, Gergely (2012). "Curvas de tiempo cerradas en computación relativista". Cartas de procesamiento paralelo . 22 (3). arXiv : 1105.0047 . doi : 10.1142 / S0129626412400105 .
- ^ Hogarth, Mark L. (1992). "¿La relatividad general permite a un observador ver una eternidad en un tiempo finito?". Fundamentos de las letras de la física . 5 (2): 173–181. Código Bibliográfico : 1992FoPhL ... 5..173H . doi : 10.1007 / BF00682813 .
- ^ István Neméti; Hajnal Andréka (2006). "¿Pueden las computadoras relativistas generales romper la barrera de Turing?". Enfoques lógicos a las barreras computacionales, Segunda Conferencia sobre Computabilidad en Europa, CiE 2006, Swansea, Reino Unido, 30 de junio al 5 de julio de 2006. Actas . Apuntes de conferencias en informática. 3988 . Saltador. doi : 10.1007 / 11780342 . ISBN 978-3-540-35466-6.
- ^ Etesi, Gabor; Nemeti, Istvan (2002). "Cálculos que no son de Turing a través de espacio-tiempos de Malament-Hogarth". Revista Internacional de Física Teórica . 41 (2): 341–370. arXiv : gr-qc / 0104023 . doi : 10.1023 / A: 1014019225365 .
- ^ Earman, John; Norton, John D. (1993). "Forever is a Day: Supertasks in Pitowsky y Malament-Hogarth Spacetimes". Filosofía de la ciencia . 60 : 22–42. doi : 10.1086 / 289716 .
- ^ Brun, Todd A. (2003). "Las computadoras con curvas cerradas en forma de tiempo pueden resolver problemas difíciles". Found.phys.lett . 16 (3): 245-253. arXiv : gr-qc / 0209061 . doi : 10.1023 / A: 1025967225931 .
- ^ S. Aaronson y J. Watrous. Las curvas cerradas en forma de tiempo hacen que la computación clásica y cuántica sean equivalentes [2]
- ^ Ha habido algunas afirmaciones en este sentido; ver Tien Kieu (2003). "Algoritmo cuántico para el décimo problema de Hilbert" . En t. J. Theor. Phys . 42 (7): 1461-1478. arXiv : quant-ph / 0110136 . doi : 10.1023 / A: 1025780028846 . 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 .y la literatura subsiguiente. Para una réplica, vea 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 incontestables". Matemática Aplicada y Computación . 178 (1): 184-193. doi : 10.1016 / j.amc.2005.09.078 ..
- ^ Bernstein, Ethan; Vazirani, Umesh (1997). "Teoría de la complejidad cuántica" . Revista SIAM de Computación . 26 (5): 1411–1473. doi : 10.1137 / S0097539796300921 .
- ^ a b EM Gold (1965). "Limitar la recursividad". Revista de lógica simbólica . 30 (1): 28–48. doi : 10.2307 / 2270580 . JSTOR 2270580 ., E. Mark Gold (1967). "Identificación del idioma en el límite" . Información y control . 10 (5): 447–474. doi : 10.1016 / S0019-9958 (67) 91165-5 .
- ^ a b Hilary Putnam (1965). "Predicados de prueba y error y la solución a un problema de Mostowksi". Revista de lógica simbólica . 30 (1): 49–57. doi : 10.2307 / 2270581 . JSTOR 2270581 .
- ^ a b LK Schubert (julio de 1974). "Recurrencia limitante iterada y el problema de minimización del programa". Revista de la ACM . 21 (3): 436–445. doi : 10.1145 / 321832.321841 .
- ^ Schmidhuber, Juergen (2000). "Teorías algorítmicas del todo". arXiv : quant-ph / 0011122 .
- ^ J. Schmidhuber (2002). "Jerarquías de complejidades generalizadas de Kolmogorov y medidas universales no enumerables computables en el límite" . Revista Internacional de Fundamentos de la Ciencia de la Computación . 13 (4): 587–612. Código Bibliográfico : 2000quant.ph.11122S . doi : 10.1142 / S0129054102001291 .
- ^ Petrus H. Potgieter (julio de 2006). "Máquinas Zeno e hipercomputación". Informática Teórica . 358 (1): 23–33. arXiv : cs / 0412022 . doi : 10.1016 / j.tcs.2005.11.040 .
- ^ Lenore Blum , Felipe Cucker, Michael Shub y Stephen Smale (1998). Complejidad y Computación Real . ISBN 978-0-387-98281-6.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ PD Welch (2008). "El alcance de la computación en los espaciotiempos de Malament-Hogarth". Revista británica de filosofía de la ciencia . 59 (4): 659–674. arXiv : gr-qc / 0609035 . doi : 10.1093 / bjps / axn031 .
- ^ HT Siegelmann (abril de 1995). "Cálculo más allá del límite de Turing" (PDF) . Ciencia . 268 (5210): 545–548. Código bibliográfico : 1995Sci ... 268..545S . doi : 10.1126 / science.268.5210.545 . PMID 17756722 .
- ^ Hava Siegelmann ; Eduardo Sontag (1994). "Computación analógica a través de redes neuronales" . Informática Teórica . 131 (2): 331–360. doi : 10.1016 / 0304-3975 (94) 90178-3 .
- ^ PD Welch (2009). "Características de los modelos de máquina de Turing de tiempo transfinito discreto: tiempos de parada, tiempos de estabilización y teoremas de forma normal" . Informática Teórica . 410 (4–5): 426–442. doi : 10.1016 / j.tcs.2008.09.050 .
- ^ Davis, Martín (2006). "Por qué no existe una disciplina como la hipercomputación". Matemática Aplicada y Computación . 178 (1): 4–7. doi : 10.1016 / j.amc.2005.09.066 .
- ^ Davis, Martín (2004). "El mito de la hipercomputación". Alan Turing: vida y legado de un gran pensador . Saltador.
- ^ Martin Davis (enero de 2003). "El mito de la hipercomputación". En Alexandra Shlapentokh (ed.). Mini taller: Décimo problema de Hilbert, Conjetura de Mazur y Secuencias de divisibilidad (PDF) . Informe MFO. 3 . Mathematisches Forschungsinstitut Oberwolfach. pag. 2.
Otras lecturas
- Mario Antoine Aoun, " Avances en tres modelos de hipercomputación ", (2016)
- L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation , Springer-Verlag 1997. Desarrollo general de la teoría de la complejidad para máquinas abstractas que calculan en números reales en lugar de bits.
- Burgin, MS (1983) Inductive Turing Machines, Avisos de la Academia de Ciencias de la URSS , v. 270, núm. 6, págs. 1289-1293
- Keith Douglas. Computación de Super-Turing: un análisis de estudio de caso ( PDF ), Tesis de maestría, Universidad Carnegie Mellon, 2003.
- Mark Burgin (2005), Algoritmos superrecursivos , Monografías en informática, Springer. ISBN 0-387-95569-0
- Cockshott, P. y Michaelson, G. ¿Existen nuevos modelos de computación? Respuesta a Wegner y Eberbach, The computer Journal , 2007
- Cooper, SB (2006). "Definibilidad como efecto hipercomputacional" (PDF) . Matemática Aplicada y Computación . 178 : 72–82. CiteSeerX 10.1.1.65.4088 . doi : 10.1016 / j.amc.2005.09.072 . Archivado desde el original (PDF) el 24 de julio de 2011 . Consultado el 16 de junio de 2011 .
- Cooper, SB; Odifreddi, P. (2003). "Incomputabilidad en la naturaleza" (PDF) . En SB Cooper; SS Goncharov (eds.). Computabilidad y modelos: perspectivas de Oriente y Occidente . Plenum Publishers, Nueva York, Boston, Dordrecht, Londres, Moscú. págs. 137-160.
- Copeland, J. (2002) Hipercomputación , Mentes y máquinas, v. 12, págs. 461–502
- Davis, Martin (2006), " The Church-Turing Thesis: Consenso y oposición ". Proceedings, Computability in Europe 2006. La URL solicitada /~simon/TEACH/28000/DavisUniversal.pdf no se encontró en este servidor. Lecture Notes in Computer Science, 3988 págs. 125-132
- Hagar, A. y Korolev, A., Hipercomputación cuántica: ¿bombo o computación? , (2007)
- Müller, Vincent C. (2011). "Sobre las posibilidades de las supertareas de hipercomputación" . Mentes y Máquinas . 21 (1): 83–96. CiteSeerX 10.1.1.225.3696 . doi : 10.1007 / s11023-011-9222-6 .
- Ord, Toby. Hipercomputación: calcular más de lo que la máquina de Turing puede calcular : artículo de una encuesta sobre diversas formas de hipercomputación.
- Piccinini , Gualtiero : Computación en sistemas físicos
- Putz, Volkmar y Karl Svozil, ¿Se puede "empujar" una computadora para que funcione más rápido que la luz? , (2010)
- Rogers, H. (1987) Teoría de funciones recursivas y computabilidad efectiva, MIT Press, Cambridge Massachusetts
- Mike Stannett, Mike (1990). "X-máquinas y el problema de la detención: la construcción de una súper máquina de Turing". Aspectos formales de la informática . 2 (1): 331–341. doi : 10.1007 / BF01888233 .
- Mike Stannett , The case for hypercomputation , Applied Mathematics and Computation, Volumen 178, Número 1, 1 de julio de 2006, Páginas 8-24, Número especial sobre hipercomputación
- Syropoulos, Apostolos (2008), Hipercomputación: Computación más allá de la barrera de Turing de la Iglesia ( vista previa ), Springer. ISBN 978-0-387-30886-9
- Turing, Alan (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 .
enlaces externos
- Red de investigación de hipercomputación