Hipercomputación - Hypercomputation

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.

Historia

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 . 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 físicamente realizables.

Espacio de Estados

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.

Modelos

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

Entradas incomputables o componentes de caja negra

Un sistema al que se le concede el conocimiento de la constante oracular de Chaitin (un número con una secuencia infinita de dígitos que codifica la solución al problema que se detiene) como entrada puede resolver una gran cantidad de problemas indecidibles útiles; un sistema al que se le ha concedido un generador de números aleatorios no computable como entrada puede crear funciones aleatorias no computables, pero generalmente no se cree que sea capaz de resolver de manera significativa funciones no computables "útiles" como el problema de la detención. Hay un número ilimitado de diferentes tipos de hipercomputadoras imaginables, que incluyen:

  • Las máquinas de 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 solo reales computables ), y estas son de alguna manera "adaptables" para cálculos útiles (en lugar de aleatorios). Esto podría requerir leyes de la física bastante extrañas (por ejemplo, una constante física medible con un valor oracular, como la constante de Chaitin ), y requeriría la capacidad de medir el valor físico real con precisión arbitraria, aunque la física estándar hace que tales valores sean arbitrarios. -medidas de precisión teóricamente inviables.
    • De manera similar, una red neuronal que de alguna manera tuviera la constante de Chaitin incrustada exactamente en su función de peso podría resolver el problema de la detención, pero está sujeta a las mismas dificultades físicas que otros modelos de hipercomputación basados ​​en computación real.
  • Ciertas "máquinas de Turing difusas" basadas en lógica difusa pueden, por definición, resolver accidentalmente el problema de la detención, pero sólo porque su capacidad para resolver el problema de la detención se asume indirectamente en la especificación de la máquina; esto tiende a verse como un "error" en la especificación original de las máquinas.
    • De manera similar, un modelo propuesto conocido como no determinismo justo puede permitir accidentalmente el cálculo oracular de funciones no computables, porque algunos de estos sistemas, por definición, tienen la capacidad oracular de identificar entradas de rechazo que causarían "injustamente" que un subsistema se ejecute para siempre.
  • Dmytro Taranovsky ha propuesto un finitista modelo de ramas tradicionalmente no finitistas de análisis, construido alrededor de una máquina de Turing equipado con una función rápidamente creciente como su oráculo. Mediante este y otros modelos más complicados pudo dar una interpretación de la aritmética de segundo orden. Estos modelos requieren una entrada incontestable, como un proceso de generación de eventos físicos donde el intervalo entre eventos crece a un ritmo increíblemente grande.
    • De manera similar, una interpretación poco ortodoxa de un modelo de no determinismo ilimitado postula, por definición, que el período de tiempo requerido para que un "actor" se establezca es fundamentalmente incognoscible y, por lo tanto, no se puede probar, dentro del modelo, que no se necesita un período de tiempo incontestablemente largo.

Modelos de "pasos computacionales infinitos"

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

  • Una máquina de Turing que puede completar un número infinito de pasos en un tiempo finito, una hazaña conocida como supertarea . El simple hecho de poder ejecutar una cantidad ilimitada de pasos no es suficiente. Un modelo matemático es la máquina de Zeno (inspirada en la paradoja de Zeno ). La máquina Zeno realiza su primer paso de cálculo en (digamos) 1 minuto, el segundo paso en ½ minuto, el tercer paso en ¼ de minuto, etc. Al sumar 1 + ½ + ¼ + ... (una serie geométrica ) vemos que la máquina realiza una infinidad de 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 del período abierto de un lado de [0, 2), por lo tanto indefinido exactamente 2 minutos después del comienzo del cálculo.
  • Parece natural que la posibilidad de viajar en el tiempo (existencia de curvas temporales cerradas (CTC)) 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 requeriría un cálculo infinito. Sin embargo, hay espaciotiempos en los que la región CTC se puede utilizar para hipercomputación relativista. Según un artículo de 1992, una computadora que opera en un espacio-tiempo de Malament-Hogarth o en órbita alrededor de un agujero negro en rotación podría, teóricamente, realizar cálculos que no sean de Turing para un observador dentro del agujero negro. El acceso a un CTC puede permitir la solución rápida a problemas completos de PSPACE , una clase de complejidad que, aunque Turing-decidible, generalmente se considera intratable desde el punto de vista computacional.

Modelos cuánticos

Algunos estudiosos conjeturan que un sistema de mecánica cuántica que de alguna manera utiliza una superposición infinita de estados podría calcular una función no computable . Esto no es posible con el estándar qubit -model ordenador cuántico , porque está comprobado que un ordenador cuántico regular es PSPACE reducible (un ordenador cuántico que se ejecuta en tiempo polinómico se puede simular un ordenador clásico que se ejecuta en el espacio polinomio ).

Sistemas "eventualmente correctos"

Algunos sistemas físicamente realizables siempre convergerán eventualmente hacia la respuesta correcta, pero tienen el defecto de que a menudo darán una respuesta incorrecta y se quedarán con la respuesta incorrecta durante un período de tiempo incontestablemente grande antes de eventualmente volver atrás 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 (los "funcionales recursivos limitantes" y los "predicados de prueba y error", respectivamente). Estos modelos permiten que algunos conjuntos no recursivos de números o idiomas (incluidos todos los conjuntos de idiomas recursivamente enumerables ) se "aprendan en el límite"; mientras que, por definición, una máquina de Turing sólo podría identificar conjuntos recursivos de números o idiomas. Si bien la máquina se estabilizará con la respuesta correcta en cualquier conjunto que se pueda aprender en un tiempo finito, solo puede identificarla como correcta si es recursiva; de lo contrario, la corrección se establece solo ejecutando la máquina para siempre y observando que nunca revisa su respuesta. Putnam identificó esta nueva interpretación como la clase de predicados "empíricos", afirmando: "si siempre 'postulamos' que la respuesta generada más recientemente es correcta, cometeremos un número finito de errores, pero eventualmente obtendremos la respuesta correcta. (Tenga en cuenta, sin embargo, que incluso si hemos llegado a la respuesta correcta (el final de la secuencia finita), nunca estamos seguros de tener la respuesta correcta). " Artículo de 1974 de LK Schubert " Iterated Limiting Recursion and the Program Minimization Problema "estudió los efectos de iterar el procedimiento de limitación; esto permite calcular cualquier predicado aritmético . Schubert escribió: "Intuitivamente, la identificación limitante iterada podría considerarse como una inferencia inductiva de orden superior realizada colectivamente por una comunidad cada vez mayor de máquinas de inferencia inductiva de orden inferior".
  • Una secuencia de símbolos se puede calcular en el límite si hay un programa finito, posiblemente sin interrupciones, en una máquina universal de Turing que genere cada símbolo de la secuencia de forma incremental. Esto incluye la expansión diádica de π y de todos los demás reales computables , pero aún excluye todos los reales no computables. Las 'máquinas monótonas de Turing' utilizadas tradicionalmente en la teoría del tamaño de la descripción no pueden editar sus resultados anteriores; Máquinas de Turing generalizadas, según la definición de Jürgen Schmidhuber , can. Define las secuencias de símbolos que se pueden describir de forma constructiva como aquellas que tienen un programa finito que no se detiene ejecutándose en una máquina de Turing generalizada, de modo 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 mostradas por primera vez por Kurt Gödel (1931), puede ser imposible predecir el tiempo de convergencia en sí mismo mediante un programa de detención, de lo contrario, el problema de la detención podría resolverse. Schmidhuber () usa este enfoque para definir el conjunto de universos formalmente describibles o constructivamente computables o teorías constructivas de todo . Las máquinas de Turing generalizadas pueden eventualmente converger hacia una solución correcta del problema de detención mediante la evaluación de una secuencia de Specker .

Análisis de capacidades

Muchas propuestas de hipercomputación equivalen a formas alternativas de leer un oráculo o una función de consejo incrustada en una máquina clásica. Otros permiten el acceso a un nivel superior de la jerarquía aritmética . Por ejemplo, las máquinas de Turing de supertarea, bajo los supuestos habituales, podrían calcular cualquier predicado en el grado de la tabla de verdad que contenga o . La recursividad limitante, por el contrario, puede calcular cualquier predicado o función en el grado de Turing correspondiente , que se sabe que es . Gold mostró además que limitar la recursividad parcial permitiría el cálculo de los predicados con precisión .

Modelo Predicados computables Notas Refs
super pregunta tt ( ) dependiente del observador externo
limitación / ensayo y error
limitación iterada ( k veces)
Máquina Blum – Shub – Smale incomparable con las funciones reales computables tradicionales
Espacio-tiempo de Malament – ​​Hogarth HYP dependiente de la estructura del espacio-tiempo
red neuronal recurrente analógica f es una función de aviso que proporciona pesos de conexión; el tamaño está limitado por el tiempo de ejecución
máquina de Turing de tiempo infinito Conjuntos aritméticos cuasi-inductivos
máquina de Turing borrosa clásica para cualquier norma t computable
aumento de la función de oráculo para el modelo de una secuencia; son re

Crítica

Martin Davis , en sus escritos sobre hipercomputación, se refiere a este tema como "un mito" y ofrece argumentos en contra de la realizabilidad física de la hipercomputación. En cuanto a su teoría, argumenta en contra de las afirmaciones de que este es 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 mencionó anteriormente. En su argumento, hace una observación de que toda la hipercomputación es poco más que: " si se permiten entradas no computables, entonces se pueden obtener salidas no computables " .

Ver también

Referencias

Otras lecturas

enlaces externos