Turingovská úplnost: Porovnání verzí
Smazaný obsah Přidaný obsah
m šablona úpravy - chybí zdroje značka: editace z Vizuálního editoru |
-nesouvisející NP-úplnost, +RE (třída složitosti), -kategorie, {{upravit}} požadující zdroje nahrazeno za {{pahýl}}: není tu nic moc rozporovatelného, spíš je to velmi letem světem |
||
Řádek 1:
'''Turingovská úplnost''' je pojem z oboru [[teorie vyčíslitelnosti]]: '''Turingovsky kompletní''', '''turingovsky úplný''' nebo '''turingovsky 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 [[Churchova–Turingova teze|Churchovy–Turingovy teze]] žádné konečné zařízení víc spočítat nedokáže). Dá se tedy říct, že turingovsky kompletní stroj je tak
▲'''Turingovsky kompletní''', '''turingovsky úplný''' nebo '''turingovsky 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 [[Churchova–Turingova teze|Churchovy–Turingovy teze]] žádné konečné zařízení víc spočítat nedokáže). Dá se tedy říct, že turingovsky kompletní stroj je tak [[univerzální]], jak je jen možné (to ovšem neříká nic o [[efektivita|efektivitě]]). Speciálně lze sestrojit [[Turingův stroj#Univerzální TS|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]]. [[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í]] ({{Vjazyce2|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
== Související články ==
* [[Churchova–Turingova teze]]
* [[Turingův stroj]]
{{Pahýl}}
{{Autoritní data}}
▲[[Kategorie:Třídy složitosti]]
[[Kategorie:Vyčíslitelnost]]
| |||