Churchova–Turingova teze

V teorii vyčíslitelnosti se pojmy Churchova–Turingova teze, Churchova teze a Turingova teze označuje hypotéza o povaze a výpočetní síle mechanických strojů počítajících matematické funkce. Teze je pojmenována po Alonzu Churchovi a Alanu Turingovi.

Hypotéza říká, že každý možný výpočet lze úspěšně uskutečnit algoritmem běžícím na počítači, je-li k dispozici dostatek času a paměti.

Požadavky kladené na algoritmus:

Algoritmus se skládá z konečného počtu instrukcí, které jsou přesně definovány použitím konečného počtu symbolů.
Algoritmus vždy po konečném počtu kroků vrátí výsledek.
Algoritmus může provádět i člověk s tužkou a papírem.
Spuštění algoritmu nepotřebuje lidskou inteligenci, kromě té, která je třeba na pochopení a vykonání instrukcí.

Tento popis algoritmu je sice intuitivně zřejmý, ale postrádá formální zázemí, jelikož není přesně popsáno, co znamená „přesně definovaná instrukce“ a co je „lidská inteligence potřebná na pochopení instrukcí“.

Neformálně řečeno, hypotéza tvrdí, že naše chápaní algoritmu je správné: vše, co lze počítačem (např. Turingovým strojem) vypočítat, lze vypočítat pomocí algoritmu a naopak. Navíc říká, že naše počítače jsou stejně „schopné“ jako jakékoli jiné stroje, které lze sestrojit. (Toto tvrzení ale nebere v úvahu rychlost a velikost paměti, což jsou v praxi velice důležité faktory.)

Formálnější znění teze

Teze může znít například takto:

„Ke každému algoritmu existuje ekvivalentní Turingův stroj.“

Kvůli neformální definici pojmu algoritmus nemůže být tato teze dokázána, šlo by ji ale vyvrátit, pokud by se podařilo vytvořit stroj schopný řešit problémy, které Turingův stroj řešit neumí (např. problém zastavení).

Jelikož každý počítačový program lze přeložit do jazyka Turingova stroje a také naopak (i když v praxi se to nedělá), lze tezi ekvivalentně formulovat pro kterýkoli běžně používaný programovací jazyk. Přesněji, programovací jazyk potřebuje aspoň jednu z následujících konstrukcí (kromě jiných), aby byl turingovsky úplný (tj. ekvivalentní Turingovu stroji):

cyklus while-do,
neomezenou (alespoň teoreticky) rekurzi,
podmíněný skok.

Běžné programovací jazyky mívají všechny tři tyto konstrukce. Mezi jazyky, které turingovsky úplné nejsou, patří SQL (myšleno bez uložených procedur) a Charity.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Churchova-Turingova teze na Wikimedia Commons