Wikipedie

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

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
PavelTom (diskuse | příspěvky)
254 editací
intuitivnost algoritmu v Church-Turing. tezi
PavelTom (diskuse | příspěvky)
254 editací
ještě jednou
Řá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ý 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]]).
Řádek 6:
* Nelze zkonstruovat algoritmus, který by pro obecný [[počítačový program|program]] ověřil konečnost jeho běhu (tzv. [[problém zastavení]]).
 
== Zajímavé hypotézy/teze ==
* Ke každému algoritmu (vintuitivně intuitivnímpředstavitelnému) smyslu)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 ==
Citováno z „https://cs.wikipedia.org/wiki/Teorie_vyčíslitelnosti“