Teorie vyčíslitelnosti
Z Wikipedie, otevřené encyklopedie
Teorie vyčíslitelnosti zkoumá hranice algoritmické konstrukce množin. Pro modelování využívá například Turingův stroj a intuicionistickou logiku.
Zajímavé výsledky:
- Nelze zkonstruovat algoritmus, který by pro obecný program ověřil jeho konečnost (tzv. problém zastavení).