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 26. 12. 2007, 16:32

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 jeho konečnost (tzv. problém zastavení).

Zajímavé hypotézy

Ke každému algoritmu existuje ekvivalentní Turingův stroj (tzv. Church-Turingova teze).

Související články

Šablona:Matematický pahýl

@@ Řá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 [[filozofie|filozofickém]] podložení teorie vyčíslitelnosti hraje [[Church-Turingova teze]], podle níž jsou všechy „rozumné“ výpočetní modely ekvivalentní Turingově stroji.
-'''Teorie vyčíslitelnosti''' zkoumá hranice [[algoritmus|algoritmické]] konstrukce [[množina|množin]].
-Pro modelování využívá například [[Turingův stroj]], [[částečně rekurzivní funkce]] a [[intuicionistická logika|intuicionistickou logiku]].
+Pro teoretický popis pojmu algoritmu využívá množství různých pojmů – například [[Turingův stroj]], [[částečně rekurzivní funkce]] a [[intuicionistická logika|intuicionistickou logiku]].
 == Zajímavé výsledky ==
@@ Řádek 13: / Řádek 14: @@
 {{Matematický pahýl}}
 [[Kategorie:Vyčíslitelnost]]