Churchova-Turingova teze

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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.

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)

Formálnější znění teze[editovat | editovat zdroj]

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í (kromě jiných), aby byl s Turingovým strojem ekvivalentní:

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

Související články[editovat | editovat zdroj]