Turing-gép

Entscheidungsproblem azaz eldönthetőségi probléma lehetséges-e általános algoritmust adni a matematikai problémák megoldására, vagy egyáltalán létezhet-e elvileg ilyen algoritmus?

A Turing-gép fogalmát Alan Turing angol matematikus dolgozta ki az 1936-ban megjelent On Computable Numbers, with an Application to the Entscheidungsproblem című cikkében a matematikai számítási eljárások, algoritmusok precíz leírására, tágabb értelemben pedig mindenfajta „gépies” problémamegoldó folyamat, automatikusan végrehajtható számítás, például az akkoriban még nem létező számítógépek működésének modellezésére. Erre az időszakra, a második világháború környékére tehető az ilyesfajta, a számítási eljárásokat azok különféle modelljein keresztül vizsgáló kutatások fellendülése, melyek végül a valódi számítógépek fejlesztésének máig tartó folyamatát elindították (Turing maga is részt vett egy valódi gép, a Colossus megépítésében).

A Turing-gép úgynevezett absztrakt automata: a valóságos digitális számítógépek nagyon leegyszerűsített modellje (részletesebben ld. következő fejezet). További jelentőségét az ún. Church–Turing-tézis adja, amely szerint a Turing-gép egy univerzális algoritmikus modell (ld. lentebb). Az ilyen egyszerű számítógépmodellek matematizált elméleteivel a matematika számítástudománynak nevezett eléggé fiatal tudományágának olyan részterületei foglalkoznak, mint például a számításelmélet.

A fogalom értelmezései, modelljei

Egy Turing-gép művészi ábrázolása. A Turing-gép egy absztrakt automata, ami egy végtelen nagy tárolókapacitással rendelkező, bármilyen hosszú ideig futni tudó »célszámítógép« , mellyel egyetlenegy beépített program hajtható végre

Ha elfogadjuk igaznak azt a kijelentést, hogy a Turing-gép nem más, mint az egyszerű számítógépek modellje, a Turing-gép kifejezésen még mindig két különféle, bár szorosan összetartozó dolgot is érthetünk, és általában szokás az is, hogy a kifejezésbe mindkét értelmet egyszerre belelássuk (de ez nem szükséges és nem is minden szerző teszi):

• A nem formális – informatikai modell: A Turing-gép jelentheti az egyszerű számítógépek informatikai modelljét. Ebben a felfogásban a Turing-gépet olyan fizikailag is megvalósítható egyszerű automata formájában szokás interpretálni, mely három, fizikailag létező tárgyként elképzelt, hardveres egységből áll: a szalagtárból (memória és input-output-perifériák), a vezérlőegységből (CPU) és az író-olvasó fejből (buszrendszer). Itt látszik, hogy a Turing-gép mennyire hasonlít a számítógépek felépítéséhez.
• Matematikailag a Turing-gépet mint egy öt-tíz elemből álló halmazrendszert szokás definiálni. Ebben az esetben a „hardveres” interpretáció elhagyható, és a Turing-gép és a vele kapcsolatos fogalmak elmélete formális elméletként közölhető (a részleteket ld. később).

A matematikai modell és egy valós gép között az a lényeges különbség van, hogy a fizikai gépek memóriája véges. Egy érdekes lehetőség, hogy a fizikai és az absztrakt modell is szimulálható akár egyszerű PC-k segítségével is.

A klasszikus Turing-gép informatikai modellje

A Turing-gépnek rengetegféle változata van, e szócikk az ún. klasszikus változattal (teljes nevén szalagtáras, egyszalagos, egyfejes, relatív címzésű, három címes, statikus programozású, véges ábécéjű, véges (állapotú) determinisztikus absztrakt automata) foglalkozik. Bizonyított matematikai tételek szerint a többi változat nagy része ekvivalens a klasszikus változattal – legalábbis ama tekintetben, hogy mit tud kiszámolni.

Ahogy fentebb mondtuk, e felfogásban a Turing-gépet fizikailag is megvalósítható egyszerű automata formájában képzeljük el, mely

• három nagyobb fizikai egységből („hardver”) áll:

1. egy cellákra osztott végtelenített papírszalag formában létező memóriából (szalagmemória, szalagtár, társzalag); minden cellában a gép által megértett nyelv betűi, azaz a Tár-abc egy-egy betűje van írva;
2. egy vezérlőegységből, mely a gép programját tartalmazza; a vezérlőegység különböző időpillanatokban különféle belső állapotokban létezhet;
3. egy író-olvasó fejből (I/O-fej), mely szimbólumokat ír vagy olvas a szalag celláira (ahogy a valóságos számítógépek betűket írnak ki a monitorra vagy a nyomtatóban lévő papírívre).

• továbbá egy „szoftveregységből”, ez az átmenettábla, ami vezérli a gép működését, megadva, hogy adott szimbólum beolvasásának hatására adott állapotban mit tegyen: hogyan mozogjon, milyen szimbólumot írjon a tárra, és milyen belső állapotba kerüljön.

A Turing-gép működése: A Turing-gépnek minden időben van egy aktuális pozíciója a memóriaszalagon, amely pozíciónál az aktuális cella helyezkedik el. Minden időben van egy állapota, amely az aktuális állapot. Az aktuális állapotok definiálása része a gép programozásának.

A gép minden lépésben beolvas egy szimbólumot a társzalag aktuális cellájából, ezután a program attól függően, hogy az aktuális állapota milyen és a beolvasott szimbólum a gép ábécéjének melyik betűje, a következő három lehetőség közül az egyiket írja elő:

• 1). az aktuális cellába beír egy meghatározott szimbólumot,
• 2). az olvasófej a társzalagon balra vagy jobbra lép, esetleg helyben marad,
• 3). a gép (vezérlőegysége) átvált az éppen aktuális állapotból (amelyben éppen van) egy másikra (az új állapot persze lehet ugyanaz mint az aktuális). Egy speciális állapot a „stop-állapot”, amely után a Turing-gép a programozása szerint megáll.

Az időbeli lefutást leírva a gép beolvas, változtat, mozog, és aztán ez a ciklus újra kezdődik: azon a cellán, amelyre mozgott, ismét beolvas, változtat, majd lép. Így megy ez, s eme folyamatnak a gép programozásától és az elvégzendő feladattól függően kétféle kimenetele lehet:

1. Szabályos megállás (terminálás): a gép leálló belső állapotba („stop-állapot”) kerül;
2. „Elszállás”: a gép végtelen ideig fut. A legegyszerűbb módon ez úgy lehet, hogy egy végtelen ciklusba kerül, de más módon is futhat végtelen ideig, mert egyszerűen sosem kerül stop állapotba.

A formális, matematikai modell

Alapelemek

Matematikailag a klasszikus Turing-gép, Turing-program vagy Turing-algoritmus egy $(\Lambda _{i},\Lambda _{o},\Sigma ,A,s,$ □,  $\sigma ,\delta ,\Phi )$ elemkilencessel (matematikai nevén egy kilenctagú elemrendszerrel) írható le, ahol

1. $\Lambda _{i}$ a (külső) input-abc; az input-tárjelek halmaza;
2. $\Lambda _{o}$ a (külső) output-abc; az output-tárjelek halmaza;
3. $\Sigma$ az állapothalmaz vagy belső abc;
4. $A$ a címek (címjelek) halmaza, melyek azt írják le, a gép a szalagon merre lép. Mindegy, hogy jelöljük őket, például legyen $A=\left\{\leftarrow ,\downarrow ,\rightarrow \right\}$;
5. $s$ a startjel vagy kezdőszimbólum (esetleg startszimbólum), $s\in \Sigma$;
6. □ az üres szimbólum, ami a szalag memóriacelláinak üres, szimbólummentes állapotát jelképezi, $u\in \Lambda _{i}$; ezt nyomdatechnikai okok miatt néha $u$-val jelöljük;
7. $\sigma \in \Sigma$ a kezdőállapot;
8. $\delta$ egy parciális (néha totális) függvény, $\delta :\left(\Lambda _{i}\times \Sigma \right)\mapsto \left(\Lambda _{o}\times \Sigma \times A\right)$
9. $\Phi \subseteq \Sigma$ az elfogadó vagy végállapotok halmaza.

Kötelezően feltesszük, hogy ha egy felhasznált szimbólum állapotjel, akkor nem lehet tárjel vagy címjel, és viszont, azaz hogy $\left[\left(\Lambda _{i}\cup \Lambda _{o}\right)\cap \Sigma \right]\cup \left[\left(\Lambda _{i}\cup \Lambda _{o}\right)\cap A\right]\cup \left[\Sigma \cap A\right]=\emptyset$.

Nyugodtan feltehető viszont (nem kötelezően, de megszorítást vagy lényegi, matematikai különbséget csak ritkán okoz), és az egyszerűség kedvéért általában fel is szokás tételezni, hogy egyrészt az input ábécé és az output ábécé megegyezik – a Turing gép „homogén”, mégpedig háromelemű: az „üres szimbólumot”, és mondjuk a 0-t és az 1-et tartalmazza. Az ilyen gépeket bináris bemenetű Turing-gépeknek nevezzük. Matematikailag ez azt jelenti, hogy $\Lambda _{i}=\Lambda _{o}:=\Lambda =\{0,1,$ □ $\}$. A legtöbb esetben azonban még célszerűbb a bővített bináris bemenetű Turing-gépeket vizsgálni: ezek ábécéje a fenti szimbólumokon kívül még egy * „elválasztójelet” is tartalmaz.

A gép működésének formális leírása

A $\delta$ kétváltozós és háromértékű átmenetfüggvény biztosítja, hogy ha a gép valamely működési fázis elején adott $s\in \Sigma$ állapotban adott $x\in \Lambda _{i}$ szimbólumot olvas be az aktuális cellából, akkor egyértelműen rendelkezésére álljon egy cellacím, egyértelműen kiírhasson egy outputszimbólumot abba cellába, ahová a cím szól, és egyértelműen átválthasson egy másik állapotba, tehát tényleg az átmenetfüggvény vezérli a gépet, hisz ez szabja meg a viselkedését, hogy milyen bemenetre milyen kimenetet ad.

A formális Turing-gép működésének matematikai lényege, hogy az egyes elemi működési fázisok mindegyikében, a kiinduló fázistól kezdve egészen a végső fázisig (ha van ilyen), a gép egy véges elemrendszerrel jellemezhető, ti. minden fázisban a gép egyértelműen jellemezhető az általunk megadott állapotjellemzőkkel, ezek:

• az aktuális cella tartalma, az aktuális szimbólum;
• az aktuális állapot;
• az előbbi kettő hatására (ti. függvényében) létrejövő output-szimbólum;
• az első kettő hatására létrejövő címzés;

E négy jellemző összessége (matematikailag természetesen egy négytagú elemrendszer, azaz rendezett elemnégyes) a Turing-gép aktuális konfigurációja. A gép működése során egy véges vagy végtelen, megszámlálható tagú konfigurációsorozat jön létre. Míg a Turing-gép, azaz egy algoritmus a Turing-gépek elméletében matematikailag egy formális elemnyolcas, addig a gép működése, vagyis egy-egy számítási eljárása, azaz az algoritmus egy konkrét megvalósulása semmi más, mint ez a megszámlálható tagú konfigurációsorozat.

Irodalmi megjegyzések, elnevezésváltozatok

A rövidítések és jelek szinte szerzőről szerzőre változnak, a mi motivációink a következők: a nagy $\Lambda$ „lambda” görög betűk az angol letters (=betű) szó kezdőbetűjére utalnak; a nagy $\Sigma$ „szigma” görög betű az angol state (=állapot) szó kezdőbetűjére, az $A$-beli szimbólumok a leolvasófej lehetséges mozgásirányaira ($\downarrow$ jelöli a helybenmaradást), a $\sigma$ kis „szigma” görög betű pedig arra, hogy ez a startállapot; a görög $\Phi$ „nagy fí” betű pedig a „final state” (=végállapot) angol kifejezés kezdőbetűjére. Az átmenetfüggvényt néha vezérlőfüggvénynek, állapotfüggvénynek is nevezik, és a legtöbb szerző a külső abc-t nem lambda-, hanem nagy szigmával (symbols) jelöli.

Példák

Összeadás az egyes számrendszerben

Az egyes számrendszerben minden pozitív egész számot felírhatunk egyesek (vonások, vagy valamilyen rögzített egyéb szimbólum) segítségével úgy, hogy annyi egyest írunk, ahányadik a szám a pozitív egészek 1,2,3,… sorozatában. Pl. $3_{(10)}=111_{(1)}$ érvényes.

Könnyű azt a formális Turing-gépet és átmenetfüggvényét elkészíteni, amely kettő vagy több egyes számrendszerbeli számot összead a következőképp: a gép szalagjára fel van írva két szám mint egyesek sorozata, úgy, hogy őket néhány * elválasztó szimbólum választja el. A gép „összeadja” ezeket a számokat egyszerűen úgy, hogy „egyesíti” a sorozatokat, kitörölve a köztük lévő elválasztójeleket.

Összeadó algoritmus megvalósítására több konkrét lehetőség is van. Egy ilyen Turing-gépet a következőképp tervezhetünk meg:

A következő feltevésekkel élünk: a gép leolvasófeje kezdetben mindig a szalagon balról az első nem üres, azaz 1-est tartalmazó cellán álljon, a számokat mindig egy * karakter válassza el, és az utolsó számot az jelzi, hogy utolsó 1-ese után csupa üres szimbólum következik, a legbaloldalibb és legjobboldalibb 1-esek közt pedig csupa egyes vagy * álljon, üres cella ne legyen. Ilyen tehát az input.

A gép a kezdőállapotban ($\alpha$) megkeresi az első elválasztójelet (*), ha megtalálja, átvált a $\beta$ állapotba, átírja 1-essé, és visszalép a számsorozat első 1-ese előtti üres celláig. Ekkor $\gamma$ állapotba lép, törli az első 1-est. Tehát az egész összeadandó sorozat eddig a legbaloldalibb egyessel csökkent, de közben az első csillag 1-esre változott, így az első két számot összeadtuk. A gép lépjen eggyel jobbra: ott szükségképp 1-est talál. Most majdnem ugyanaz a helyzet, mint kezdetben: az összeadandó számsor legbaloldalibb egyesén állunk, és össze kell adnunk a még összeadandókat (csak két szám már össze van adva, ennyivel közelebb a megoldás). Mivel ez tulajdonképp majdnem megint a kiinduló helyzetünk, „menjünk vissza alfába”, keressük meg a következő *-ot, ezt „bétában” írjuk felül 1-essel, „gammában” pedig töröljünk egy egyest a számsorozatunk elejéről. Ez a ciklus addig folytatódik, amíg az utolsó csillag el nem fogy: ezt a gép úgy tudja érzékelni, hogy az $\alpha$ állapotban jobbra lépkedve nem csillagba, hanem a sorozat végén lévő üres cellába ütközik. Ekkor váltsunk $\omega$ állapotba, mely a befejezendő állapot. Összeadtuk az összes számot.

Tehát Turing-gépünk, kereszteljük UNAD-1 névre, matematikailag egy $UNAD-1=(\Lambda _{i},\Lambda _{0},\Sigma ,A,1,$ □ $,\delta ,\Phi )$ nyolcas, ahol $\Lambda _{i}=\Lambda _{o}:=\Lambda =\{0,1,*,$ □ $,\}$, $\Sigma =\left\{\alpha ,\beta ,\gamma ,\delta \right\}$, $\Phi =\left\{\omega \right\}$

A gép $\delta$ átmenetfüggvényét táblázat alakban ábrázolva:

	□	1	*
α	(□, ω, ↓)	(1, α, →)	(*, β, ↓)
β	(□, γ, →)	(1, β, ←)	(1, β, ←)
γ		(□, α, →)
ω	STOP

A gép ábécéje tehát három szimbólumból áll, és négy állapotot használ. Valójában sem időkihasználás, sem összetettség tekintetében nem ez a legjobb algoritmus de nem foglalkozunk a javításával. Egyébként elvileg nem nehéz jobb algoritmust keresni: az ezen háromelemű ábécé feletti legfeljebb négy állapotú „nem-izomorf” Turing gépek (azaz a definiálható átmenetfüggvények) száma mindenképp véges, tehát „pusztán” az összes definiálható átmenetfüggvényt kell végignézni, hogy működik-e a fenti inputfeltételek mellett (egy durva becslés: a megvizsgálandó Turing-gépek száma biztosan kisebb mint

$\sum _{i=1}^{4}{\left(9i\right)}^{3\cdot \left(i-1\right)}$ $=$ $1+2^{3}3^{6}+3^{18}+6^{18}$ $=$
$=$ $101560344094738$ $\approx$ $10^{14}$ , tehát kb. százbillió Turing-gépnél többet biztosan nem kell megvizsgálnunk …

A Turing-algoritmusok megszámlálhatóak és felsorolhatóak

Az előbbi kiszámolt eredményre a következőképp lehet jutni: adott véges n elemű ábécé feletti 1<k-állapotú Turing-gép egyértelműen megadható egy átmenetfüggvénnyel. Ez olyan táblázat, melynek n oszlopa és k sora van, tehát n×k cellája. Minden cellában az átmenetfüggvény egy lehetséges értéke áll, egy elemhármas, mely egy külső, egy belső és egy címszimbólumból álló rendezett elemhármas, ilyen pedig n×k×3 db. van. Mármost bármely cellába elvileg bármely lehetséges elemhármas beírható (persze az így kapott átmenetfüggvények többsége olyan gépet eredményez, ami semmi értelmeset nem csinál, például ha minden kimenő állapot stop-állapot, de bizony ez is egy Turing-gép), tehát n×k×3 elem n×k-adosztályú variációjáról van szó. Ezek száma pedig (n×k×3)^n×k. A becslés javítható, ha a stop-állapotot nem számítjuk külön sornak (mert ha a gép stop-állapotba kerül, akkor már nem számít ki több átmenetfüggvény-értéket, az stopnak megfelelő táblázatsor üres), az így kapott eredmény n×k×3^n×(k-1). Azért is érdemes ezt részletesen taglalni, mert észre lehet venni mindebből, hogy az adott ábécé feletti izomorf Turing-gépek (ti. ezek osztályai) felsorolhatóak, vagyis adott ábécé felett megszámlálhatóan végtelen sok nem-izomorf (Turing-) algoritmus létezik!

A klasszikus Turing-algoritmusok matematikai osztályzása

Formális ekvivalencia

Két

$TM_{1}=\left({\Lambda _{i}}_{1},{\Lambda _{o}}_{1},{\Sigma }_{1},A,s_{1},\sigma _{1},u,\delta _{1},{\Phi }_{1}\right)$

és

$TM_{2}=\left({\Lambda _{i}}_{2},{\Lambda _{o}}_{2},{\Sigma }_{2},A,s_{2},\sigma _{2},u,\delta _{2},{\Phi }_{2}\right)$

Turing algoritmust izomorfnak nevezünk, ha léteznek olyan

$\lambda _{i}:{\Lambda _{i}}_{1}\mapsto {\Lambda _{i}}_{2}$, $\lambda _{o}:{\Lambda _{o}}_{1}\mapsto {\Lambda _{o}}_{2}$

és

$\sigma :\Sigma _{1}\mapsto \Sigma _{2}$

bijektív függvények, melyekre tetszőleges $i_{1}\in {\Lambda _{i}}_{1}$, $i_{2}\in {\Lambda _{i}}_{2}$, $o_{1}\in {\Lambda _{o}}_{1}$, $o_{2}\in {\Lambda _{o}}_{2}$, $\alpha _{1},\beta _{1}\in \Sigma _{1}$, $\alpha _{2},\beta _{2}\in \Sigma _{2}$, $a\in A$ esetén teljesül $\delta _{1}\left(i_{1},alpha_{1}\right)=\left(o_{1},beta_{1},a\right)\Leftrightarrow \delta _{2}\left(i_{2},alpha_{2}\right)=\left(o_{2},beta_{2},a\right)$.

A formalizmust félretéve, itt arról van szó, hogy ugyanúgy programoztuk a Turing-gépet, csak az állapotokat és esetleg az I/O szimbólumokat máshogy neveztük el.

Egyéb osztályzási módszerek

Rengeteg másféle ekvivalencia is definiálható, alapjául szolgálva a gépek további osztályzásának. Például vizsgálható, hogy az inputjelekből képezett összes véges sorozatok közül melyek azok, melyeket egy véges automata elfogad (ti. inputként adva ezt a sorozatot a gépnek, az szabályosan terminálni fog-e). Az ilyen véges $\Lambda _{i}$ ábécé betűiből álló betűsorozatok (nem biztosan véges) halmazát az automata által elfogadott nyelvnek nevezzük a $\Lambda _{i}$ ábécé felett, két Turing-automatát pedig ekvivalensnek nevezhetünk, ha ugyanazt a nyelvet fogadják el (sőt, nem is kell mindkettőnek klasszikus Turing-gépnek lennie, például lehet az egyik egy Neumann-automata, a másik egy nemdeterminisztikus Turing-gép is stb.). A számításelmélet ezen kívül foglalkozik a gépek időigény, tárigény vagy egy véletlenszám-generátor-igénybevétel szerinti osztályzásával is.

A Church-Turing-tézis

A Church–Turing-tézis egy, a múlt század harmincas éveiben megfogalmazott sejtés, miszerint minden formalizálható probléma, ami megoldható algoritmussal, az megoldható Turing-géppel is; azaz a Turing-gép a feladatmegoldó eljárások legáltalánosabb és a fenti értelemben legerősebb példája. A sejtést azért nem tételnek, hanem csak (hipo)tézisnek nevezik, mert nem matematikai tétel, ugyanis a „feladatmegoldó eljárás” nem mint definiált matematikai fogalom szerepel. Ugyanakkor szintén a harmincas években a „feladatmegoldó eljárás” fogalmát számtalan alakban sikerült formálisan megfoghatóvá tenni, de kiderült, hogy ezek a megfogalmazások is ekvivalensek a Turing-gépre épülő eljárásfogalommal. Ez azt jelenti, hogy a Turing-gép egy univerzális algoritmikus modell. Maga a Turing-gép tekinthető az algoritmus egy definíciójának. A tézis összefügg az erős mesterséges intelligencia elvi létével ill. lehetetlenségével is (vagyis, hogy az olyan szellemi minőségek, mint pl. az értelem, érzelem, gondolkodás; vajon csupán az algoritmusok tulajdonságai és elválasztható a hardvertől, vagy sem.)

Nem ismerünk olyan algoritmikus rendszert, amelyről tudnánk, hogy erősebb a Turing-gépnél, és a legtöbb algoritmikus rendszerre bizonyított, hogy gyengébb, vagy ekvivalens. A bizonyítottan Turing-ekvivalens algoritmikus rendszerek a következők:

• asszociatív kalkulusok
• rekurzív függvények osztálya
• a lambda-kalkulus függvény-osztálya
• formális nyelvek legáltalánosabb, kötetlen osztálya
• C, LISP, Java, Prolog, Pascal stb.

AVAGY a Parciálisan rekurzív függvény szócikk alatt:

A Church-Turing-tézis vagy Church-tézis az az állítás, hogy a parciálisan rekurzív függvények pontosan az (algoritmussal) kiszámítható függvények. Ez matematikailag ellenőrizhető állítássá válik, ha az algoritmussal kiszámíthatóság homályos fogalma helyett bármilyen más matematikailag precízen megadott függvényosztályt vizsgálunk, így igazolható például, hogy a parciálisan rekurzív és a Turing-géppel kiszámítható függvények egybeesnek.

Történelem

A múlt…

Turing 1936-ban dolgozta ki a Turing-gép fogalmát egy cikkében (On computable numbers, with an application to the Entscheidungsproblem). Az algoritmusok matematikai leírásán túl, e problémát általánosítva a logikai és a fizikai folyamatok, gondolkodás és cselekvés szintézisére törekedett. E célt szolgálta az úgynevezett (egyetemes vagy) univerzális Turing-gép teóriája. Ekkor merült fel az a máig nagy vitákat kiváltó kérdés, lehet-e hűen szimulálni, modellezni, sőt esetleg reprodukálni számítógép segítségével az emberi gondolkodást. Ha a gép társzalagja(i) elegendő hosszúságú(ak), bármi kiszámolható; az összes (jól meghatározott) feladat egyetlen (a szükséges programokkal ellátott) géppel. De hogyan rendszerezhetők, milyen szabályok alapján működnek a valóság matematikailag rendkívül nehezen vagy egyáltalán nem modellálható (uncomputable) szegmensei, például az emberi intuíció? E kérdésekre egy 1938-as esszében (Ordinal Logics) próbált választ adni, a későbbiekben viszont soha többé.

A második világháború táján több más, Turingtól függetlenül dolgozó szerző (például S. C. Kleene, A. Church, A. A. Markov, G. H. Mealy, Neumann János) is hasonló gondolatok kidolgozásán fáradozott. Máig Turing koncepciója a leginkább kutatott és oktatott, legalapvetőbbnek tekintett algoritmusmodell. A negyvenes években, elektronikai ismeretekkel felvértezve, Turing az elméleti számítógép gyakorlati megvalósításán, a Colossus megtervezésében és építésében munkálkodott, az angol titkosszolgálat kötelékében. Ez időszakban egyébként többen is építettek már számítógépet (az első digitális gépet Vincent Atanasoff és Clifford Berry, ill. az első programozható digitális gépet Konrad Zuse).

Ekkoriban már nem elsősorban az foglalkoztatta, hogy mire képtelen a Turing-gép, hanem a benne rejlő lehetőségeket tanulmányozta. „Mintha egy agyat építenénk” – nyilatkozta. Elképzelhetőnek tartotta, hogy a jövőben (az ezredfordulóig bezárólag) mesterséges intelligenciát (MI) hozzunk világra, amely átmenne a Turing-teszten. A korabeli neurológia eredményeire támaszkodva a mai neuronhálózatokat előlegező elméletet vázolt fel: ha egy mechanikus rendszer kellően komplex, akár a tanulás képességével is bírhat.

Egy automata Post és Turing szerint nem más, mint egy feketedoboz, amely véges sok állapottal rendelkezik. Számukra az volt a fontos, hogy leírják, milyen módon megy át az automata egy i-edik állapotából a j-edik állapotába. Az állapotváltozás a környezettel való kölcsönhatás révén jön létre, amelyet egy szalag reprezentál, amelyen a gép a fentebb már leírt módon lépked, olvas és ír. Turing bináris számjegyekből álló végtelen sorozatokat vizsgált, s arra a kérdésre keresett választ, hogy mely sorozatok állíthatóak elő. Az előállító szabálysor véges hosszúságú, az automata futási ideje végtelen, így állítva elő a végtelen jelsort. A Turing által bizonyított eredmény érdekes és váratlan volt. Egyrészt kiderült, hogy létezik univerzális automata, amely minden speciális géppel előállított sorozatot szintén képes előállítani, másrészt megmutatta, hogy minden speciális automata leírható véges hosszúságú utasítássorozattal. Ez az eredmény Neumann Jánost nagyon izgatta és 1947-ben erejét két területre kezdte el koncentrálni: egyrészt az önreprodukálásra képes berendezésre, másrészt a hibás alkatrészekből előállítható berendezések optimalizálására.

A jövő?…

A jövőben a Turing-gépek eszméje esetleg különféle matematikai és informatikai kiszámíthatósági paradigmák (például az algoritmusok párhuzamosítása) konkrét és gyors megvalósításához is használható lesz – elvben – mivel az információhordozó DNS és RNS-molekulák mint négybetűs társzalag, az őket kezelő enzimrendszer mint leolvasófej, és maga a sejt mint CPU tekinthetőek akár egy iszonyatosan gyorsan működő, és párhuzamosan kapcsolható (több sejt együtt) Turing-gépnek is. Elvben, mivel a géntechnológia és nanotechnológia nem áll azon a színvonalon, hogy tetszőleges összetételű és mennyiségű polinukleinsav-molekulákat, azaz tetszőleges inputot könnyen előállítsunk.

Változatok

• A Turing-féle automaták lehetnek determinisztikusak (DTG: determinisztikus Turing-gép) és indeterminisztikusak (N(D)TG: nem-determinisztikus Turing-gép). Az első esetben az átmenetfüggvény valódi függvény (balról jobbra egyértelmű reláció); a második esetben viszont egy általánosabb reláció. Megjegyezzük: annak ellenére, hogy az indeterminisztikus Turing-gépet már Turing is említi dolgozatában („non automatic” machine), később nem tekintették Turing-gépnek, és azt mondták, egy absztrakt automata alapértelmezés szerint véges állapotú és determinisztikus, de az utóbbi időben, a számításelmélet indeterminisztikus gépekre vonatkozó ágai olyan fejlődésnek indultak, hogy újabban az absztrakt automata fogalmába megint szokás beleérteni azt is, hogy az nem feltétlen determinisztikus.
• A klasszikus modell programozása statikus: ez azt jelenti, hogy működés közben nem módosul. A mesterséges intelligencia kutatói azonban vizsgáltak már dinamikusan programozott (azaz önmódosító) Turing-gépeket is, ezek helyett azonban később inkább a LISP nyelven programozott valódi gépekre összpontosítottak. A helyzet ugyanaz, mint előbb: a Turing-gép fogalmába szinte mindenkor automatikusan beleértjük azt, hogy statikusan programozott.
• A véges automata kifejezés azt jelenti, hogy az automatának véges sok állapota lehetséges.
• a Turing-gép jelentéktelennek látszó, valójában azonban egyik leglényegesebb eleme, hogy címzése relatív és háromcímes, legalábbis ez különbözteti meg a többi véges determinisztikus automatatípustól: a Neumann-osztályú vagy egyéb többdimenziós sejtautomatáktól, a Markov-, Moore- és Mealy-gépektől, az abszolút címzésű regisztergépektől és RAM-gépektől stb.
• A szakemberek vizsgáltak egy helyett több szalagot vagy leolvasófejet tartalmazó nem-klasszikus Turing-gépeket is. Ezekről azonban kiderült, hogy lényegében „ugyanazt tudják”, mint a klasszikus gép (u.is minden ilyen értelemben véve nem klasszikus modellhez mindenféle előképzettség nélkül is szerkeszthető egy velük „izomorf” klasszikus gép). Lásd a Turing-típusú automaták szócikket.
• Több szalagos gép esetén némely társzalag lehet pusztán olvasható (read-only, RO) vagy csak pusztán írható (write-only, WO), és az automaták (ti. a szalagok) lehetnek korlátozott címzésűek, például ha a gép elért egy cellát, előfordulhat, hogy az attól jobbra vagy az attól balra lévő cellákat már soha nem tudja olvasni; az ilyen szalagot egyirányúnak vagy unidirekcionálisnak nevezik (UD); a „normális” három című szalagot pedig kétirányúnak vagy bidirekcionálisnak (BD). Bebizonyítható, hogy a bidirekcionális és unidirekcionális szalagú, de egyéb tekintetben ugyanolyan automaták „ugyanazt képesek kiszámolni”, kiszámíthatóságelméleti értelemben ekvivalensek (noha az idő- és tárigény szempontjából némi eltérés lehetséges).

Kapcsolódó szócikkek

• Neumann-elvek
• absztrakt automata
• sejtautomata
• formális nyelv
• kiszámíthatóság-elmélet
• nem-determinisztikus Turing-gép
• Turing-kiszámíthatóság

Források

• Dömösi Pál, Falucskai János, Horváth Géza, Mecsei Zoltán, Nagy Benedek: Formális nyelvek és automaták
• Trahtenbrot: Algoritmusok és absztrakt automaták.
• J.I.Manyin: Bevezetés a kiszámíthatóság matematikai elméletébe. Budapest, 1986, Műszaki Könyvkiadó.
• Demetrovics–Denev–Pavlov: A számítástudomány matematikai alapjai. Budapest, 1999, Nemzeti Tankönyvkiadó.
• Papadimitriou, Christos H.: Számítási bonyolultság (Computational complexity). Győr, 1999, Novadat Bt. ISBN 963-9056-20-0.
• Rónyai–Ivanyos–Szabó: Algoritmusok. 1999, Typotex.
• Czirkos Zoltán: Turing gépei és a Brainfuck nyelv

Külső hivatkozások

• A Turing Machine - Overview (video)
• Visual Turing, a Turing machine interactive simulator/IDE (free software for Windows)
• Charles Petzold: The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine, 2008, ISBN 978-0470229057
• Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965; online: *Boolos, G. and Jeffrey, R., Computability and Logic, 2nd ed., Cambridge: Cambridge University Press, 1980.
• Rogozhin, Yurii: „A Universal Turing Machine with 22 States and 2 Symbols”, Romanian Journal Of Information Science and Technology, 1(3), 259-265, 1998. (surveys known results about small universal Turing machines)
• C++ Simulator of a Nondeterministic and Deterministic Turing Machine (free software).
• A Church-Turing tézis formalizációja (angolul) (PDF)
• George H. Mealy: A method for synthesizing sequential circuits, Bell System Technical Journal, 34(5):1045–1079, 1955.