Church-Turingova teze

V teorii vyčíslitelnosti se pojmy Church-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 disposici dostatek času a paměti.

Algoritmus musí splňovat následující požadavky:

1. 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ů.
2. Algoritmus vždy vrátí výsledek po konečném počtu kroků.
3. Algoritmus může provádět i člověk s tužkou a papírem.
4. Spuštění algoritmu nepotřebuje lidskou inteligenci, s výjimkou 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)

[editovat] Formálnější definice

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 nikdy dokázána, lze ji ale vyvrátit, podaří-li se sestrojit stroj, který bude umět ř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 obvykle i naopak, lze tezi ekvivalentně formulovat pro kterýkoli běžně používaný programovací jazyk. Přesněji, programovací jazyk potřebuje jednu z následujících konstrukcí, aby byl s Turingovým strojem ekvivalentní:

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

a běžné programovací jazyky mívají obojí. Mezi jazyky, které turing-ekvivalentní nejsou, patří SQL (myšleno bez vložených procedur) a Charity.