Verze z 25. 11. 2008, 11:37 editovat MystBot (diskuse \| příspěvky) 21 532 editací m robot přidal: fi:Turing-vahva ← Přejít na předchozí porovnání		Verze z 22. 1. 2009, 22:57 editovat zrušit editaci Milan Keršláger (diskuse \| příspěvky) Prověření uživatelé 12 670 editací m +odkaz Přejít na další porovnání →
Řádek 1: '''Turing-kompletní''', '''turing-~~uplný~~úplný''' nebo '''turing-ekvivalentní''' ({{Vjazyce2\|en\|'''Turing-complete'''}}) 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 [[Church-Turingova teze\|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 [[efektivita\|efektivitě]]). Speciálně lze sestrojit [[univerzální Turingův stroj]], který dokáže simulovat libovolný jiný turingův stroj (zadaný na vstupu). [[Formální jazyk\|Jazyky]] přijímané Turingovým strojem se nazývají [[rekurzivně spočetný jazyk\|rekurzivně spočetné jazyky]]. Tato třída jazyků je uzavřená na konečné sjednocení, konečné průniky, [[konkatenace\|konkatenaci]], [[iterace\|iteraci]], zrcadlový obraz, [[kvocient]]y s [[rekurze\|rekurzivně]] spočetnými jazyky a rekurzivně spočetnou substituci. Nejsou uzavřené na doplněk. [[Formální gramatika\|Gramatiky]] [[Chomského hierarchie]] které generují tyto jazyky, se nijak nenazývají, protože každá gramatika generuje rekurzivně spočetný jazyk. Řádek 6: Název je odvozen od matematického pojmu [[NP-úplnost\|NP-úplný]]. == Související články == * [[Church-Turingova teze]] * [[Turingův stroj]] [[Kategorie:Třídy složitosti]]

Turingovská úplnost: Porovnání verzí