Church-Turingova teze
Z Wikipedie, otevřené encyklopedie
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:
- 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 vrátí výsledek po konečném počtu kroků.
- Algoritmus může provádět i člověk s tužkou a papírem.
- 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.

