Turing-kompletní

Z Wikipedie, otevřené encyklopedie

Turing-kompletní, turing-uplný nebo turing-ekvivalentní je stroj (počítač), programovací jazyk, úloha nebo abstraktní stroj, který má stejnou výpočetní sílu jako Turingův stroj. Tato třída je důležitá proto, že není znám žádný způsob řešení úlohy, která je těžší (Podle Churchovy hypotézy žádné konečné zařízení víc spočítat nedokáže). Dá se tedy říct, že turing-kompletní stroj je tak univerzální, jak je jen možné. (To ovšem neříká nic o efektivitě.) Speciálně lze sestrojit univerzální turingův stroj, který dokáže simulovat libovolný jiný turingův stroj (zadaný na vstupu).

Jazyky přijímané Turingovým strojem se nazývají rekurzivně spočetné jazyky. Tato třída jazyků je uzavřená na konečné sjednocení, konečné průniky, konkatenaci, iteraci, zrcadlový obraz, kvocienty s rekurzivně spočetnými jazyky a rekurzivně spočetnou substituci. Nejsou uzavřené na doplněk. Gramatiky Chomského hierarchie které generují tyto jazyky, se nijak nenazývají, protože každá gramatika generuje rekurzivně spočetný jazyk.

Typickým problémem, který nelze řešit na turingově stroji je problém zastavení (halting problem), tedy problém zastavení turingova stroje. Matematicky je tento problém demonstrací neuzavřenosti třídy rekurzivně spočetných jazyků na doplněk. Teorie vyčíslitelnosti pokračuje v teoretickém výzkumu k ještě složitějším problémům - aritmetická hierarchie je posloupnost tříd jazyků. Její nultý stupeň jsou rekurzivně spočetné jazyky, všechny jazyky na stejném stupni jsou mezi sebou turingovsky převeditelné a problém zastavení pro stupeň N je ve stupni N+1.

Název je odvozen od matematického pojmu NP-úplný.