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

Kruhový diagram z analogové výpočty prvek do integrovat danou funkci. Skutečná teorie výpočtu zkoumá vlastnosti těchto zařízení pod idealizovat předpoklad nekonečné přesnosti.

v teorie vypočítatelnosti, teorie skutečný výpočet se zabývá hypotetickými výpočetními stroji využívajícími nekonečnou přesnost reálná čísla. Dostali toto jméno, protože pracují na množině reálná čísla. V rámci této teorie je možné dokázat zajímavá tvrzení jako „Doplněk Mandelbrotova sada je rozhodnutelný pouze částečně. “

Tyto hypotetické výpočetní stroje lze považovat za idealizované analogové počítače které fungují 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 rozdíl a algebraický modely (digitální počítače, v této souvislosti by měly být považovány za topologické, alespoň pokud jde o jejich provoz na vypočítatelné reals je znepokojen[1]). V závislosti na zvoleném modelu to může umožnit skutečným počítačům řešit problémy, které jsou neoddělitelné od digitálních počítačů (například Hava Siegelmann je neurální sítě mohou mít nepočítatelné reálné váhy, což jim umožňuje počítat nerekurzivní jazyky.) nebo naopak. (Claude Shannon Idealizovaný analogový počítač dokáže vyř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 spravedlivé, protože v roce 2006 Claude Shannon Idealizované analogové počítačové výpočty jsou okamžitě hotové; 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.)[2]

Kanonický model výpočtu nad reálemi je Stroj Blum – Shub – Smale (BSS).

Pokud by skutečné výpočty byly fyzicky realizovatelné, dalo by se to použít k řešení NP-kompletní problémy, a dokonce #P -kompletní problémy, v polynomiální čas. Neomezená přesnost reálných čísel ve fyzickém vesmíru je zakázána holografický princip a Bekenstein vázán.[3]

Viz také

Reference

  1. ^ Klaus Weihrauch (1995). Jednoduchý úvod do vypočítatelné analýzy.
  2. ^ O. Bournez; M. L. Campagnolo; D. S. Graça a E. Hainry (červen 2007). "Polynomiální diferenciální rovnice spočítají všechny skutečné vypočítatelné funkce ve 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í