Teorie vyčíslitelnosti: Porovnání verzí
Smazaný obsah Přidaný obsah
m repahýl |
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 ... |
||
Řádek 1:
'''Teorie vyčíslitelnosti''' zkoumá hranice [[algoritmus|algoritmické]] konstrukce [[množina|množin]].
Pro modelování využívá například [[Turingův stroj]], [[částečně rekurzivní funkce]] a [[intuicionistická logika|intuicionistickou logiku]].
== Zajímavé výsledky
* Nelze zkonstruovat algoritmus, který by pro obecný [[počítačový program|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]]).
== Související články ==
* [[Chomského hierarchie]]
{{Matematický pahýl}}
| |||