Prawdziwe obliczenia

Schemat analogowego elementu obliczeniowego całkującego daną funkcję. Teoria obliczeń rzeczywistych bada właściwości takich urządzeń przy idealizującym założeniu nieskończonej precyzji.

W teorii obliczalności teoria obliczeń rzeczywistych dotyczy hipotetycznych maszyn liczących wykorzystujących liczby rzeczywiste o nieskończonej precyzji . Nadano im tę nazwę, ponieważ działają na zbiorze liczb rzeczywistych . W ramach tej teorii można udowodnić interesujące stwierdzenia, takie jak „Dopełnienie zbioru Mandelbrota jest rozstrzygalne tylko częściowo”.

Te hipotetyczne maszyny liczące można postrzegać jako wyidealizowane komputery analogowe , które działają na liczbach rzeczywistych, podczas gdy komputery cyfrowe ograniczają się do liczb obliczalnych . Można je dalej podzielić na różniczkowe i algebraiczne (w tym kontekście komputery cyfrowe należy uważać za topologiczne , przynajmniej w zakresie, w jakim ich działanie na obliczalnych jest zaniepokojony). W zależności od wybranego modelu może to umożliwić prawdziwym komputerom rozwiązywanie problemów, których nie da się rozwiązać na komputerach cyfrowych (na przykład sieci neuronowe Havy Siegelmanna mogą mieć nieprzeliczalne wagi rzeczywiste, dzięki czemu są w stanie obliczać języki nierekursywne) lub odwrotnie. ( Wyidealizowany komputer analogowy Claude'a Shannona może rozwiązywać tylko algebraiczne równania różniczkowe, podczas gdy komputer cyfrowy może również rozwiązywać niektóre równania przestępne. Jednak to porównanie nie jest do końca sprawiedliwe, ponieważ w przypadku Claude'a Shannona wyidealizowane analogowe obliczenia komputerowe są natychmiast wykonywane; tzn. obliczenia wykonywane są w czasie rzeczywistym. Model Shannona można dostosować, aby poradzić sobie z tym problemem.)

Kanonicznym modelem obliczeń na liczbach rzeczywistych jest maszyna Bluma – Shuba – Smalla (BSS).

Gdyby rzeczywiste obliczenia były fizycznie wykonalne, można by ich użyć do rozwiązywania problemów NP-zupełnych , a nawet problemów #P -zupełnych, w czasie wielomianowym . Nieograniczona precyzja liczb rzeczywistych we wszechświecie fizycznym jest zabroniona przez zasadę holograficzną i ograniczenie Bekensteina .

Zobacz też

Hypercomputation dla innych tak potężnych maszyn.

^ Klausa Weihraucha (1995). Proste wprowadzenie do analizy obliczeniowej .
^ O. Bournez; ML Campagnolo; DS Graça i E. Hainry (czerwiec 2007). „Wielomianowe równania różniczkowe obliczają wszystkie rzeczywiste funkcje obliczeniowe na obliczalnych zwartych przedziałach” . Dziennik złożoności . 23 (3): 317–335. doi : 10.1016/j.jco.2006.12.005 .
^ Scott Aaronson , Problemy NP-zupełne i rzeczywistość fizyczna , ACM SIGACT News, tom. 36, nr 1. (marzec 2005), s. 30–52.

Dalsza lektura

Lenore Blum , Felipe Cucker, Michael Shub i Stephen Smale (1998). Złożoność i obliczenia rzeczywiste . ISBN 0-387-98281-7 . {{ cite book }} : CS1 maint: wiele nazw: lista autorów ( link )
Campagnolo, Manuel Lameiras (lipiec 2001). Złożoność obliczeniowa funkcji rekurencyjnych o wartościach rzeczywistych i obwodów analogowych . Universidade Técnica de Lisboa, Instituto Superior Técnico.
Natschläger, Thomas, Wolfgang Maass, Henry Markram. „Płynny komputer” – nowatorska strategia obliczeń w czasie rzeczywistym na szeregach czasowych (PDF) . {{ cite book }} : CS1 maint: wiele nazw: lista autorów ( link )
Siegelmann, Hawa (grudzień 1998). Sieci neuronowe i obliczenia analogowe: poza granicą Turinga . ISBN 0-8176-3949-7 .
Siegelmann, Hava & Sontag, Eduardo D. O mocy obliczeniowej sieci neuronowych . ^{[ stały martwy link ]}

[1] Klausa Weihraucha (1995). Proste wprowadzenie do analizy obliczeniowej .

[2] O. Bournez; ML Campagnolo; DS Graça i E. Hainry (czerwiec 2007). „Wielomianowe równania różniczkowe obliczają wszystkie rzeczywiste funkcje obliczeniowe na obliczalnych zwartych przedziałach” . Dziennik złożoności . 23 (3): 317–335. doi : 10.1016/j.jco.2006.12.005 .

[3] Scott Aaronson , Problemy NP-zupełne i rzeczywistość fizyczna , ACM SIGACT News, tom. 36, nr 1. (marzec 2005), s. 30–52.