Turingovská úplnost: Porovnání verzí
Smazaný obsah Přidaný obsah
Bez shrnutí editace |
pridani par linku |
||
Řádek 1:
'''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 [[Churchova hypotéza|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í [[rekursivně 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.
| |||