Teorie vyčíslitelnosti

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Teorie vyčíslitelnosti je vědní obor na pomezí matematiky a informatiky, který zkoumá otázky algoritmické řešitelnosti problémů. Vytváří teoretický základ a zkoumá možnosti a hranice využití algoritmicky pracujících postupů, což se v praxi uplatňuje především na počítačové programy. Pod pojmem algoritmu se běžně rozumí mechanizovaný postup, který lze realizovat třeba na Turingově stroji. Významnou roli ve filozofickém podložení teorie vyčíslitelnosti hraje Church-Turingova teze, podle níž jsou všechny „rozumné“ výpočetní modely ekvivalentní Turingově stroji.

Pro teoretický popis pojmu algoritmu se využívá množství výpočetních modelů – například Turingův stroj, částečně rekurzivní funkce, RAM stroj a Lambda kalkul (nebo kombinatorická logika).

Zajímavé výsledky[editovat | editovat zdroj]

Zajímavé hypotézy[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

  • SIPSER, Michael. Introduction to the Theory of Computation. [s.l.] : Cengage Learning, 2005. 400 s. ISBN 0619217642.  
  • HOPCROFT, John. Introduction to Automata Theory, Languages, and Computation. [s.l.] : Pearson Education, 2007. ISBN 0321514483.  

Související články[editovat | editovat zdroj]