Verze z 9. 3. 2013, 05:15 editovat Addbot (diskuse \| příspěvky) 210 261 editací m Bot: Odstranění 17 odkazů interwiki, které jsou nyní dostupné na Wikidatech (d:q197970) ← Přejít na předchozí porovnání		Verze z 9. 4. 2013, 01:32 editovat zrušit editaci Milda (diskuse \| příspěvky) Prověření uživatelé 11 819 editací m čárka, pomlčka Přejít na další porovnání →
Řádek 5: [[Formální jazyk\|Jazyky]] přijímané Turingovým strojem se nazývají [[rekurzivně spočetný jazyk\|rekurzivně spočetné jazyky]]. [[Formální gramatika\|Gramatiky]], které generují tyto jazyky, se v rámci [[Chomského hierarchie]] označují jako gramatiky typu 0. Typickým problémem, který nelze řešit na [[Turingův stroj\|Turingově stroji]], je [[problém zastavení]] ({{Vjazyce\|en}} {{Cizojazyčně\|en\|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řevoditelné a problém zastavení pro stupeň ''N'' je ve stupni ''N+1''. == Související články ==

Turingovská úplnost: Porovnání verzí