Computação real
 |
Em teoria da computação, a teoria da computação real lida com hipotéticas máquinas de computaçao que usam números reais com precisão infinita. Elas recebem esse nome porque operam sobre o conjunto dos números reais. Nessa teoria, é possível provar importantes enunciados tais como a proposição de que "O complemento do conjunto de Mandelbrot é semidecidível ".
Essas hipotéticas máquinas de computação podem ser vistas como um Computador analógico idealizado que opera sobre os números reais, enquanto que computadores estão limitados a números computáveis. Elas ainda podem ser subdivididas em modelos diferencial e algébrico (computadores digitais, nesse contexto, devem ser considerados como topológicos, pelo menos nas operações em que a computação real se preocupa [1]). Dependendo do modelo escolhido, podemos permitir que computadores reais resolvam problemas inextricáveis em computadores digitais (por exemplo,redes neurais de Hava Siegelmann's podem ter pesos reais não-computáveis, fazendo-os capaz de computar linguagens não recursivas.) ou vice versa. (O computador analógico idealizado de Claude Shannon consegue apenas resolver equações algebricas diferencias, enquanto que um computador digital consegue resolver também algumas equaçoes transcendentais . Entretanto, essa comparação não é completamente justa uma vez que no computador analógico idealizado de Claude Shannon as computações são realizadas imediatamente ; i.e., a computação é feita em tempo real. O modelo de Shannon pode ser adaptado para lidar com esse problema.)[2]
Um modelo canônico de computação sobre os reais é a máquina de Blum–Shub–Smale (BSS).
Se a computação real fosse fisicamente possível, poderiamos usá-la para resolver problemas NP-completos, e até mesmo problemas #P-completos, em tempo polinomial. Números reais com precisão ilimitada são inconcebíveis de acordo com o princípio holográfico e o Limite de Bekenstein.[3]
Veja também[editar | editar código-fonte]
- Hipercomputação, para outras máquinas tão poderosas quanto.
Referências
- ↑ Klaus Weihrauch (1995). A Simple Introduction to ComputableAnalysis. [S.l.: s.n.]
- ↑ O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry (2007). «Polynomial differential equations compute all real computable functions on computable compact intervals». Journal of Complexity. 23 (3): 317–335. doi:10.1016/j.jco.2006.12.005
- ↑ Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.
Leitura extra[editar | editar código-fonte]
- Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale. Complexity and Real Computation. [S.l.: s.n.] ISBN 0-387-98281-7
- Campagnolo, Manuel Lameiras (julho de 2001). Computational complexity of real valued recursive functions and analog circuits. [S.l.]: 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). [S.l.: s.n.]
- Siegelmann, Hava. Neural Networks and Analog Computation: Beyond the Turing Limit. [S.l.: s.n.] ISBN 0-8176-3949-7
- Siegelmann, Hava & Sontag, Eduardo D. On The Computational Power Of Neural Nets. [S.l.: s.n.][ligação inativa]