Church-Turingova teze odkazuje na koncept efektivní, systematické nebo mechanické metody v logice, matematice a informatice. Je formulována jako popis intuitivního konceptu vyčíslitelnosti a ve vztahu k obecným rekurzivním funkcím je častěji nazývána Churchovou tezí. Odkazuje také na teorii počítačově vyčíslitelných funkcí. Teze se objevila ve 30. letech 20. století, kdy počítače samotné ještě neexistovaly. Později byl pojmenován po americkém matematikovi Alonsu Churchovi a jeho britském kolegovi Alanu Turingovi.
Účinnost metody k dosažení výsledku
Prvním zařízením, které se podobalo modernímu počítači, byl Bombie, stroj vytvořený anglickým matematikem Alanem Turingem. To bylo používáno k dešifrování německých zpráv během druhé světové války. Ale pro svou tezi a formalizaci konceptu algoritmu použil abstraktní stroje, později nazývané Turingovy stroje. Diplomová práce uvádízájem pro matematiky i programátory, protože tato myšlenka inspirovala tvůrce prvních počítačů.
V teorii vyčíslitelnosti je Churchova-Turingova teze známá také jako domněnka o povaze vyčíslitelných funkcí. Uvádí, že pro jakoukoli algoritmicky vypočítatelnou funkci na přirozených číslech existuje Turingův stroj, který ji dokáže spočítat. Nebo jinými slovy, existuje pro to vhodný algoritmus. Známým příkladem účinnosti této metody je test pravdivostní tabulky pro testování tautologie.
Způsob, jak dosáhnout jakéhokoli požadovaného výsledku, se nazývá „efektivní“, „systematický“nebo „mechanický“, pokud:
- Metoda je specifikována jako konečný počet přesných instrukcí, každá instrukce je vyjádřena pomocí konečného počtu znaků.
- Poběží bez chyb, v určitém počtu kroků vytvoří požadovaný výsledek.
- Metodu může provádět člověk bez pomoci s jakýmkoli jiným zařízením než papírem a tužkou
- Nevyžaduje pochopení, intuici ani vynalézavost ze strany osoby provádějící akci
Dříve se v matematice používal neformální termín „efektivně vyčíslitelný“pro označení funkcí, které lze vypočítat tužkou a papírem. Ale samotný pojem algoritmické vyčíslitelnosti byl intuitivnější než cokoliv konkrétního. Nyní byl charakterizován funkcí s přirozeným argumentem, pro kterou existuje výpočetní algoritmus. Jedním z úspěchů Alana Turinga bylreprezentace formálně přesného predikátu, s jehož pomocí by bylo možné nahradit neformální, pokud je použita podmínka účinnosti metody. Church učinil stejný objev.
Základní koncepty rekurzivních funkcí
Turingova změna predikátů na první pohled vypadala jinak než ta, kterou navrhl jeho kolega. Ale ve výsledku se ukázalo, že jsou ekvivalentní v tom smyslu, že každý z nich vybere stejnou množinu matematických funkcí. Church-Turingova teze je tvrzení, že tato množina obsahuje každou funkci, jejíž hodnoty lze získat metodou, která splňuje podmínky účinnosti. Mezi oběma objevy byl ještě jeden rozdíl. Bylo to tak, že Church zvažoval pouze příklady kladných celých čísel, zatímco Turing popsal svou práci jako pokrytí vyčíslitelných funkcí integrální nebo reálnou proměnnou.
Běžné rekurzivní funkce
Církevní původní formulace uvádí, že výpočet lze provést pomocí λ-kalkulu. To je ekvivalentní použití generických rekurzivních funkcí. Church-Turingova teze pokrývá více druhů počítání, než se původně předpokládalo. Například týkající se celulárních automatů, kombinátorů, registračních strojů a substitučních systémů. V roce 1933 vytvořili matematici Kurt Gödel a Jacques Herbrand formální definici třídy nazvané obecné rekurzivní funkce. Používá funkce, kde je možný více než jeden argument.
Vytvoření metodyλ-kalkul
V roce 1936 vytvořil Alonso Church metodu určování zvanou λ-kalkul. Byl spojován s přirozenými čísly. V rámci λ-kalkulu vědec určil jejich kódování. V důsledku toho se jim říká církevní čísla. Funkce založená na přirozených číslech se nazývala λ-vypočítatelná. Existovala jiná definice. Funkce z Churchovy teze se nazývá λ-vyčíslitelná za dvou podmínek. První zněla takto: pokud byl počítán na církevních prvcích, a druhou podmínkou byla možnost být reprezentován členem λ-kalkulu.
Také v roce 1936, před studiem práce svého kolegy, vytvořil Turing teoretický model pro abstraktní stroje, které jsou nyní po něm pojmenovány. Mohli provádět výpočty manipulací se znaky na pásce. To platí i pro další matematické aktivity, které se vyskytují v teoretické informatice, jako je kvantové pravděpodobnostní počítání. Funkce z Churchovy teze byla až později doložena pomocí Turingova stroje. Zpočátku se spoléhali na λ-kalkul.
Vyčíslitelnost funkcí
Když jsou přirozená čísla vhodně zakódována jako sekvence znaků, říká se, že funkce na přirozených číslech je Turingově vyčíslitelná, pokud abstraktní stroj našel požadovaný algoritmus a vytiskl tuto funkci na pásku. Takové zařízení, které ve 30. letech minulého století neexistovalo, by v budoucnu bylo považováno za počítač. Abstraktní Turingův stroj a Churchova teze ohlašovaly éru vývojevýpočetní zařízení. Bylo prokázáno, že třídy funkcí formálně definované oběma vědci se shodují. Proto se ve výsledku obě tvrzení spojila do jednoho. Výpočetní funkce a Churchova teze měly také silný vliv na koncept vyčíslitelnosti. Staly se také důležitým nástrojem pro matematickou logiku a teorii důkazů.
Odůvodnění a problémy metody
Na práci jsou protichůdné názory. Pro „pracovní hypotézu“navrženou Churchem a Turingem v roce 1936 bylo shromážděno mnoho důkazů. Ale všechny známé metody či operace pro objevování nových efektivně vyčíslitelných funkcí z daných souvisely s metodami stavby strojů, které tehdy neexistovaly. Abychom dokázali Church-Turingovu tezi, vycházíme ze skutečnosti, že každý realistický model výpočtu je ekvivalentní.
Vzhledem k rozmanitosti různých analýz je to obecně považováno za zvláště silný důkaz. Všechny pokusy o přesnější definici intuitivního pojmu efektivně vypočítatelné funkce se ukázaly jako ekvivalentní. Každá analýza, která byla navržena, dokázala vyčlenit stejnou třídu funkcí, jmenovitě ty, které jsou vypočitatelné Turingovými stroji. Ukázalo se však, že některé výpočetní modely jsou efektivnější z hlediska času a využití paměti pro různé úkoly. Později bylo poznamenáno, že základní koncepty rekurzivních funkcí a Churchova teze jsou spíše hypotetické.
Teze M
Je důležité rozlišovat mezi Turingovou tezí a tvrzením, že vše, co lze vypočítat výpočetním zařízením, může vypočítat jeho stroj. Druhá možnost má svou vlastní definici. Gándhí nazývá druhou větu „Thesis M“. Zní to takto: „Cokoliv dokáže spočítat zařízení, může spočítat Turingův stroj.“V úzkém smyslu teze se jedná o empirickou tezi, jejíž pravdivostní hodnota je neznámá. Turingova teze a „teze M“jsou někdy zaměňovány. Druhá verze je v podstatě nesprávná. Byly popsány různé podmíněné stroje, které mohou počítat funkce, které nejsou Turingově vyčíslitelné. Je důležité poznamenat, že první teze nezahrnuje druhou, ale je v souladu s její nepravdivostí.
Obrácená implikace práce
V teorii vyčíslitelnosti se Churchova teze používá jako popis pojmu vyčíslitelnost pomocí třídy obecných rekurzivních funkcí. Američan Stephen Kleene podal obecnější formulaci. Nazval částečně rekurzivní všechny parciální funkce vypočítatelné pomocí algoritmů.
Reverzní implikace je běžně označována jako Churchova obrácená teze. Spočívá v tom, že každá rekurzivní funkce kladných celých čísel je efektivně vyhodnocena. V úzkém smyslu teze takovou možnost jednoduše označuje. A v širším slova smyslu abstrahuje od otázky, zda v něm tento podmíněný stroj může existovat.
Kvantové počítače
Koncepty vyčíslitelných funkcí a Churchova teze se staly důležitým objevem pro matematiku, teorii strojů a mnoho dalších věd. Technologie se ale hodně změnila a stále se zlepšuje. Předpokládá se, že kvantové počítače mohou provádět mnoho běžných úkolů s kratší dobou než moderní počítače. Ale zůstávají otázky, jako je problém zastavení. Kvantový počítač na to nedokáže odpovědět. A podle Church-Turingovy teze ani žádné jiné výpočetní zařízení.
