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^[3][4] 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).^[5]

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

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 lehetséges, 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 ${\displaystyle (\Lambda _{i},\Lambda _{o},\Sigma ,A,s,}$ □,  ${\displaystyle \sigma ,\delta ,\Phi )}$ elemkilencessel (matematikai nevén egy kilenctagú elemrendszerrel) írható le, ahol

1. ${\displaystyle \Lambda _{i}}$ a (külső) input-abc; az input-tárjelek halmaza;
2. ${\displaystyle \Lambda _{o}}$ a (külső) output-abc; az output-tárjelek halmaza;
3. ${\displaystyle \Sigma }$ az állapothalmaz vagy belső abc;
4. ${\displaystyle 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 ${\displaystyle A=\left\{\leftarrow ,\downarrow ,\rightarrow \right\}}$;
5. ${\displaystyle s}$ a startjel vagy kezdőszimbólum (esetleg startszimbólum), ${\displaystyle s\in \Sigma }$;
6. □ az üres szimbólum, ami a szalag memóriacelláinak üres, szimbólummentes állapotát jelképezi, ${\displaystyle u\in \Lambda _{i}}$; ezt nyomdatechnikai okok miatt néha ${\displaystyle u}$-val jelöljük;
7. ${\displaystyle \sigma \in \Sigma }$ a kezdőállapot;
8. ${\displaystyle \delta }$ egy parciális (néha totális) függvény, ${\displaystyle \delta :\left(\Lambda _{i}\times \Sigma \right)\mapsto \left(\Lambda _{o}\times \Sigma \times A\right)}$
9. ${\displaystyle \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 ${\displaystyle \left\cup \left\cup \left=\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 ${\displaystyle \Lambda _{i}=\Lambda _{o}:=\Lambda =\{0,1,}$ □ ${\displaystyle \}}$. 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 ${\displaystyle \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 ${\displaystyle s\in \Sigma }$ állapotban adott ${\displaystyle 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 ${\displaystyle \Lambda }$ „lambda” görög betűk az angol letters (=betű) szó kezdőbetűjére utalnak; a nagy ${\displaystyle \Sigma }$ „szigma” görög betű az angol state (=állapot) szó kezdőbetűjére, az ${\displaystyle A}$-beli szimbólumok a leolvasófej lehetséges mozgásirányaira (${\displaystyle \downarrow }$ jelöli a helybenmaradást), a ${\displaystyle \sigma }$ kis „szigma” görög betű pedig arra, hogy ez a startállapot; a görög ${\displaystyle \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. ${\displaystyle 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 (${\displaystyle \alpha }$) megkeresi az első elválasztójelet (*), ha megtalálja, átvált a ${\displaystyle \beta }$ állapotba, átírja 1-essé, és visszalép a számsorozat első 1-ese előtti üres celláig. Ekkor ${\displaystyle \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 ${\displaystyle \alpha }$ állapotban jobbra lépkedve nem csillagba, hanem a sorozat végén lévő üres cellába ütközik. Ekkor váltsunk ${\displaystyle \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 ${\displaystyle UNAD-1=(\Lambda _{i},\Lambda _{0},\Sigma ,A,1,}$ □ ${\displaystyle ,\delta ,\Phi )}$ nyolcas, ahol ${\displaystyle \Lambda _{i}=\Lambda _{o}:=\Lambda =\{0,1,*,}$Információ forrás: https://hu.wikipedia.org/wiki/Turing-gép
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.