Teorie vyčíslitelnosti: Porovnání verzí

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 30. 7. 2016, 06:53

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

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.

Související články

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

Verze z 18. 10. 2015, 08:29 editovat Jj14 (diskuse \| příspěvky) Prověření uživatelé 88 592 editací m →‎Související články: styl CAPS značka: editace z Vizuálního editoru ← Přejít na předchozí porovnání		Verze z 30. 7. 2016, 06:53 editovat zrušit editaci 89.29.20.218 (diskuse) →‎top: Drobná stylistická úprava Přejít na další porovnání →
Řádek 1:		Řádek 1:
	'''Teorie vyčíslitelnosti''' je [[věda\|vědní]] obor na pomezí [[matematika\|matematiky]] a [[informatika\|informatiky]], který zkoumá otázky [[algoritmus\|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ý program\|počítačové programy]]. Pod pojmem algoritmu se běžně rozumí mechanizovaný postup, který ~~se dá~~ realizovat třeba na [[Turingův stroj\|Turingově stroji]]. Významnou roli ve [[Filosofie\|filozofickém]] podložení teorie vyčíslitelnosti hraje [[Church-Turingova teze]], podle níž jsou všechny „rozumné“ výpočetní modely ekvivalentní Turingově stroji.		'''Teorie vyčíslitelnosti''' je [[věda\|vědní]] obor na pomezí [[matematika\|matematiky]] a [[informatika\|informatiky]], který zkoumá otázky [[algoritmus\|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ý program\|počítačové programy]]. Pod pojmem algoritmu se běžně rozumí mechanizovaný postup, který lze realizovat třeba na [[Turingův stroj\|Turingově stroji]]. Významnou roli ve [[Filosofie\|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í model\|výpočetních modelů]] – například [[Turingův stroj]], [[částečně rekurzivní funkce]], [[RAM stroj]] a [[Lambda kalkul]] (nebo [[kombinatorická logika]]).		Pro teoretický popis pojmu algoritmu se využívá množství [[výpočetní model\|výpočetních modelů]] – například [[Turingův stroj]], [[částečně rekurzivní funkce]], [[RAM stroj]] a [[Lambda kalkul]] (nebo [[kombinatorická logika]]).