Riktig beräkning

Kretsschema för ett analogt beräkningselement för att integrera en given funktion. Verklig beräkningsteori undersöker egenskaperna hos sådana enheter under det idealiserande antagandet om oändlig precision.

I beräkningsbarhetsteorin behandlar teorin om verklig beräkning hypotetiska beräkningsmaskiner som använder reella tal med oändlig precision . De får det här namnet eftersom de arbetar på uppsättningen av reella tal . Inom denna teori är det möjligt att bevisa intressanta påståenden som "Komplementet till Mandelbrot-uppsättningen är endast delvis avgörbart."

Dessa hypotetiska beräkningsmaskiner kan ses som idealiserade analoga datorer som arbetar på reella siffror, medan digitala datorer är begränsade till beräkningsbara siffror . De kan delas in ytterligare i differentiella och algebraiska modeller (digitala datorer, i detta sammanhang, bör ses som topologiska , åtminstone när det gäller deras funktion på beräkningsbara realer ). Beroende på vilken modell som väljs kan detta göra det möjligt för riktiga datorer att lösa problem som är oupplösliga på digitala datorer (Till exempel kan Hava Siegelmanns neurala nät ha icke-beräknbara reella vikter, vilket gör dem i stånd att beräkna icke-rekursiva språk.) eller vice versa. ( Claude Shannons idealiserade analoga dator kan bara lösa algebraiska differentialekvationer, medan en digital dator också kan lösa vissa transcendentala ekvationer. Denna jämförelse är dock inte helt rättvis eftersom i Claude Shannons idealiserade analoga datorberäkningar görs omedelbart; dvs. görs i realtid. Shannons modell kan anpassas för att klara detta problem.)

En kanonisk modell för beräkning över realerna är Blum–Shub–Smale machine ( BSS).

Om verklig beräkning var fysiskt realiserbar, skulle man kunna använda den för att lösa NP-kompletta problem, och till och med #P -kompletta problem, i polynomtid . Reella tal med obegränsad precision i det fysiska universum är förbjudna av den holografiska principen och Bekenstein-bunden .

Se även

Hypercomputation , för andra sådana kraftfulla maskiner.

^ Klaus Weihrauch (1995). En enkel introduktion till beräkningsbar analys .
^ O. Bournez; ML Campagnolo; DS Graça & E. Hainry (juni 2007). "Polynomiska differentialekvationer beräknar alla verkliga beräkningsbara funktioner på beräkningsbara kompakta intervall" . Journal of Complexity . 23 (3): 317–335. doi : 10.1016/j.jco.2006.12.005 .
^ Scott Aaronson , NP-fullständiga problem och fysisk verklighet , ACM SIGACT News, Vol. 36, nr 1. (mars 2005), s. 30–52.

Vidare läsning

Lenore Blum , Felipe Cucker, Michael Shub och Stephen Smale (1998). Komplexitet och verklig beräkning . ISBN 0-387-98281-7 . {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )
Campagnolo, Manuel Lameiras (juli 2001). Beräkningskomplexitet för verkligt värderade rekursiva funktioner och analoga kretsar . Universidade Técnica de Lisboa, Instituto Superior Técnico.
Natschläger, Thomas, Wolfgang Maass, Henry Markram. "Liquid Computer" En ny strategi för realtidsberäkning i tidsserier ( PDF) . {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )
Siegelmann, Hava (december 1998). Neurala nätverk och analog beräkning: bortom Turing-gränsen . ISBN 0-8176-3949-7 .
Siegelmann, Hava & Sontag, Eduardo D. On the Computational Power Of Neural Nets . ^{[ permanent död länk ]}

[1] Klaus Weihrauch (1995). En enkel introduktion till beräkningsbar analys .

[2] O. Bournez; ML Campagnolo; DS Graça & E. Hainry (juni 2007). "Polynomiska differentialekvationer beräknar alla verkliga beräkningsbara funktioner på beräkningsbara kompakta intervall" . Journal of Complexity . 23 (3): 317–335. doi : 10.1016/j.jco.2006.12.005 .

[3] Scott Aaronson , NP-fullständiga problem och fysisk verklighet , ACM SIGACT News, Vol. 36, nr 1. (mars 2005), s. 30–52.