Hipercomputación
La hipercomputación o la 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 pudiera resolver el problema de la detención sería una hipercomputadora; también lo haría uno que pueda evaluar correctamente cada declaración en la aritmética de Peano .
La tesis de Church-Turing establece que cualquier función "computable" que pueda calcular un matemático con lápiz y papel utilizando un conjunto finito de algoritmos simples, puede calcularse con 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 no es computable; sin embargo, la mayor parte de la literatura sobre hipercomputación se centra en cambio en el cálculo de funciones no computables deterministas, en lugar de aleatorias.
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ó los sistemas matemáticos en los que se disponía de un oráculo que podía calcular una sola 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 del oráculo de Turing son abstracciones matemáticas y no son físicamente realizables. [2]
En cierto sentido, la mayoría de las funciones no son computables: 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 Oracle originales de Turing), hasta generadores de funciones aleatorias menos útiles que son más plausiblemente "realizables" (como una máquina aleatoria de Turing ).