Teorie vyčíslitelnosti

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

Teorie vyčíslitelnosti je 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 Churchova-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/teze

Ke každému (intuitivně představitelnému) algoritmu existuje ekvivalentní Turingův stroj (tzv. Churchova-Turingova teze). +more ::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

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top