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ý se dá 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]