Teorie vyčíslitelnosti , známá také jako teorie rekurzivních funkcí, je odvětví moderní matematiky , které leží na křižovatce matematické logiky , teorie algoritmů a informatiky , která vznikla jako výsledek studia pojmů vyčíslitelnost a ne - vyčíslitelnost. Zpočátku byla teorie věnována vyčíslitelným a nevyčíslitelným funkcím a porovnávání různých modelů počítání . Nyní se obor teorie vyčíslitelnosti rozšířil – objevují se nové definice pojmu vyčíslitelnost a dochází ke sloučení s matematickou logikou, kde namísto vyčíslitelnosti a nevyčíslitelnosti hovoříme o dokazatelnosti a nedokazatelnosti (odvoditelnosti a neodvozitelnosti) tvrzení v rámci jakýchkoliv teorií.
Teorie vyčíslitelnosti pochází z práce Alana Turinga ( 1936 ) „On Computable Numbers, With An Application to Entscheidungsproblem“, ve které představil koncept abstraktního počítače, který později dostal jeho jméno, a dokázal základní teorém o neřešitelnost problému jeho zastavení . Gödelův slavný teorém neúplnosti ( 1931 ) byl dokázán v podmínkách primitivních rekurzivních funkcí , jejichž třídu Gödel v roce 1934 rozšířil na třídu obecných rekurzivních funkcí . Ukázalo se, že formalismus vyvinutý Gödelem je ekvivalentní Turingovu (stejně jako mnoha dalším). Spolu s Church-Turingovou tezí tato skutečnost jasně demonstrovala obsah nové teorie a nyní jsou tyto definice obecně přijímány jako formální analogie algoritmicky vyčíslitelných funkcí.
Gödelova definice vypočitatelných funkcí měla syntaktický charakter a teprve stanovení koincidence této třídy s třídou obecných rekurzivních funkcí (spolu s formulací a „akceptací“ Churchovy teze) ukázalo skutečný význam věty o neúplnosti.Eršov, Jurij Leonidovič
| Logika | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Filosofie • Sémantika • Syntaxe • Historie | |||||||||
| Logické skupiny |
| ||||||||
| Komponenty |
| ||||||||
| Seznam booleovských symbolů | |||||||||
| Hlavní směry informatiky | |
|---|---|
| Matematické základy | |
| Teorie algoritmů | |
| Algoritmy , datové struktury | |
| Programovací jazyky , kompilátory | |
| Souběžné a paralelní výpočty , distribuované systémy | |
Softwarové inženýrství | |
| Architektura systému | |
| Telekomunikace , sítě | |
| Databáze | |
| Umělá inteligence |
|
| Počítačová grafika | |
Interakce člověka s počítačem |
|
| vědecké výpočty | |
| Poznámka: Informatiku lze také rozdělit do různých témat nebo oborů podle ACM Computing Classification System . | |