Computación real

Diagrama de circuito de un elemento informático analógico para integrar una función determinada. La teoría de la computación real investiga las propiedades de tales dispositivos bajo el supuesto idealizador de precisión infinita.

En la teoría de la computabilidad , la teoría de la computación real se ocupa de máquinas de computación hipotéticas que utilizan números reales de precisión infinita . Se les da este nombre porque operan sobre el conjunto de números reales . Dentro de esta teoría, es posible probar afirmaciones interesantes como "El complemento del conjunto de Mandelbrot es sólo parcialmente decidible".

Estas máquinas de computación hipotéticas pueden verse como computadoras analógicas idealizadas que operan con números reales, mientras que las computadoras digitales están limitadas a números computables . Pueden subdividirse en diferenciales y algebraicas modelos (las computadoras digitales, en este contexto, debe ser considerado como topológico , al menos en cuanto a su operación en reales computables se refiere a ^[1] ). Dependiendo del modelo elegido, esto puede permitir que los equipos reales para resolver problemas que son inseparables en las computadoras digitales (Por ejemplo, Hava Siegelmann 's redes neuronalespueden tener pesos reales no computables, lo que les permite computar lenguajes no recursivos.) o viceversa. ( La computadora analógica idealizada de Claude Shannon solo puede resolver ecuaciones diferenciales algebraicas, mientras que una computadora digital también puede resolver algunas ecuaciones trascendentales. Sin embargo, esta comparación no es del todo justa ya que en la computadora analógica idealizada de Claude Shannon los cálculos se realizan inmediatamente; es decir, el cálculo se realiza en tiempo real. El modelo de Shannon se puede adaptar para hacer frente a este problema.) ^[2]

Un modelo canónico de cálculo sobre los reales es la máquina Blum-Shub-Smale (BSS).

Si el cálculo real fuera físicamente realizable, se podría usar para resolver problemas NP-completos , e incluso problemas #P -completos, en tiempo polinomial . Los números reales de precisión ilimitada en el universo físico están prohibidos por el principio holográfico y el límite de Bekenstein . ^[3]

Ver también

• Hipercomputación , para otras máquinas tan poderosas.

Referencias

1. Klaus Weihrauch (1995). Una simple introducción al análisis computable .
2. O. Bournez; ML Campagnolo; DS Graça y E. Hainry (junio de 2007). "Las ecuaciones diferenciales polinomiales calculan todas las funciones computables reales en intervalos compactos computables" . Revista de complejidad . 23 (3): 317–335. doi : 10.1016 / j.jco.2006.12.005 .
3. Scott Aaronson , NP-completo problemas y realidad física , ACM SIGACT News, vol. 36, No. 1. (marzo de 2005), págs. 30–52.

Otras lecturas

• Lenore Blum , Felipe Cucker, Michael Shub y Stephen Smale (1998). Complejidad y Computación Real . ISBN 0-387-98281-7.
• Campagnolo, Manuel Lameiras (julio de 2001). Complejidad computacional de funciones recursivas de valor real y circuitos analógicos . Universidade Técnica de Lisboa, Instituto Superior Técnico.
• Natschläger, Thomas, Wolfgang Maass, Henry Markram. La "computadora líquida" Una estrategia novedosa para la computación en tiempo real en series de tiempo (PDF) .
• Siegelmann, Hava (diciembre de 1998). Redes neuronales y computación analógica: más allá del límite de Turing . ISBN 0-8176-3949-7.
• Siegelmann, Hava & Sontag, Eduardo D. Sobre el poder computacional de las redes neuronales .^{[ enlace muerto permanente ]}

Este artículo de ciencias de la computación es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .

• v
• t
• mi