Hipercomputación

Ajustar Compartir Imprimir Citar

Modelos de cálculo que proporcionan productos que no son compatibles con Turing

Hipercomputación o supercomputación de Turing se refiere a modelos de computación que pueden proporcionar resultados que no son computables por Turing. La computación de Super-Turing, introducida a principios de la década de 1990 por Hava Siegelmann, se refiere a dicha computación realizable biológica, física y de inspiración neurológica; Se convirtió en la base matemática del aprendizaje automático permanente. Se dice que la hipercomputación, introducida como un campo de la ciencia a fines de la década de 1990, se basa en el super-Turing, pero también incluye construcciones que son filosóficas. 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 "computable" función que puede 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 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.

Historia

Un modelo computacional que va más allá de las máquinas de Turing fue presentado por Alan Turing en su tesis doctoral de 1938 Sistemas de lógica basados en ordinales. Este artículo investigó los 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 del oráculo de Turing son abstracciones matemáticas y no son físicamente realizables.

Espacio de estados

En cierto sentido, la mayoría de las funciones son incomputables: hay $aleph _{0}$ funciones computables, pero hay un número incontable ( $2^{aleph _{0}}$ ) de posibles funciones super-Turing.

Modelos

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 de Turing aleatoria).

Entradas no computables o componentes de caja negra

Un sistema que otorga el conocimiento de la constante incomputable y oracular de Chaitin (un número con una secuencia infinita de dígitos que codifican la solución al problema de detención) como entrada puede resolver una gran cantidad de problemas indecidibles útiles; un sistema al que se le otorgó un generador de números aleatorios no computables como entrada puede crear funciones aleatorias no computables, pero en general no se cree que pueda resolver de manera significativa problemas "útiles" funciones no computables como el problema de la detención. Hay un número ilimitado de diferentes tipos de hipercomputadoras concebibles, que incluyen:

Las máquinas oráculo originales de Turing, definidas por Turing en 1939.
Una computadora real (una especie de computadora analógica idealizada) puede realizar hipercomputación si la física admite variables reales generales (no sólo reales computables), y éstas son de alguna manera "hábil" para computación útil (en vez de azar). Esto podría requerir leyes bastante extrañas de la física (por ejemplo, una constante física mensurable con un valor oracular, como la constante de Chaitin), y requeriría la capacidad de medir el valor físico real a la precisión arbitraria, aunque la física estándar hace tales mediciones de precisión arbitraria teóricamente infeibles.
- Del mismo modo, una red neuronal que de alguna manera tenía la constante de Chaitin incrustada exactamente en su función de peso sería capaz de resolver el problema de detener, pero está sujeta a las mismas dificultades físicas que otros modelos de hipercomputación basados en la computación real.
Ciertas "máquinas de Turing con lógica borrosa" pueden, por definición, resolver accidentalmente el problema de detenimiento, pero sólo porque su capacidad para resolver el problema de detenimiento se asume indirectamente en la especificación de la máquina; esto tiende a ser visto como un "bug" en la especificación original de las máquinas.
- Análogamente, un modelo propuesto conocido como el nodeterminismo justo puede permitir accidentalmente la computación oracular de funciones no compatibles, ya que algunos de estos sistemas, por definición, tienen la capacidad oracular de identificar los insumos rechazados que "injustamente" causan que un subsistema funcione para siempre.
Dmytro Taranovsky ha propuesto un modelo finitario de ramas de análisis tradicionalmente no-finitistas, construido alrededor de una máquina de Turing equipada con una función de rápido aumento como su oráculo. Por esto y modelos más complicados pudo dar una interpretación de la aritmética de segundo orden. Estos modelos requieren una entrada incomputable, como un proceso físico de generación de eventos donde el intervalo entre eventos crece a un ritmo incomputablemente grande.
- Del mismo modo, una interpretación no ortodoxa de un modelo de no determinación sin límites plantea, por definición, que la duración del tiempo requerido para que un "Actor" se resuelva es fundamentalmente inconocible, y por lo tanto no se puede probar, dentro del modelo, que no toma un período de tiempo incontestablemente largo.

"Pasos computacionales infinitos" modelos

Para que funcionen correctamente, ciertos cálculos realizados por las máquinas a continuación literalmente requieren espacio físico y recursos infinitos, en lugar de meramente ilimitados pero finitos; en contraste, con una máquina de Turing, cualquier cálculo dado que se detenga requerirá solo un espacio físico y recursos finitos.

Una máquina de Turing que puede completo infinitamente muchos pasos en tiempo finito, una hazaña conocida como una supertasca. Simplemente poder correr por un número ilimitado de pasos no basta. Un modelo matemático es la máquina Zeno (inspirada por la paradoja de Zeno). La máquina Zeno realiza su primer paso de computación en (diga) 1 minuto, el segundo paso en 1⁄2 minuto, el tercer paso en 1⁄4 minuto, etc. Al resumir 1+1⁄2+1⁄4+... (una serie geométrica) vemos que la máquina realiza infinitamente muchos 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 de un lado período abierto de [0, 2), por lo que no se define exactamente a 2 minutos después del comienzo de la computación.

Parece natural que la posibilidad de viajar en el tiempo (existencia de curvas cerradas (CTCs)) 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 un cálculo infinito requeriría. No obstante, existen tiempos espaciales en que la región del CTC puede utilizarse para la hipercomputación relativista. Según un documento de 1992, una computadora que operaba en un espacio Malament – Hogarth o en órbita alrededor de un agujero negro giratorio podía realizar teóricamente computaciones no-Turing para un observador dentro del agujero negro. El acceso a un CTC puede permitir la solución rápida a los problemas completos de PSPACE, una clase de complejidad que, mientras Turing-decidable, generalmente se considera computacionalmente intráctil.

Modelos cuánticos

Algunos académicos conjeturan que un sistema mecánico cuántico que de alguna manera usa una superposición infinita de estados podría calcular una función no computable. Esto no es posible usando la computadora cuántica modelo qubit estándar, porque está probado que una computadora cuántica normal es reducible por PSPACE (una computadora cuántica que se ejecuta en tiempo polinomial puede simularse con una computadora clásica que se ejecuta en espacio polinomial).

"Eventualmente correcto" sistemas

Algunos sistemas físicamente realizables eventualmente siempre convergerán en la respuesta correcta, pero tienen el defecto de que a menudo generarán una respuesta incorrecta y se quedarán con la respuesta incorrecta durante un período de tiempo incomputablemente largo antes de regresar y corregir el error.

A mediados de la década de 1960, E Mark Gold y Hilary Putnam propusieron de forma independiente modelos de inferencia inductiva (las "funcionalidades recursivas limitadas" y "predeterminados del juicio y el terrorismo", respectivamente). Estos modelos permiten que algunos conjuntos no recursivos de números o idiomas (incluidos todos los conjuntos repetidamente enumerables de idiomas) sean "apretados en el límite"; mientras que, por definición, sólo los números o idiomas recursivos podrían ser identificados por una máquina de Turing. Mientras que la máquina se estabilizará a la respuesta correcta en cualquier conjunto aprendiz en algún tiempo finito, sólo puede identificarla como correcta si es recursiva; de lo contrario, la corrección se establece sólo por ejecutar la máquina para siempre y notando que nunca revisa su respuesta. Putnam identificó esta nueva interpretación como la clase de predicados "empíricos", afirmando: "si siempre 'posit' que la respuesta más recientemente generada es correcta, haremos un número finito de errores, pero eventualmente conseguiremos la respuesta correcta. (Nota, sin embargo, que incluso si hemos llegado a la respuesta correcta (el final de la secuencia finita) nunca somos Seguro. que tenemos la respuesta correcta.)" El documento de L. K. Schubert de 1974 "Recusión de Limitación Iterada y el Problema de Minimización del Programa" estudió los efectos de la iteración del procedimiento de limitación; esto permite que cualquier predicado aritmético sea computado. Schubert escribió: "Intuitivamente, la identificación limitada iterada podría considerarse como una inferencia inductiva de mayor orden realizada colectivamente por una comunidad cada vez mayor de máquinas de inferencia inductiva de menor orden".
Una secuencia de símbolo es computable en el límite si hay un programa finito, posiblemente no-halador en una máquina de Turing universal que produce gradualmente cada símbolo de la secuencia. Esto incluye la expansión dyadic de π y de cada otro real computable, pero aún excluye todos los reales no computacionales. Las 'Máquinas de Turing Monotone' utilizadas tradicionalmente en la teoría del tamaño de la descripción no pueden editar sus salidas anteriores; máquinas de Turing generalizadas, según define Jürgen Schmidhuber, puede. Él define las secuencias de símbolos constructivamente descriptibles como aquellas que tienen un programa finito y no-halador funcionando en una máquina de Turing generalizada, de tal manera 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 expuestas por Kurt Gödel (1931), puede ser imposible predecir el tiempo de convergencia en sí mismo por un programa de cesación, de lo contrario el problema de suspensión podría resolverse. Schmidhuber () utiliza este enfoque para definir el conjunto de universos formalmente descriptibles o constructivamente computables o teorías constructivas de todo. Las máquinas de Turing generalizadas pueden eventualmente converger a una solución correcta del problema de parar evaluando una secuencia de Specker.

Análisis de capacidades

Muchas propuestas de hipercomputación equivalen a formas alternativas para leer una función de oráculo o consejo incrustada en una máquina de otra manera clásica. Otros permiten el acceso a algún nivel superior de la jerarquía aritmética. Por ejemplo, las máquinas de supertasking Turing, bajo las suposiciones habituales, serían capaces de calcular cualquier predicado en el grado de veracidad que contenga $Sigma _{1}^{0}$ o $Pi _{1}^{0}$ . Limitar-recusión, por contraste, puede calcular cualquier predicado o función en el correspondiente grado de Turing, que se sabe que $Delta _{2}^{0}$ . El oro mostró además que limitar la recursión parcial permitiría la computación de precisamente el $Sigma _{2}^{0}$ predicados.

Modelo	predicados complejos	Notas
supertasking	tt( $Sigma _{1}^{0},Pi _{1}^{0}$ )	dependiente de observadores externos
limiting/trial-and-error	$Delta _{2}^{0}$
límite iterado (k veces)	$Delta _{k+1}^{0}$
Blum–Shub–Máquina masculina		incomparable con las funciones reales computables tradicionales
Malament–Hogarth spacetime	HYP	dependiente de la estructura espacial
red neuronal analógica	$Delta _{1}^{0}[f]$	f es una función de asesoramiento que da pesos de conexión; el tamaño está ligado por el tiempo de ejecución
Tiempo infinito Máquina de Turing	${displaystyle AQI}$	Conjuntos Aritmetical Quasi-Inductive
clásico fuzzy Máquina de tortuga	$Sigma _{1}^{0}cup Pi _{1}^{0}$	para cualquier t-norm computable
función creciente oráculo	$Delta _{1}^{1}$	para el modelo de una secuencia; $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 contraargumentos a la realizabilidad física de la hipercomputación. En cuanto a su teoría, argumenta en contra las afirmaciones de que este es un campo nuevo fundado en la década de 1990. Este punto de vista se basa sobre 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 un comentario de que toda la hipercomputación es poco más que: "si se permiten entradas no computables, entonces se pueden obtener salidas no computables."