Teorie vyčíslitelnosti: Porovnání verzí
Smazaný obsah Přidaný obsah
m Portálové šablony dle doporučení (s pomocí dat od Dannyho B.) |
m robot přidal: as, bn, uk odebral: fr, pt změnil: en, he |
||
| Řádek 26: | Řádek 26: | ||
[[ar:نظرية الحاسوبية]] |
[[ar:نظرية الحاسوبية]] |
||
[[as:কম্পিউটেবিলিটি থিয়ৰী]] |
|||
[[bn:গণনীয়তা তত্ত্ব (কম্পিউটার বিজ্ঞান)]] |
|||
[[ca:Teoria de la computabilitat]] |
[[ca:Teoria de la computabilitat]] |
||
[[de:Berechenbarkeitstheorie]] |
[[de:Berechenbarkeitstheorie]] |
||
[[en:Computability]] |
[[en:Computability theory]] |
||
[[es:Teoría de la computabilidad]] |
[[es:Teoría de la computabilidad]] |
||
[[fa:نظریه محاسبهپذیری]] |
[[fa:نظریه محاسبهپذیری]] |
||
[[he:תורת הרקורסיה]] |
|||
[[fr:Calculabilité]] |
|||
[[he:חישוביות]] |
|||
[[hr:Teorija izračunljivosti (računarstvo)]] |
[[hr:Teorija izračunljivosti (računarstvo)]] |
||
[[it:Teoria della calcolabilità]] |
[[it:Teoria della calcolabilità]] |
||
| Řádek 39: | Řádek 40: | ||
[[nl:Berekenbaarheid]] |
[[nl:Berekenbaarheid]] |
||
[[pl:Teoria obliczalności]] |
[[pl:Teoria obliczalności]] |
||
[[pt:Computabilidade]] |
|||
[[ru:Теория вычислимости]] |
[[ru:Теория вычислимости]] |
||
[[sh:Teorija izračunljivosti (računarstvo)]] |
[[sh:Teorija izračunljivosti (računarstvo)]] |
||
[[simple:Computability theory]] |
[[simple:Computability theory]] |
||
[[th:ทฤษฎีการคำนวณได้]] |
[[th:ทฤษฎีการคำนวณได้]] |
||
[[uk:Теорія обчислень]] |
|||
[[zh:可计算性理论]] |
[[zh:可计算性理论]] |
||
Verze z 24. 2. 2011, 16:27
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šechy „rozumné“ výpočetní modely ekvivalentní Turingově stroji.
Pro teoretický popis pojmu algoritmu využívá množství různých pojmů – například Turingův stroj, částečně rekurzivní funkce a intuicionistickou logiku.
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
- Ke každému algoritmu existuje ekvivalentní Turingův stroj (tzv. Church-Turingova teze).
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.