Churchova-Turingova téza sa týka konceptu efektívnej, systematickej alebo mechanickej metódy v logike, matematike a informatike. Je formulovaná ako opis intuitívneho konceptu vypočítateľnosti a vo vzťahu k všeobecným rekurzívnym funkciám sa častejšie nazýva Churchova téza. Odvoláva sa tiež na teóriu počítačovo vypočítateľných funkcií. Téza sa objavila v tridsiatych rokoch minulého storočia, keď počítače samotné ešte neexistovali. Neskôr bol pomenovaný po americkom matematikovi Alonsovi Churchovi a jeho britskom kolegovi Alanovi Turingovi.
Účinnosť metódy na dosiahnutie výsledku
Prvým zariadením, ktoré pripomínalo moderný počítač, bol Bombie, stroj vytvorený anglickým matematikom Alanom Turingom. Slúžil na dešifrovanie nemeckých správ počas druhej svetovej vojny. Ale pre svoju tézu a formalizáciu konceptu algoritmu použil abstraktné stroje, neskôr nazývané Turingove stroje. Diplomová práca prezentujezáujem pre matematikov aj programátorov, keďže táto myšlienka inšpirovala tvorcov prvých počítačov.
V teórii vyčísliteľnosti je Churchova-Turingova téza známa aj ako domnienka o povahe vyčísliteľných funkcií. Uvádza, že pre akúkoľvek algoritmicky vypočítateľnú funkciu na prirodzených číslach existuje Turingov stroj, ktorý ju dokáže vypočítať. Alebo inými slovami, existuje na to vhodný algoritmus. Známym príkladom účinnosti tejto metódy je test pravdivostnej tabuľky na testovanie tautológie.
Spôsob, ako dosiahnuť akýkoľvek požadovaný výsledok, sa nazýva „účinný“, „systematický“alebo „mechanický“, ak:
- Metóda je špecifikovaná ako konečný počet presných inštrukcií, každá inštrukcia je vyjadrená pomocou konečného počtu znakov.
- Prebehne bez chýb, požadovaný výsledok prinesie v určitom počte krokov.
- Túto metódu môže vykonať človek bez pomoci s akýmkoľvek zariadením okrem papiera a ceruzky
- Nevyžaduje si to pochopenie, intuíciu ani vynaliezavosť zo strany osoby, ktorá akciu vykonáva
Skôr v matematike sa neformálny termín „efektívne spočítateľný“používal na označenie funkcií, ktoré možno vypočítať pomocou ceruzky a papiera. Ale samotný pojem algoritmickej vypočítateľnosti bol intuitívnejší než čokoľvek konkrétne. Teraz bol charakterizovaný funkciou s prirodzeným argumentom, pre ktorú existuje výpočtový algoritmus. Jedným z úspechov Alana Turinga bolreprezentácia formálne presného predikátu, pomocou ktorého by bolo možné nahradiť neformálny, ak sa použije podmienka účinnosti metódy. Church urobil rovnaký objav.
Základné koncepty rekurzívnych funkcií
Turingova zmena predikátov na prvý pohľad vyzerala inak ako tá, ktorú navrhol jeho kolega. Ale vo výsledku sa ukázali ako ekvivalentné v tom zmysle, že každý z nich vyberá rovnakú množinu matematických funkcií. Church-Turingova téza je tvrdenie, že táto množina obsahuje každú funkciu, ktorej hodnoty možno získať metódou, ktorá spĺňa podmienky účinnosti. Medzi týmito dvoma objavmi bol ešte jeden rozdiel. Bolo to tak, že Church zvažoval iba príklady kladných celých čísel, zatiaľ čo Turing opísal svoju prácu ako pokrytie vyčísliteľných funkcií integrálnou alebo reálnou premennou.
Bežné rekurzívne funkcie
Pôvodná formulácia cirkvi uvádza, že výpočet možno vykonať pomocou λ-kalkulu. To je ekvivalentné použitiu generických rekurzívnych funkcií. Church-Turingova práca pokrýva viac druhov výpočtov, než sa pôvodne predpokladalo. Napríklad v súvislosti s celulárnymi automatmi, kombinátormi, registračnými strojmi a substitučnými systémami. V roku 1933 matematici Kurt Gödel a Jacques Herbrand vytvorili formálnu definíciu triedy nazývanej všeobecné rekurzívne funkcie. Používa funkcie, kde je možný viac ako jeden argument.
Vytvorenie metódyλ-kalkul
V roku 1936 Alonso Church vytvoril metódu určenia nazývanú λ-kalkulus. Bol spájaný s prirodzenými číslami. V rámci λ-kalkulu vedec určil ich kódovanie. V dôsledku toho sa nazývajú cirkevné čísla. Funkcia založená na prirodzených číslach sa nazývala λ-vypočítateľná. Existovala iná definícia. Funkcia z Churchovej tézy sa nazýva λ-vypočítateľná za dvoch podmienok. Prvá znela takto: ak bola vypočítaná na cirkevných prvkoch, a druhou podmienkou bola možnosť byť reprezentovaný členom λ-kalkulu.
V roku 1936, pred štúdiom práce svojho kolegu, vytvoril Turing teoretický model pre abstraktné stroje, ktoré sú teraz po ňom pomenované. Mohli vykonávať výpočty manipuláciou so znakmi na páske. Týka sa to aj iných matematických činností, ktoré sa vyskytujú v teoretickej informatike, ako napríklad kvantové pravdepodobnostné výpočty. Funkcia z Churchovej tézy bola až neskôr podložená pomocou Turingovho stroja. Spočiatku sa spoliehali na λ-kalkul.
Vypočítateľnosť funkcií
Keď sú prirodzené čísla vhodne zakódované ako postupnosť znakov, funkcia na prirodzených číslach sa považuje za Turingovu vypočítateľnú, ak abstraktný stroj nájde požadovaný algoritmus a vytlačí túto funkciu na pásku. Takéto zariadenie, ktoré v 30. rokoch minulého storočia neexistovalo, by sa v budúcnosti považovalo za počítač. Abstraktný Turingov stroj a Churchova téza predznamenali éru rozvojavýpočtových zariadení. Bolo dokázané, že triedy funkcií formálne definované oboma vedcami sa zhodujú. Preto sa v dôsledku toho oba výroky spojili do jedného. Výpočtové funkcie a Churchova téza mali tiež silný vplyv na koncepciu vypočítateľnosti. Stali sa tiež dôležitým nástrojom pre matematickú logiku a teóriu dôkazov.
Odôvodnenie a problémy metódy
Na prácu sú protichodné názory. Pre „pracovnú hypotézu“, ktorú navrhli Church a Turing v roku 1936, sa zhromaždilo množstvo dôkazov. Ale všetky známe metódy či operácie na objavovanie nových efektívne spočítateľných funkcií z daných súviseli s metódami stavby strojov, ktoré vtedy neexistovali. Na potvrdenie Church-Turingovej tézy vychádzame zo skutočnosti, že každý realistický výpočtový model je ekvivalentný.
Vzhľadom na množstvo rôznych analýz sa to vo všeobecnosti považuje za obzvlášť silný dôkaz. Všetky pokusy o presnejšie definovanie intuitívneho pojmu efektívne vyčísliteľnej funkcie sa ukázali ako rovnocenné. Každá analýza, ktorá bola navrhnutá, dokázala vyčleniť rovnakú triedu funkcií, konkrétne tie, ktoré sú vypočítateľné Turingovými strojmi. Ukázalo sa však, že niektoré výpočtové modely sú efektívnejšie z hľadiska času a využitia pamäte pre rôzne úlohy. Neskôr sa zistilo, že základné koncepty rekurzívnych funkcií a Churchova téza sú skôr hypotetické.
Práca M
Je dôležité rozlišovať medzi Turingovou tézou a tvrdením, že čokoľvek, čo sa dá vypočítať výpočtovým zariadením, dokáže vypočítať aj jeho stroj. Druhá možnosť má svoju vlastnú definíciu. Gándhí nazýva druhú vetu „Téza M“. Znie to takto: „Čokoľvek dokáže vypočítať zariadenie, môže vypočítať Turingov stroj.“V užšom zmysle práce ide o empirický výrok, ktorého pravdivosť nie je známa. Turingova práca a „práca M“sú niekedy zamieňané. Druhá verzia je vo všeobecnosti nesprávna. Boli opísané rôzne podmienené stroje, ktoré dokážu vypočítať funkcie, ktoré nie sú Turingovo vypočítateľné. Je dôležité poznamenať, že prvá téza nezahŕňa druhú, ale je v súlade s jej nepravdivosťou.
Obrátená implikácia práce
V teórii vyčísliteľnosti sa Churchova téza používa ako opis pojmu vyčísliteľnosti triedou všeobecných rekurzívnych funkcií. Američan Stephen Kleene dal všeobecnejšiu formuláciu. Nazval čiastočne rekurzívne všetky parciálne funkcie vypočítateľné pomocou algoritmov.
Obrátená implikácia sa bežne označuje ako Churchova obrátená téza. Spočíva v tom, že každá rekurzívna funkcia kladných celých čísel je efektívne vyhodnotená. V užšom zmysle práca jednoducho označuje takúto možnosť. A v širšom zmysle abstrahuje od otázky, či v ňom môže existovať tento podmienený stroj.
Kvantové počítače
Koncepty vyčísliteľných funkcií a Churchova téza sa stali dôležitým objavom pre matematiku, teóriu strojov a mnohé ďalšie vedy. Technológia sa však veľmi zmenila a stále sa zlepšuje. Predpokladá sa, že kvantové počítače dokážu vykonávať mnohé bežné úlohy s kratším časom ako moderné. Zostávajú však otázky, ako napríklad problém so zastavením. Kvantový počítač na to nedokáže odpovedať. A podľa Church-Turingovej tézy ani žiadne iné výpočtové zariadenie.
