A Church-Turing tézis egy hatékony, szisztematikus vagy mechanikus módszer fogalmára utal a logikában, a matematikában és a számítástechnikában. A kiszámíthatóság intuitív fogalmának leírásaként fogalmazták meg, és az általános rekurzív függvényekkel kapcsolatban gyakrabban Church tézisének nevezik. Ugyancsak utal a számítógéppel kiszámítható függvények elméletére. A tézis az 1930-as években jelent meg, amikor maguk a számítógépek még nem léteztek. Később Alonso Church amerikai matematikusról és brit kollégájáról, Alan Turingről nevezték el.
A módszer hatékonysága az eredmény eléréséhez
Az első olyan eszköz, amely modern számítógépre hasonlított, a Bombie volt, egy Alan Turing angol matematikus által megalkotott gép. A második világháború idején német üzenetek megfejtésére használták. Téziséhez és az algoritmus fogalmának formalizálásához azonban absztrakt gépeket használt, amelyeket később Turing-gépeknek neveztek. A szakdolgozat bemutatjamind a matematikusok, mind a programozók érdeklődését, mivel ez az ötlet inspirálta az első számítógépek alkotóit.
A kiszámíthatóságelméletben a Church-Turing-tézis a kiszámítható függvények természetére vonatkozó sejtésként is ismert. Azt állítja, hogy minden természetes számokon algoritmikusan kiszámítható függvényhez létezik egy Turing-gép, amely képes kiszámítani. Vagy más szóval, létezik erre alkalmas algoritmus. A módszer hatékonyságának jól ismert példája a tautológia tesztelésére szolgáló igazságtáblázat-teszt.
A kívánt eredmény elérésének egyik módját „hatékonynak”, „szisztematikusnak” vagy „mechanikusnak” nevezzük, ha:
- A metódus véges számú pontos utasításban van megadva, minden utasítás véges számú karakterrel van kifejezve.
- Hiba nélkül fog futni, bizonyos számú lépésben a kívánt eredményt hozza.
- A módszert ember is elvégezheti segítség nélkül, papíron és ceruzán kívül bármilyen más eszközzel
- Nem igényel megértést, intuíciót vagy találékonyságot a cselekvést végző személytől
Korábban a matematikában a "hatékonyan kiszámítható" informális kifejezést a ceruzával és papírral kiszámítható függvényekre használták. De maga az algoritmikus kiszámíthatóság fogalma minden konkrétnál intuitívabb volt. Most egy természetes argumentummal rendelkező függvény volt jellemezve, amelyhez létezik számítási algoritmus. Alan Turing egyik eredménye az voltformálisan egzakt predikátum reprezentációja, amelynek segítségével a módszer hatékonysági feltétele mellett az informális helyettesíthető lenne. Church ugyanezt a felfedezést tette.
A rekurzív függvények alapfogalmai
Turing predikátumváltása első pillantásra másnak tűnt, mint a kollégája által javasolt. De ennek eredményeként ekvivalensnek bizonyultak abban az értelemben, hogy mindegyik ugyanazt a matematikai függvénykészletet választja ki. A Church-Turing tézis az az állítás, hogy ez a halmaz minden olyan függvényt tartalmaz, amelynek értékei a hatékonysági feltételeket kielégítő módszerrel megszerezhetők. Volt még egy különbség a két felfedezés között. Church csak a pozitív egészek példáit vette figyelembe, míg Turing úgy írta le munkáját, hogy a kiszámítható függvényeket integrálja vagy valós változókkal fedi le.
Gyakori rekurzív függvények
A Church eredeti megfogalmazása szerint a számítás elvégezhető a λ-kalkulus segítségével. Ez megegyezik az általános rekurzív függvények használatával. A Church-Turing tézis több fajta számítást fed le, mint azt eredetileg gondolták. Például sejtautomatákkal, kombinátorokkal, regisztrációs gépekkel és helyettesítő rendszerekkel kapcsolatban. 1933-ban Kurt Gödel és Jacques Herbrand matematikusok megalkották az általános rekurzív függvényeknek nevezett osztály formális meghatározását. Olyan függvényeket használ, ahol egynél több argumentum is lehetséges.
Módszer létrehozásaλ-számítás
1936-ban Alonso Church megalkotta a meghatározási módszert, az úgynevezett λ-kalkulust. Természetes számokhoz kapcsolták. A λ-számításon belül a tudós meghatározta a kódolásukat. Ennek eredményeként hívják őket egyházi számoknak. A természetes számokon alapuló függvényt λ-számíthatónak nevezték. Volt egy másik meghatározás is. A Church téziséből származó függvényt két feltétel mellett λ-számíthatónak nevezzük. Az első így hangzott: ha egyházi elemekre számították, a második feltétel pedig az volt, hogy a λ-kalkulus egy tagja képviselje.
Szintén 1936-ban, mielőtt kollégája munkáját tanulmányozta volna, Turing elméleti modellt készített a ma róla elnevezett absztrakt gépekhez. Számításokat végezhettek a szalagon lévő karakterek manipulálásával. Ez vonatkozik az elméleti számítástechnikában megtalálható egyéb matematikai tevékenységekre is, például a kvantumvalószínűségi számításokra. A Church téziséből származó függvényt csak később igazolták Turing-gép segítségével. Kezdetben a λ-számításra támaszkodtak.
A függvény kiszámíthatósága
Amikor a természetes számok megfelelően vannak kódolva karaktersorozatként, a természetes számokon lévő függvényt Turing-számítógépnek mondjuk, ha az absztrakt gép megtalálta a kívánt algoritmust, és ezt a függvényt szalagra nyomtatta. Egy ilyen eszköz, amely az 1930-as években nem létezett, a jövőben számítógépnek számítana. Az absztrakt Turing-gép és Church tézise a fejlődés korszakát hirdette megszámítástechnikai eszközök. Bebizonyosodott, hogy a két tudós által formálisan meghatározott függvényosztályok egybeesnek. Ezért ennek eredményeként mindkét állítást egyesítették. A számítási függvények és Church tézise is erősen befolyásolta a kiszámíthatóság fogalmát. A matematikai logika és a bizonyítási elmélet fontos eszközévé is váltak.
A módszer indoklása és problémái
Vannak ellentmondó nézetek a dolgozatról. Számos bizonyítékot gyűjtöttek össze a Church és Turing által 1936-ban felvetett "munkahipotézissel". De minden ismert módszer vagy művelet, amellyel az adottakból új, hatékonyan kiszámítható függvényeket lehetett felfedezni, összekapcsolódott a gépgyártási módszerekkel, amelyek akkor még nem léteztek. A Church-Turing tézis bizonyításához abból indulunk ki, hogy minden reális számítási modell egyenértékű.
A különféle elemzések sokfélesége miatt ezt általában különösen erős bizonyítéknak tekintik. A hatékonyan kiszámítható függvény intuitív fogalmának pontosabb meghatározására tett kísérletek egyenértékűnek bizonyultak. Minden javasolt elemzés bebizonyította, hogy a függvények ugyanazt az osztályát emeli ki, nevezetesen azokat, amelyeket a Turing-gépek számítanak ki. Néhány számítási modell azonban hatékonyabbnak bizonyult az idő és a memóriahasználat tekintetében a különböző feladatokhoz. Később megállapították, hogy a rekurzív függvények alapfogalmai és Church tézise meglehetősen hipotetikus.
M tézis
Fontos különbséget tenni Turing tézise és azon állítás között, hogy bármit, amit egy számítástechnikai eszköz ki tud számítani, azt a gépe is ki tudja számítani. A második lehetőségnek megvan a maga meghatározása. Gandhi a második mondatot "M tézisnek" nevezi. Ez így hangzik: „Amit egy eszköz ki tud számítani, azt a Turing-gép is ki tudja számítani.” A tézis szűkebb értelmében empirikus állításról van szó, amelynek igazságértéke ismeretlen. Turing tézisét és "M tézisét" néha összekeverik. A második verzió nagyjából hibás. Különféle feltételes gépeket írtak le, amelyek képesek olyan függvényeket kiszámítani, amelyek nem számíthatók Turing-rendszerrel. Fontos megjegyezni, hogy az első tézis nem foglalja magában a másodikat, de összhangban van annak hamisságával.
A tézis fordított implikációja
A kiszámíthatóság elméletében Church tézisét az általános rekurzív függvények osztálya általi kiszámíthatóság fogalmának leírására használják. Az amerikai Stephen Kleene általánosabb megfogalmazást adott. Részlegesen rekurzívnak nevezte az összes algoritmus által kiszámítható parciális függvényt.
A fordított implikációt általában Church fordított tézisének nevezik. Ez abban rejlik, hogy a pozitív egészek minden rekurzív függvénye hatékonyan kiértékelésre kerül. Szűk értelemben a tézis egyszerűen egy ilyen lehetőséget jelöl. És tágabb értelemben elvonatkoztat attól a kérdéstől, hogy létezhet-e benne ez a feltételes gép.
Kvantumszámítógépek
A kiszámítható függvények fogalma és Church tézise fontos felfedezéssé vált a matematika, a gépelmélet és sok más tudomány számára. A technológia azonban sokat változott, és folyamatosan javul. Feltételezhető, hogy a kvantumszámítógépek sok általános feladatot kevesebb idő alatt képesek elvégezni, mint a modern számítógépek. De kérdések maradnak, például a megállás probléma. Egy kvantumszámítógép nem tud rá válaszolni. És a Church-Turing tézis szerint nincs más számítástechnikai eszköz sem.
