Computación real

Concepto en la teoría de la computabilidad

Diagrama de circuito de un elemento de computación analógica para integrar una función dada. La teoría de 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 demostrar enunciados interesantes como "El complemento del conjunto de Mandelbrot es solo parcialmente decidible".

Estas máquinas de computación hipotéticas pueden ser vistas 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 modelos diferenciales y algebraicos (las computadoras digitales, en este contexto, deben considerarse topológicas , al menos en lo que respecta a su operación en reales computables ^[1] ). Dependiendo del modelo elegido, esto puede permitir que las computadoras reales resuelvan problemas que son inextricables en las computadoras digitales (por ejemplo, las redes neuronales de Hava Siegelmann pueden tener pesos reales no computables, lo que las hace capaces de calcular 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 computación sobre los números reales es la máquina Blum-Shub-Smale (BSS).

Si la computación 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]

Véase también

• Hipercomputación , para otras máquinas tan potentes.
• RAM real .
• Autómata cuántico finito , para una generalización a espacios geométricos arbitrarios.

Referencias

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

Lectura adicional

• Lenore Blum , Felipe Cucker, Michael Shub y Stephen Smale (1998). Complejidad y computación real . ISBN 0-387-98281-7.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Campagnolo, Manuel Lameiras (julio de 2001). Complejidad computacional de funciones recursivas de valor real y circuitos analógicos . Universidad Técnica de Lisboa, Instituto Superior Técnico.
• Natschläger, Thomas, Wolfgang Maass, Henry Markram. La "computadora líquida": una nueva estrategia para la computación en tiempo real sobre series temporales (PDF) .{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
• 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 T. ; Sontag, Eduardo D. (1995). "Sobre el poder computacional de las redes neuronales" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 50 (1): 132–150. doi :10.1006/jcss.1995.1013. MR  1322637.