Skutečný výpočet - Real computation
V teorii vypočítatelnosti se teorie reálných výpočtů zabývá hypotetickými výpočetními stroji využívajícími reálná čísla s nekonečnou přesností . Dostali toto jméno, protože pracují na množině reálných čísel . V rámci této teorie je možné dokázat zajímavá tvrzení jako „Doplněk Mandelbrotovy množiny je rozhodnutelný pouze částečně.“
Tyto hypotetické výpočetní stroje lze považovat za idealizované analogové počítače, které pracují na reálných číslech, zatímco digitální počítače jsou omezeny na vypočítatelná čísla . Mohou být dále rozděleny na diferenciální a algebraické modely (digitální počítače by v této souvislosti měly být považovány za topologické , alespoň pokud jde o jejich provoz na vypočítatelných realitách ). V závislosti na zvoleném modelu, může to umožnit skutečné počítačů k řešení problémů, které jsou neoddělitelné na číslicových počítačů (například Hava Siegelmann s neuronové sítě mohou mít noncomputable skutečné hmotnosti, což je schopen vypočítat nerekurzivní jazyky.), Nebo vice versa. ( Idealizovaný analogový počítač Clauda Shannona dokáže řešit pouze algebraické diferenciální rovnice, zatímco digitální počítač dokáže vyřešit i některé transcendentální rovnice. Toto srovnání však není zcela férové, protože v idealizovaných analogových počítačových výpočtech Clauda Shannona se provádí okamžitě; tj. Výpočet se provádí v reálném čase. Shannonův model lze upravit tak, aby se s tímto problémem vyrovnal.)
Kanonickým modelem výpočtu nad reálemi je stroj Blum – Shub – Smale (BSS).
Pokud by byl skutečný výpočet fyzicky realizovatelný, bylo by možné jej použít k řešení NP-úplných problémů a dokonce #P -kompletních problémů v polynomiálním čase . Neomezená přesnost reálných čísel ve fyzickém vesmíru je zakázána holografickým principem a Bekensteinovým vázáním .
Viz také
- Hypercomputation , pro další takové výkonné stroje.
Reference
- ^ Klaus Weihrauch (1995). Jednoduchý úvod do vypočítatelné analýzy .
- ^ O. Bournez; ML Campagnolo; DS Graça & E. Hainry (červen 2007). Msgstr "Polynomiální diferenciální rovnice počítají všechny skutečné vypočítatelné funkce v vypočítatelných kompaktních intervalech" . Journal of Complexity . 23 (3): 317–335. doi : 10.1016 / j.jco.2006.12.005 .
- ^ Scott Aaronson , NP-úplné problémy a fyzická realita , ACM SIGACT News, sv. 36, č. 1 (březen 2005), s. 30–52.
Další čtení
- Lenore Blum , Felipe Cucker, Michael Shub a Stephen Smale (1998). Složitost a skutečný výpočet . ISBN 0-387-98281-7.CS1 maint: více jmen: seznam autorů ( odkaz )
- Campagnolo, Manuel Lameiras (červenec 2001). Výpočetní složitost reálně oceněných rekurzivních funkcí a analogových obvodů . Universidade Técnica de Lisboa, Instituto Superior Técnico.
- Natschläger, Thomas, Wolfgang Maass, Henry Markram. „Tekutý počítač“ Nová strategie pro výpočet v reálném čase na časové řadě (PDF) .CS1 maint: více jmen: seznam autorů ( odkaz )
- Siegelmann, Hava (prosinec 1998). Neuronové sítě a analogové výpočty: Za Turingovým limitem . ISBN 0-8176-3949-7.
- Siegelmann, Hava & Sontag, Eduardo D. O výpočetní síle neuronových sítí .
Tento článek o informatice je útržek . Wikipedii můžete pomoci rozšířením . |