Computación real

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 . Reciben este nombre porque operan sobre el conjunto de los números reales. Dentro de esta teoría, es posible demostrar afirmaciones interesantes como «El complemento del conjunto de Mandelbrot es solo parcialmente decidible».

Estas hipotéticas máquinas de computación pueden considerarse computadoras analógicas idealizadas que operan con números reales, mientras que las computadoras digitales se limitan a números computables . Pueden subdividirse aún más en modelos diferenciales y algebraicos (en este contexto, las computadoras digitales deben considerarse topológicas , al menos en lo que respecta a su operación con números reales computables ^{[ 1 ]} ). Dependiendo del modelo elegido, esto puede permitir que las computadoras reales resuelvan problemas que son irresolubles en las computadoras digitales, o viceversa. Por ejemplo, las redes neuronales de Hava Siegelmann pueden tener pesos reales no computables, lo que les permite computar lenguajes no recursivos. 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 de inmediato; es decir, el cálculo se realiza en tiempo real. El modelo de Shannon puede adaptarse para abordar este problema. ^{[ 2 ]}

Un modelo canónico de computación sobre los números reales es la máquina de 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 la cota de Bekenstein . ^{[ 3 ]}

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

• Lenore Blum , Felipe Cucker, Michael Shub y Stephen Smale (1998). Complejidad y computación real . Springer. 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 estrategia novedosa para la computación en tiempo real en 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 . Springer. ISBN 0-8176-3949-7.
• Siegelmann, Hava T. ; Sontag, Eduardo D. (1995). "Sobre el poder computacional de las redes neuronales" (PDF) . Journal of Computer and System Sciences . 50 (1): 132– 150. doi : 10.1006/jcss.1995.1013 . MR 1322637 .