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. 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.

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 ${\mathrm{\Sigma }}_1^0$ o ${\mathrm{\Pi }}_1^0$. 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 ${\mathrm{\Delta }}_2^0$. Gold demostró además que la recursividad parcial limitadora permitiría calcular precisamente el grado de ${\mathrm{\Sigma }}_2^0$ predicados.

Modelo	Predicados computables	Notas	Refs
supertarea	$\mathrm{tt}({\mathrm{\Sigma }}_1^0,{\mathrm{\Pi }}_1^0)$	depende de un observador externo
limitación/juicio-y-error	${\mathrm{\Delta }}_2^0$
limitación iterada (k veces)	${\mathrm{\Delta }}_{k+1}^0$
Máquina Blum-Shub-Smale		incomparables con las funciones reales computables tradicionales
Espaciotiempo Malament-Hogarth	HYP	depende de la estructura del espaciotiempo
red neuronal recurrente analógica	${\mathrm{\Delta }}_1^0[f]$	f es una función de asesoramiento que da pesos de conexión; el tamaño está limitado por el tiempo de ejecución
máquina de Turing de tiempo infinito	$AQI$	Conjuntos aritméticos cuasi inductivos
máquina de Turing difusa clásica	${\mathrm{\Sigma }}_1^0\cup {\mathrm{\Pi }}_1^0$	para cualquier t-norma computable
oráculo de función creciente	${\mathrm{\Delta }}_1^1$	para el modelo de una secuencia; ${\mathrm{\Pi }}_1^1$ son r.e.

Crítica

Martin Davis, en sus escritos sobre hipercomputación, 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».

Véase también

• Máquina de Turing
• Función computable
• Teoría de la computabilidad