Real cómputo - Enciclopedia

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 números reales. Dentro de esta teoría, es posible probar afirmaciones interesantes como "El complemento del conjunto de Mandelbrot es solo parcialmente decidible".

Estas máquinas de computación hipotéticas pueden considerarse computadores analógicos idealizados que operan sobre números reales, mientras que los computadores digitales están limitados a números computables. Pueden subdividirse en modelos diferenciales y algebraicos (en este contexto, los computadores digitales deben pensarse como topológicos, al menos en lo que respecta a su operación sobre números reales computables). Dependiendo del modelo elegido, esto puede permitir que los computadores reales resuelvan problemas que son inextricablemente difíciles en los computadores digitales (por ejemplo, las redes neuronales de Hava Siegelmann pueden tener pesos reales no computables, lo que les permite computar lenguajes no recursivos) o viceversa. (El computador analógico idealizado de Claude Shannon solo puede resolver ecuaciones diferenciales algebraicas, mientras que un computador digital puede resolver algunas ecuaciones trascendentes también. Sin embargo, esta comparación no es completamente justa, ya que en el computador analógico idealizado de Claude Shannon las computaciones se realizan inmediatamente; es decir, la computación se realiza en tiempo real. El modelo de Shannon puede adaptarse para hacer frente a este problema).

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


Ver también
Hypercomputation, para otras máquinas tan poderosas.
Real RAM.
Autómata cuántico finito, para una generalización a espacios geométricos arbitrarios.


Referencias


Leer más
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: multiple names: authors list (link)
Campagnolo, Manuel Lameiras (julio 2001). Computational complexity of real valued recursive functions and analog circuits. Universidade Técnica de Lisboa, Instituto Superior Técnico.
Natschläger, Thomas, Wolfgang Maass, Henry Markram. The "Liquid Computer" A Novel Strategy for Real-Time Computing on Time Series (PDF).{{cite book}}: CS1 maint: multiple names: authors list (link)
Siegelmann, Hava (diciembre 1998). Neural Networks and Analog Computation: Beyond the Turing Limit. Springer. ISBN 0-8176-3949-7.
Siegelmann, Hava T.; Sontag, Eduardo D. (1995). "On the computational power of neural nets" (PDF). Journal of Computer and System Sciences. 50 (1): 132–150. doi:10.1006/jcss.1995.1013. MR 1322637.