Teorie vyčíslitelnosti: Porovnání verzí
ještě jednou |
m {{Commonscat}} |
||
Řádek 18: | Řádek 18: | ||
* [[Gödelovy věty o neúplnosti]] |
* [[Gödelovy věty o neúplnosti]] |
||
* [[Intuicionistická logika]] |
* [[Intuicionistická logika]] |
||
== Externí odkazy == |
|||
* {{Commonscat}} |
|||
{{Pahýl}} |
{{Pahýl}} |
Verze z 4. 6. 2021, 21:43
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
- Nelze zkonstruovat algoritmus, který by pro obecný program ověřil konečnost jeho běhu (tzv. problém zastavení).
Zajímavé hypotézy/teze
- Ke každému (intuitivně představitelnému) algoritmu existuje ekvivalentní Turingův stroj (tzv. Church-Turingova teze).
- Tato teze se snaží spojit intuitivní pojem algoritmu s matematickou definicí Turingova stroje. Spojuje tak filozofický a matematický svět, a proto ze své podstaty není matematickým tvrzením.
Literatura
- 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
Externí odkazy
- Obrázky, zvuky či videa k tématu teorie vyčíslitelnosti na Wikimedia Commons