Algoritmo superrecursivo - Super-recursive algorithm

En la teoría de la computabilidad , los algoritmos superrecursivos son una generalización de los algoritmos ordinarios que son más poderosos, es decir, calculan más que las máquinas de Turing . El término fue introducido por Mark Burgin, cuyo libro "Algoritmos superrecursivos" desarrolla su teoría y presenta varios modelos matemáticos. Las máquinas de Turing y otros modelos matemáticos de algoritmos convencionales permiten a los investigadores encontrar propiedades de algoritmos recursivos y sus cálculos. De manera similar, los modelos matemáticos de algoritmos súper recursivos, como las máquinas de Turing inductivas , permiten a los investigadores encontrar propiedades de algoritmos súper recursivos y sus cálculos.

Burgin, así como otros investigadores (incluidos Selim Akl , Eugene Eberbach, Peter Kugel, Jan van Leeuwen , Hava Siegelmann , Peter Wegner y Jiří Wiedermann) que estudiaron diferentes tipos de algoritmos superrecursivos y contribuyeron a la teoría de los superrecursivos. algoritmos, han argumentado que los algoritmos superrecursivos pueden usarse para refutar la tesis de Church-Turing , pero este punto de vista ha sido criticado dentro de la comunidad matemática y no es ampliamente aceptado.

Definición

Burgin (2005: 13) usa el término algoritmos recursivos para los algoritmos que se pueden implementar en máquinas de Turing, y usa la palabra algoritmo en un sentido más general. Entonces, una clase de algoritmos superrecursivos es "una clase de algoritmos en los que es posible calcular funciones que ninguna máquina de Turing puede calcular " (Burgin 2005: 107).

Los algoritmos superrecursivos están estrechamente relacionados con la hipercomputación de una manera similar a la relación entre la computación ordinaria y los algoritmos ordinarios. La computación es un proceso, mientras que un algoritmo es una descripción constructiva finita de dicho proceso. Por tanto, un algoritmo superrecursivo define un "proceso computacional (incluidos los procesos de entrada y salida) que no puede realizarse mediante algoritmos recursivos". (Burgin 2005: 108). Una definición más restringida exige que la hipercomputación resuelva una supertarea (ver Copeland 2002; Hagar y Korolev 2007).

Los algoritmos superrecursivos también están relacionados con esquemas algorítmicos , que son más generales que los algoritmos superrecursivos. Burgin sostiene (2005: 115) que es necesario hacer una distinción clara entre algoritmos superrecursivos y aquellos esquemas algorítmicos que no son algoritmos. Bajo esta distinción, algunos tipos de hipercomputación se obtienen mediante algoritmos superrecursivos, por ejemplo, máquinas de Turing inductivas, mientras que otros tipos de hipercomputación son dirigidos por esquemas algorítmicos, por ejemplo, máquinas de Turing de tiempo infinito. Esto explica cómo los trabajos en algoritmos superrecursivos están relacionados con la hipercomputación y viceversa. Según este argumento, los algoritmos superrecursivos son solo una forma de definir un proceso hipercomputacional.

Ejemplos de

Los ejemplos de algoritmos superrecursivos incluyen (Burgin 2005: 132):

  • limitar las funciones recursivas y limitar las funciones recursivas parciales (EM Gold 1965)
  • predicados de prueba y error (Hilary Putnam 1965)
  • máquinas de inferencia inductiva (Carl Smith)
  • máquinas de Turing inductivas , que realizan cálculos similares a los cálculos de las máquinas de Turing y producen sus resultados después de un número finito de pasos (Mark Burgin)
  • limitar las máquinas de Turing , que realizan cálculos similares a los cálculos de las máquinas de Turing, pero sus resultados finales son límites de sus resultados intermedios (Mark Burgin)
  • máquinas de prueba y error (Ja. Hintikka y A. Mutanen 1998)
  • Máquinas de Turing en general (J. Schmidhuber)
  • Máquinas de Internet ( van Leeuwen, J. y Wiedermann, J.)
  • Computadoras evolutivas , que usan ADN para producir el valor de una función (Darko Roglic)
  • cálculo difuso (Jirí Wiedermann 2004)
  • máquinas de Turing evolutivas (Eugene Eberbach 2005)

Los ejemplos de esquemas algorítmicos incluyen:

  • Máquinas de Turing con oráculos arbitrarios (Alan Turing)
  • Operadores transrecursivos (Borodyanskii y Burgin)
  • máquinas que calculan con números reales (L. Blum, F. Cucker, M. Shub y S. Smale 1998)
  • redes neuronales basadas en números reales (Hava Siegelmann 1999)

Para obtener ejemplos de algoritmos superrecursivos prácticos , consulte el libro de Burgin.

Máquinas inductivas de Turing

Las máquinas de Turing inductivas implementan una clase importante de algoritmos superrecursivos. Una máquina de Turing inductiva es una lista definida de instrucciones bien definidas para completar una tarea que, cuando se le da un estado inicial, procederá a través de una serie bien definida de estados sucesivos, dando finalmente el resultado final. La diferencia entre una máquina de Turing inductiva y una máquina de Turing ordinaria es que una máquina de Turing normal debe detenerse cuando ha obtenido su resultado, mientras que en algunos casos una máquina de Turing inductiva puede continuar calculando después de obtener el resultado, sin detenerse. Kleene llamó a los procedimientos que podían ejecutarse para siempre sin detenerse por el nombre de procedimiento de cálculo o algoritmo (Kleene 1952: 137). Kleene también exigió que tal algoritmo eventualmente exhibiera "algún objeto" (Kleene 1952: 137). Burgin sostiene que esta condición la satisfacen las máquinas de Turing inductivas, ya que sus resultados se muestran después de un número finito de pasos. La razón por la que no se puede ordenar a las máquinas de Turing inductivas que se detengan cuando se produce su salida final es que, en algunos casos, las máquinas de Turing inductivas pueden no ser capaces de decir en qué paso se ha obtenido el resultado.

Las máquinas de Turing inductivas simples son equivalentes a otros modelos de computación como las máquinas de Turing generales de Schmidhuber, los predicados de prueba y error de Hilary Putnam, las funciones recursivas parciales limitantes de Gold y las máquinas de prueba y error de Hintikka y Mutanen (1998). Las máquinas de Turing inductivas más avanzadas son mucho más potentes. Hay jerarquías de máquinas de Turing inductivas que pueden decidir la pertenencia a conjuntos arbitrarios de la jerarquía aritmética (Burgin 2005). En comparación con otros modelos equivalentes de computación, las máquinas de Turing inductivas simples y las máquinas de Turing en general dan construcciones directas de autómatas de computación que están completamente basadas en máquinas físicas. En contraste, los predicados de prueba y error, las funciones recursivas limitantes y las funciones recursivas parciales limitantes presentan sólo sistemas sintácticos de símbolos con reglas formales para su manipulación. Las máquinas de Turing inductivas simples y las máquinas de Turing generales están relacionadas con la limitación de funciones recursivas parciales y los predicados de prueba y error, como las máquinas de Turing están relacionadas con funciones recursivas parciales y cálculo lambda.

Los cálculos ininterrumpidos de las máquinas de Turing inductivas no deben confundirse con los cálculos de tiempo infinito (ver, por ejemplo, Potgieter 2006). Primero, algunos cálculos de las máquinas de Turing inductivas se detienen. Como en el caso de las máquinas de Turing convencionales, algunos cálculos detenidos dan el resultado, mientras que otros no. Incluso si no se detiene, una máquina de Turing inductiva produce salidas de vez en cuando. Si esta salida deja de cambiar, se considera el resultado del cálculo.

Hay dos distinciones principales entre las máquinas de Turing ordinarias y las máquinas de Turing inductivas simples. La primera distinción es que incluso las máquinas de Turing inductivas simples pueden hacer mucho más que las máquinas de Turing convencionales. La segunda distinción es que una máquina de Turing convencional siempre determinará (al llegar a un estado final) cuándo se obtiene el resultado, mientras que una máquina de Turing inductiva simple, en algunos casos (como cuando "calcula" algo que no puede ser calculado por un máquina de Turing ordinaria), no podrá tomar esta determinación.

Máquinas de Turing generalizadas de Schmidhuber

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 π, pero aún excluye la mayoría de los números reales, porque la mayoría no puede describirse mediante un programa finito. Las máquinas de Turing tradicionales con una cinta de salida de solo escritura no pueden editar sus salidas anteriores; Las máquinas de Turing generalizadas , según Jürgen Schmidhuber , pueden editar tanto su cinta de salida como su cinta de trabajo. Él define las secuencias de símbolos constructivamente describibles 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. Schmidhuber (2000, 2002) utiliza 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 y las máquinas de Turing inductivas simples son dos clases de algoritmos superrecursivos que son los más cercanos a los algoritmos recursivos (Schmidhuber 2000).

Relación con la tesis de Church-Turing

La tesis de Church-Turing en la teoría de la recursividad se basa en una definición particular del término algoritmo . Basado en definiciones que son más generales que las que se usan comúnmente en la teoría de la recursividad, Burgin sostiene que los algoritmos superrecursivos, como las máquinas inductivas de Turing, refutan la tesis de Church-Turing . Además, demuestra que los algoritmos superrecursivos teóricamente podrían proporcionar ganancias de eficiencia aún mayores que el uso de algoritmos cuánticos .

La interpretación de Burgin de los algoritmos superrecursivos ha encontrado oposición en la comunidad matemática. Un crítico es el lógico Martin Davis , quien sostiene que las afirmaciones de Burgin se han entendido bien "durante décadas". Davis dice,

"La presente crítica no se trata de la discusión matemática de estos asuntos, sino sólo de las afirmaciones engañosas sobre los sistemas físicos del presente y del futuro" (Davis 2006: 128).

Davis cuestiona las afirmaciones de Burgin de que los conjuntos en el nivel de la jerarquía aritmética se pueden llamar computables, diciendo

"Se entiende generalmente que para que un resultado computacional sea útil, uno debe ser capaz de reconocer al menos que es realmente el resultado buscado". (Davis 2006: 128)

Ver también

Referencias

  • Blum, L., F. Cucker, M. Shub y S. Smale, Complexity and Real Computation , Springer Publishing 1998
  • Burgin, Mark (2005), Algoritmos superrecursivos , Monografías en informática, Springer. ISBN  0-387-95569-0
  • Copeland, J. (2002) Hypercomputation, Minds and Machines , v. 12, págs. 461–502
  • Davis, Martin (2006), " The Church-Turing Thesis: Consenso y oposición ". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 págs. 125-132
  • Eberbach, E. (2005) "Hacia una teoría de la computación evolutiva", BioSystems 82, 1-19
  • Oro, EM Limitando la recursividad. J. Symb. Tronco. 10 (1965), 28-48.
  • Gold, E. Mark (1967), Language Identification in the Limit (PDF) , 10 , Información y control , págs. 447–474
  • Hagar, A. y Korolev, A. (2007) "Hipercomputación cuántica: ¿bombo o computación?"
  • Hintikka, Ja. y Mutanen, A. Un concepto alternativo de computabilidad, en "Lenguaje, verdad y lógica en matemáticas", Dordrecht, págs. 174-188, 1998
  • Kleene, Stephen C. (1952), Introducción a las metamatemáticas (Primera edición), Amsterdam: North-Holland Publishing Company.
  • Peter Kugel, "Es hora de pensar fuera de la caja computacional", Communications of the ACM , Volumen 48, Número 11, noviembre de 2005
  • Petrus H. Potgieter, "Zeno machines and hypercomputation", Theoretical Computer Science , Volumen 358, Número 1 (julio de 2006) págs. 23 - 33
  • Hilary Putnam, "Predicados de prueba y error y la solución a un problema de Mostowski". Journal of Symbolic Logic , volumen 30, número 1 (1965), 49-57
  • Darko Roglic, " La computadora evolutiva universal basada en algoritmos superrecursivos de evolución "
  • Hava Siegelmann, Redes neuronales y computación analógica: más allá del límite de Turing , Birkhäuser , 1999, ISBN  0817639497
  • Turing, A. (1939) Sistemas de lógica basados ​​en ordinales, Proc. Lond. Matemáticas. Soc. , Ser.2, v. 45: 161-228
  • van Leeuwen, J. y Wiedermann, J. (2000a) Rompiendo la barrera de Turing: El caso de Internet , Techn. Informe, Inst. de Ciencias de la Computación, Academia de Ciencias de la República Checa , Praga
  • Jiří Wiedermann, Caracterización de la potencia y eficiencia de la computación súper Turing de las máquinas de Turing difusas clásicas, Informática teórica , Volumen 317, Número 1-3, junio de 2004
  • Jiří Wiedermann y Jan van Leeuwen , "El potencial computacional emergente de los sistemas vivos artificiales en evolución", AI Communications , v. 15, No. 4, 2002

Otras lecturas

  • Akl, SG, Tres contraejemplos para disipar el mito de la computadora universal, Cartas de procesamiento paralelo , vol. 16, núm. 3, septiembre de 2006, págs. 381 - 403.
  • Akl, SG, The myth of universal computation, en: Parallel Numerics, Trobec, R., Zinterhof, P., Vajtersic, M., y Uhl, A., Eds., Part 2, Systems and Simulation , Universidad de Salzburgo, Salzburgo, Austria e Instituto Jozef Stefan, Ljubljana, Eslovenia, 2005, págs. 211 - 236
  • Angluin, D. y Smith, CH (1983) Inductive Inference: Theory and Methods, Comput. Encuestas , v. 15, no. 3, págs. 237–269
  • Apsïtis, K, Arikawa, S, Freivalds, R., Hirowatari, E. y Smith, CH (1999) Sobre la inferencia inductiva de funciones recursivas de valor real, Theoretical Computer Science , 219 (1-2): 3-17
  • Boddy, M, Dean, T. 1989. "Solución de problemas de planificación dependientes del tiempo". Informe técnico: CS-89-03, Brown University
  • Burgin, M. "Complejidad algorítmica de algoritmos recursivos e inductivos", Ciencias de la computación teóricas , v. 317, No. 1/3, 2004, pp. 31-60
  • Burgin, M. y Klinger, A. Experiencia, generaciones y límites en el aprendizaje automático, Informática teórica , v. 317, núm. 1/3, 2004, págs. 71–91
  • Eberbach, E. y Wegner, P., "Beyond Turing Machines", Boletín de la Asociación Europea de Ciencias de la Computación Teórica (Boletín EATCS), 81, octubre de 2003, 279-304
  • S. Zilberstein, Uso de algoritmos en cualquier momento en sistemas inteligentes, "AI Magazine", 17 (3): 73-83, 1996

enlaces externos