350px|bélyegkép|jobbra|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?Dénes Tamás: A. M. Turing különös világa: A Turing-géptől a rejtjelfejtő Bombe-ig
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ébenOn Computable Numbers, with an Application to the EntscheidungsproblemExtract, 'On computable numbers, with an application to the Entscheidungsproblem' from Proceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937) 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).Colossus, the first large-scale electronic computer
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 350px|bélyegkép|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égreTuring Machine 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: 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; 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; 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.
bélyegkép|jobbra|400px|A Turing-gép sémája
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ő:
az aktuális cellába beír egy meghatározott szimbólumot, az olvasófej a társzalagon balra vagy jobbra lép, esetleg helyben marad, 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:
Szabályos megállás (terminálás): a gép leálló belső állapotba („stop-állapot”) kerül; „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 □, elemkilencessel (matematikai nevén egy kilenctagú elemrendszerrel) írható le, ahol:
a (külső) input-abc; az input-tárjelek halmaza; a (külső) output-abc; az output-tárjelek halmaza; az állapothalmaz vagy belső abc; 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 startjel vagy kezdőszimbólum (esetleg startszimbólum), ; □ az üres szimbólum, ami a szalag memóriacelláinak üres, szimbólummentes állapotát jelképezi, ; ezt nyomdatechnikai okok miatt néha -val jelöljük; a kezdőállapot; egy parciális (néha totális) függvény, 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 .
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 . 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 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 állapotban adott 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” görög betűk az angol letters (=betű) szó kezdőbetűjére utalnak; a nagy „szigma” görög betű az angol state (=állapot) szó kezdőbetűjére, az -beli szimbólumok a leolvasófej lehetséges mozgásirányaira ( jelöli a helybenmaradást), a kis „szigma” görög betű pedig arra, hogy ez a startállapot; a görög „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. é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.