Hipercomputación
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 todos los enunciados de 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.
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]
En cierto sentido, la mayoría de las funciones no se pueden calcular: hay funciones computables, pero hay un número incontable ( ) de posibles funciones de Super-Turing. [3]
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 ).