Teorie vyčíslitelnosti: Porovnání verzí
Smazaný obsah Přidaný obsah
Tohle je vážně zoufalý pahýl ... když člověka nenapadne podívat se do té kategorie, připadá mu že tu nic není ... alespoň něco přidávám ... |
→Související články: Ještě něco ... |
||
| Řádek 10: | Řádek 10: | ||
== Související články == |
== Související články == |
||
* [[Chomského hierarchie]] |
* [[Chomského hierarchie]] |
||
* [[Gödelovy věty o neúplnosti]] |
|||
{{Matematický pahýl}} |
{{Matematický pahýl}} |
||
Verze z 14. 4. 2007, 13:07
Teorie vyčíslitelnosti zkoumá hranice algoritmické konstrukce množin. Pro modelování využívá například Turingův stroj, částečně rekurzivní funkce a intuicionistickou logiku.
Zajímavé výsledky
- Nelze zkonstruovat algoritmus, který by pro obecný program ověřil jeho konečnost (tzv. problém zastavení).
Zajímavé hypotézy
- Ke každému algoritmu existuje ekvivalentní Turingův stroj (tzv. Church-Turingova teze).