Skutečný výpočet - Real computation

Schéma zapojení z analogového výpočetní prvek integrovat danou funkci. Teorie reálných výpočtů zkoumá vlastnosti těchto zařízení za idealizujícího předpokladu nekonečné přesnosti.

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é

Reference

  1. ^ Klaus Weihrauch (1995). Jednoduchý úvod do vypočítatelné analýzy .
  2. ^ 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 .
  3. ^ Scott Aaronson , NP-úplné problémy a fyzická realita , ACM SIGACT News, sv. 36, č. 1 (březen 2005), s. 30–52.

Další čtení