Hipercomputación
La hipercomputación o supercomputación de Turing es un conjunto de modelos de computación que pueden proporcionar resultados que no son Turing-computables. Por ejemplo, una máquina capaz de resolver el problema de la parada sería un hiperordenador; 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 sencillos, puede ser calculada por una máquina de Turing. Los hiperordenadores computan funciones que una máquina de Turing no puede y que, por tanto, no son computables en el sentido de Church-Turing.
Técnicamente, la salida de una máquina de Turing aleatoria no es computable; sin embargo, la mayor parte de la literatura sobre hipercomputación se centra en el cálculo de funciones deterministas no aleatorias no computables.
Historia
Alan Turing introdujo un modelo computacional que iba más allá de las máquinas de Turing en su tesis doctoral de 1938 Systems of Logic Based on Ordinals.[1] Este trabajo investigaba 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. Utilizó este dispositivo para demostrar que, incluso en esos sistemas más potentes, la indecidibilidad sigue presente. Las máquinas de oráculo de Turing son abstracciones matemáticas y no son físicamente realizables.[2]
Modelos
Muchas propuestas de hipercomputación consisten en formas alternativas de leer un oráculo o una función de asesoramiento integrada en una máquina clásica. Otras permiten acceder a algún nivel superior de la jerarquía aritmética. Por ejemplo, las máquinas de Turing supertarea, bajo los supuestos habituales, serían capaces de calcular cualquier predicado en el grado de la tabla de verdad que contenga o . La excursión limitadora, 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 la recursividad parcial limitadora permitiría calcular precisamente el grado de predicados.
Modelo | Predicados computables | Notas | Refs |
---|---|---|---|
supertarea | depende de un observador externo | [3] | |
limitación/juicio-y-error | [4][5] | ||
limitación iterada (k veces) | [6] | ||
Máquina Blum-Shub-Smale | incomparables con las funciones reales computables tradicionales | [7] | |
Espaciotiempo Malament-Hogarth | HYP | depende de la estructura del espaciotiempo | [8] |
red neuronal recurrente analógica | f es una función de asesoramiento que da pesos de conexión; el tamaño está limitado por el tiempo de ejecución | [9][10] | |
máquina de Turing de tiempo infinito | Conjuntos aritméticos cuasi inductivos | [11] | |
máquina de Turing difusa clásica | para cualquier t-norma computable | [12] | |
oráculo de función creciente | para el modelo de una secuencia; son r.e. | [13] |
Crítica
Martin Davis, en sus escritos sobre hipercomputación,[14] se refiere a este tema como «un mito» y ofrece argumentos contrarios a la realizabilidad física de la hipercomputación. En cuanto a su teoría, se opone a las afirmaciones de que se trata de un nuevo campo 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 ha mencionado anteriormente. En su argumentación, hace la observación de que toda hipercomputabilidad es poco más que: «si se permiten entradas no computables, entonces son alcanzables salidas no computables».[15]
Véase también
Referencias
- ↑ Turing, A. M. (1939). «Systems of Logic Based on Ordinals†». Proceedings of the London Mathematical Society (en inglés) 45: 161-228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
- ↑ Turing, A. M. (1938). Systems of Logic Based On Ordinals. p. 167. «Supongamos que disponemos de un medio indeterminado para resolver problemas de teoría de números, una especie de oráculo. No profundizaremos más en la naturaleza de este oráculo, aparte de decir que no puede ser una máquina».
- ↑ Petrus H. Potgieter (Julio de 2006). «Zeno machines and hypercomputation». Theoretical Computer Science (en inglés) 358 (1): 23-33. S2CID 6749770. arXiv:cs/0412022. doi:10.1016/j.tcs.2005.11.040.
- ↑ E. M. Gold (1965). «Limiting Recursion». Journal of Symbolic Logic (en inglés) 30 (1): 28-48. JSTOR 2270580. S2CID 33811657. doi:10.2307/2270580. , E. Mark Gold (1967). «Language identification in the limit». Information and Control (en inglés) 10 (5): 447-474. doi:10.1016/S0019-9958(67)91165-5.
- ↑ E. Mark Gold (1967). «Language identification in the limit». Information and Control (en inglés) 10 (5): 447-474. doi:10.1016/S0019-9958(67)91165-5.
- ↑ L. K. Schubert (Julio de 1974). «Iterated Limiting Recursion and the Program Minimization Problem». Journal of the ACM (en inglés) 21 (3): 436-445. S2CID 2071951. doi:10.1145/321832.321841.
- ↑ Lenore, Blum; Felipe, Cuckel; Michael, Shub & Stephen, Smale (1998). Complexity and Real Computation (en inglés). Springer. ISBN 978-0-387-98281-6.
- ↑ P.D. Welch (2008). «The extent of computation in Malament-Hogarth spacetimes». British Journal for the Philosophy of Science (en inglés) 59 (4): 659-674. arXiv:gr-qc/0609035. doi:10.1093/bjps/axn031.
- ↑ H.T. Siegelmann (Apr 1995). «Computation Beyond the Turing Limit». Science (en inglés) 268 (5210): 545-548. Bibcode:1995Sci...268..545S. PMID 17756722. S2CID 17495161. doi:10.1126/science.268.5210.545.
- ↑ Hava Siegelmann; Eduardo Sontag (1994). «Analog Computation via Neural Networks». Theoretical Computer Science (en inglés) 131 (2): 331-360. doi:10.1016/0304-3975(94)90178-3.
- ↑ P.D. Welch (2009). «Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems». Theoretical Computer Science (en inglés) 410 (4–5): 426-442. doi:10.1016/j.tcs.2008.09.050.
- ↑ Wiedermann, Jiří (2004). «Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines». Theoretical Computer Science (en inglés) 317 (1–3): 61-69. doi:10.1016/j.tcs.2003.12.004. «Su (capacidad de resolver el problema de detención) se debe a su criterio de aceptación en el que se asume indirectamente la capacidad de resolver el problema de detención.»
- ↑ Dmytro Taranovsky (17 de julio de 2005). «Finitism and Hypercomputation» (en inglés).
- ↑ Davis, Martin (2006). «Why there is no such discipline as hypercomputation». Applied Mathematics and Computation (en inglés) 178 (1): 4-7. doi:10.1016/j.amc.2005.09.066.
- ↑ Martin Davis (Enero de 2003). «The Myth of Hypercomputation». En Alexandra Shlapentokh, ed. Miniworkshop: Hilbert's Tenth Problem, Mazur's Conjecture and Divisibility Sequences. MFO Report (en inglés) 3. Mathematisches Forschungsinstitut Oberwolfach. p. 2.
Datos: Q2661997