Real computation

rdf:langString Computação real

rdf:langString 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 (computadores digitais, nesse contexto, devem ser considerados como topológicos, pelo menos nas operações em que a computação real se preocupa ). Dependendo do modelo escolhido, podemos permitir que computadores reais resolvam problemas inextricáveis em computadores digitais (por exemplo,redes neurais de '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.) Um modelo canônico de computação sobre os reais é a (BSS). Se a computação real fosse fisicamente possível, poderiamos usá-la para resolver problemas NP-completos, e até mesmo problemas -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.