kedvenc szerzőim (David Deutsch, Roger Penrose és Douglas Hofstadter) mind a számításelmélet Church-Turing-Tézisével, és ami még fontosabb, annak legerősebb értelmezésével foglalkoznak: a Turing-elvvel. Ebben a bejegyzésben először az egyház-Turing tézist magyarázom laikus kifejezésekkel.
vissza, amikor dolgoztam a számítástechnika diplomát tanultam Turing gépek és a Church-Turing dolgozat az én Intro számításelmélet osztályban. Akkoriban azt hittem, hogy csak időpocsékolás. Csak számítógépeket akartam programozni, és egyáltalán nem érdekelt ez a rég halott Turing srác (sem ez a Templomos srác), sem a hülye elméleti gépei.
most, hogy megértem az egyház-Turing-tézis filozófiai következményeit, bárcsak figyeltem volna az osztályban! Mert az egyház-Turing tézisnek, ha igaz, van néhány mély filozófiai következménye, és elmondhat nekünk valamit a valóság mély és különleges természetéről is.
véges automaták
minden szövegek és osztályok a számításelmélet indul ki valami úgynevezett “véges automaták.”Az alapötlet mögöttük nagyon egyszerű. Képzeljünk el egy egyszerű ‘gépet’, amely képes döntéseket hozni és államok között mozogni. Íme egy példa egy nagyon egyszerűre, amely az érmével működtetett forgókapu “logikáját” képviseli.
egyszerű angol nyelven, ez azt mondja, hogy ha megpróbálja, hogy álljon át a forgóajtó, hogy zárva van, akkor nem, ha nem először hozott egy érmét. Ha betett egy érmét, de még nem tolta át, további érmék csak nyitva hagyják. Ha már fel egy érmét, akkor nyomja át. Ezután ismét bezáródik a következő személy számára.
valószínűleg könnyebb volt megérteni a diagramból, mint a leírásból.
a véges automaták ennél sokkal bonyolultabb logika végrehajtására képesek. De ennek alapvető érzést kell adnia arról, hogy a véges automaták hogyan működnek.
egy dolgot meg kell jegyezni, hogy a véges automata, mint a fenti, tisztán elméleti, mert csak buborékok és vonalak halmazaként létezik egy darab papíron. Ez nem olyan, mint van néhány kis “véges automata gép” belsejében forgóajtó, amely ezeket a döntéseket. Vagy talán inkább azt kellene mondanom,hogy maga a forgóajtó a véges automata.
ha igazán akarnánk, valószínűleg építhetnénk egy gépet a való életben, amely véges automata lenne.Semmi sem akadályozza meg valakit abban, hogy valódi gépként építse fel a való életben, majd telepítse a forgóajtóba. Ez nem a legolcsóbb módja ennek.
tehát bármely “program”, amelyet véges automata rajzaként készít, valódi “számítássá” alakítható, amely valóban működik. A ténylegesen létező számítástechnikai gép (mint egy véges automata) és a csak hipotetikus és a fizika törvényeit sértő gép közötti különbség fontossága egy pillanat alatt fontossá válik.
erősebb gépek
a számításelméleti osztály előrehaladtával a hallgatók egyre összetettebb ‘gépekkel’ ismerkedhetnek meg, amelyek erősebbek, mint a véges automaták. Amint a jobb oldali ábra mutatja, a következő legerősebb a Pushdown Automata (PDA). A PDA valójában csak egy DFA, egyfajta “memória”hozzáadásával. Ez a memória lehetővé teszi a PDA számára olyan számítások (vagy programok) létrehozását és futtatását, amelyeket a DFA nem tud.
a lényeg csak az, hogy vannak bizonyos típusú programok, amelyeket PDA-ra lehet írni, de nem írhatók determinisztikus véges automatára (DFA). Más szavakkal, a PDA – k “erősebbek”, mint a DFA-k, mert képesek olyan “programok” osztályait kifejezni, amelyeket a DFA-k nem tudnak.
tehát kapcsolat van a DFA-k és a PDA-k között a “számítási teljesítmény” szempontjából.”Nevezetesen be lehet bizonyítani, hogy bármely DFA-ra írt program PDA-ra is írható, de fordítva nem igaz.
a bizonyíték a bizonyítékban van
annak igazolása, hogy a PDA bármit futtathat, amit a DFA képes, úgy történik, hogy előáll egy sémával, amellyel a DFA logikája leképezhető egy PDA-ra. Mivel a PDA csak memóriával rendelkező DFA, ezt nem nehéz megtenni — csak ne használja a “memória funkciót”.
de mi a helyzet a fordított? Be tudjuk bizonyítani, hogy lehetetlen a PDA-ra írt bizonyos típusú “programokat” lefordítani DFA-ra? Vagyis van-e bizonyíték arra, hogy a Pushdown automatákat nem lehet leképezni egy véges automatához? Vagy csak azt feltételezzük, hogy egy véges Automata kevésbé erős, mint egy Pushdown Automata, mert jelenleg nem tudunk módot arra, hogy a PDA-t visszavezessük az FDA-hoz? Lehet, hogy van mód a PDA-k FDA-khoz való leképezésére, és talán még senki sem fedezte fel, hogyan kell ezt megtenni? Ez legalább egy lehetőség, nem?
mint kiderült, be lehet bizonyítani, hogy a PDA képes bizonyos típusú programokat futtatni, amelyeket a DFA nem tud. A módszer az lenne, ha találna egy számítást (pl. a program), hogy bizonyítani tudja, hogy a DFA nem tudja kiszámítani, majd bizonyítani, hogy a PDA képes kiszámítani.
egy gép számítási teljesítménye
ez a tény — hogy vannak erősebb (PDA) és kevésbé erős (DFA) logikai gépek — önmagában is érdekes.
de ez filozófiai kérdéshez vezet: van-e olyan dolog, mint a “legerősebb számítástechnikai gép?”
ha létezne egy ilyen “legerősebb gép”, honnan tudhatnánk, hogy bármely konkrét javasolt gép történetesen ” a legerősebb?”Vagy csak különböző típusú számítástechnikai gépek állnak rendelkezésre, és ki kell választani a megfelelőt a munkához?
Turing gépek
tehát melyik gép erősebb, mint egy PDA?
a történelem szerint körülbelül ugyanabban az időben két nagyon különböző típusú “gépet” javasoltak, amelyek bizonyíthatóan erősebbek voltak, mint a PDA-k.
az egyik Alan Turing Turing-gépe volt. A másik nem annyira gép volt, mint az Alonzo Church által kifejlesztett okos jelöléskészlet, amely ugyanazt a célt szolgálta, mint egy gép fejlesztése. E két ” gép ” közül a Turing-gépet fogalmilag könnyebb tanítani, tehát általában ezt a gépet tanítják a Számításelméleti tanfolyam.
a Turing-gépek vicces kis elméleti gépek, amelyek rendelkeznek író/olvasó fejjel és (hipotetikus) papírszalaggal, amelyről olvasni vagy írni tud. A Turing-gép olvasása alapján a Turing-gépet olyan akcióállapotba helyezi, amely valamilyen feladatkombinációt hajt végre, amely az olvasási/írási fej előre vagy hátra mozgatásából, a szalag új helyzetéből történő olvasásból, vagy új pozícióból történő írásból áll.a szalagon. Egy Turing-gép így néz ki:
Turing-gépek és Modern számítógépek
az egyik érdekes dolog az, hogy a Turing-gép a felszíni megjelenés ellenére valójában nagyon hasonlít egy modern számítógéphez. Egy modern számítógépben a központi feldolgozó egység (CPU) egyenértékű a Turing-gép író/olvasó fejével. A memóriachipek (RAM vagy ROM) nagyon hasonlítanak a hosszú papírszalag celláihoz, amelyekről az esztergagép képes olvasni vagy írni. Úgy tűnik tehát, hogy a modern számítógépek nagyjából egyenértékűek egy Turing-géppel.
egy modern számítógépnek van egy előnye a Turing-géppel szemben. A modern számítógépnek nem kell egymás után mozognia a “memória” egyik cellájából, mint egy Turing-gép.
az a tény, hogy egy Turing-gép egyszerre csak egy cellát tud mozgatni, jelentős korlátozásnak tűnik, nem? Most láttuk, hogy egyes gépek logikailag ‘erősebbek’, mint mások: a PDA képes olyan számítási feladatokat végrehajtani, amelyekre az FDA nem képes. Tehát talán vannak olyan gépek, amelyek erősebbek, mint a Turing-gépek, amelyek olyan feladatokat tudnak végrehajtani, amelyeket a Turing-gépek nem tudnak? És talán a modern számítógépek-mivel képesek a memória körül ugrálni, ahelyett, hogy egymás után celláról cellára kellene mozogniuk — futtathatnak olyan programokat, amelyekre egy Turing-gép nem képes?
valójában a modern számítógépnek valójában kevésbé kifejező ereje van, mint egy Turing-gépnek, mivel a Turing-gépeket végtelenül hosszú papírszalagnak (azaz végtelen memóriának) tekintették, ahol a való életben a számítógépnek mindig véges memóriája lesz. Általában azonban ez nagyon kevés különbséget jelent abban, hogy milyen típusú számításokat lehet végrehajtani, mivel az embereket általában nem érdekli a végtelenül hosszú számítások, amelyek végtelenül hosszú eredményeket adnak ki. Ezért mondom, hogy a modern számítógépek és a Turing-gépek “nagyjából” egyenértékűek. Valójában mindaddig, amíg bármilyen tetszőleges, de véges méretű memóriát feltételez, pontosan ekvivalensek abban a tekintetben, hogy milyen típusú programokat tudnak futtatni.
az egyház Turing tézis: Turing Machine = Max logikai teljesítmény
de mi a helyzet szegény Alonzo Church? Szegény kis “gépét” elfelejtették, mert a Turing-gépeket könnyebb tanítani. Lehet, hogy a gépe képes olyan számításokat /programokat kifejezni, amelyeket egy Turing-gép nem tud, vagy fordítva?
nem lenne egy csillag véletlen, ha csak úgy történt, hogy Alan Turing és Alonzo Church éppen így történt, hogy hozzon létre két teljesen különböző típusú elméleti számítás gépek és csak úgy történt, hogy azok pontosan azonosak szempontjából milyen típusú számítások tudnak végezni?
képzeljétek el mindenki meglepetését, amikor Alan Turing bizonyítékot tudott felmutatni arra, hogy bármely Turing-gépre írt program írható egyházi gépre is, és azt is, hogy bármely egyházi gépre írt program írható Turing-gépre is.
valójában számos javasolt elméleti számítási gép létezik. Például a teoretikusok megpróbálták megengedni, hogy egy Turing-gépnek több szalagja legyen az olvasáshoz/íráshoz. Még azt is megpróbálták engedélyezni egy Turing-gépnek, hogy 2 dimenziós ‘lapot’ tudjon írni és olvasni. A teoretikusok mindenféle fejlesztést kipróbáltak a Turing-gépeken (és az egyházi gépeken).
és eddig sikerült mindegyikre bizonyítani, hogy egyenértékűek egy egyszerű Turing-géppel.
ez vad véletlennek tűnik, nem? És ez vad véletlen lenne, hacsak nincs felső korlátozás arra, hogy milyen típusú számításokat lehet végrehajtani.
ha létezik egy ilyen felső határ, akkor egyáltalán nem lenne véletlen, hogy a Turing-gép és a Church-gép és az összes többi javasolt számítási gép véletlenül ugyanolyan számítási teljesítménnyel rendelkezik, mivel valójában azért egyenértékűek, mert elértük a számítási teljesítmény felső határát.
de be tudjuk — e bizonyítani, hogy nincs olyan számítástechnikai gép — amelyet még nem fedeztünk fel -, amely képes olyan számításokat végrehajtani, amelyekre egy Turing-gép nem képes?
pontosan hogyan állítanánk elő ilyen bizonyítékot? Az a tény, hogy nem tudjuk bizonyítani, hogy nincs semmi erősebb, mint egy Turing-gép. Szóval, ki tudja, talán van.
de tény, hogy nem találunk (vagy találunk) ilyen gépeket.
tehát a Turing-gépek erejének javítására irányuló próbálkozások és kudarcok után végül elfogadták az egyház-Turing-tézist, bár nem bizonyult igaznak. Az egyház-Turing tézis lényegében valami ilyesmit mond:
ez nem lehetséges, hogy dolgozzon ki bármilyen számítógépes gép, amely képes végrehajtani egy logikai program, hogy egy sima régi Turing gép nem.
vagy más szavakkal:
a Turing-gépek és azok megfelelői a lehető legerősebb számítási gépek, és nincsenek olyan erősebbek, amelyekről még nem tudunk.
évek óta tartó kutatás után ez a tézis alapvetően még mindig tart. Később látni fogjuk, hogy az elméleti kvantumszámítógépek bevezetésével némileg módosult a tézis. De alapvetően a tézis ma is igaz. Soha senki nem találta ki a módját, hogy felülmúlja a Turing-gépeket, amikor a logikai expresszivitásról van szó. A Turing gépek továbbra is az uralkodó bajnok.
tehát most már érted az egyház-Turing tézist. Az egyház-Turing tézis azonban valójában nem teljesen egyenértékű a Turing-elvvel. Tehát egy jövőbeli bejegyzésben kifejtem, mi a különbség, és mi a filozófiai következménye.
Megjegyzések
A Turing-Elv. Így nevezte Roger Penrose, aki nem hisz benne (legalábbis nem a jelenlegi formában). A Turing-Deutsch elvet David Deutsch fejlesztette ki, aki hisz benne, legalábbis az ő formájában.) (Lásd a Wikipedia cikkét további részletekért)