Computação real

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde abril de 2013).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.

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, é possivel 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]

Referências

  1. Klaus Weihrauch. A Simple Introduction to ComputableAnalysis. [S.l.: s.n.], 1995.
  2. O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry. (Jun 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.
  3. 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]