Computação real: diferenças entre revisões
nova página: Em teoria da computação, a teoria da '''computação real''' lida com hipotéticas máquinas de computaçao que usam numeros reais com precisão infinita. Elas recebem ess... |
(Sem diferenças)
|
Revisão das 02h55min de 16 de abril de 2013
Em teoria da computação, a teoria da computação real lida com hipotéticas máquinas de computaçao que usam numeros reais com precisão infinita. Elas recebem esse nome porque operam sobre o conjunto dos números reais. Nessa teoria, é possivel provar importantes declarações tais como a declaração de que "O complemento do conjunto de Mandelbrot é parcialmente decidível ".
Essas hipoteticas máquinas de computaçao podem ser vistas como computadores análogos idealizados que operam sobre os números reais, enquanto que computadores digitais estão limitados à númeroscomputáveis. Elas ainda podem ser subdivididas em modelos diferencial e algébrico (computadores digitais, nesse contexto, devem ser considerados como topologicos, pelo menos nas operações em que a computaçao real se preocupa [1]). Dependendo do modelo escolhido, podemos permitir que computadores reais resolvam problemas inextricáveis em computadores digitais (por exemplo, Hava Siegelmann's redes neurais podem ter pesos reais não-computaveis, fazendo-os capaz de computar linguagens não recursivas.) ou vice versa. (Claude Shannon's computador analogo idealizado consegue apenas resolver equações algebricas diferencias, enquanto que um computador digital consegue resolver também algumas equaçoes transcedentais . Entretanto essa comparação não é completamente justa uma vez que no computador análogo idealizado deClaude Shannon's computaçoes são realizadas imediatamente ; i.e. A computaçao é feita em tempo real. O modelo de Shannon's pode ser adaptado para lidar com esse problema.)[2]
Um modelo canônico de computaçao sobre os reais é o Blum–Shub–Smale machine (BSS).
Se a computaçao real fosse fisicamente possivel, poderiamos usa-la para resolver problemas NP-completo, e até mesmo problemas #P-completo, em tempo polinomial. Números reais com precisão ilimitada são inconcebíveis de acordo com o principio holografico e o Limite de Bekenstein.[3]
See also
- Hypercomputation, for other such powerful machines.
References
- ↑ Klaus Weihrauch (1995). A Simple Introduction to Computable Analysis. [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.
Further reading
- 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 (July 2001). Computational complexity of real valued recursive functions and analog circuits. [S.l.]: Universidade Técnica de Lisboa, Instituto Superior Técnico Verifique data em:
|data=(ajuda) - 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.]