9.2. A Turing-gépek megállási problémája és az algoritmikusan eldönthetetlen feladatosztályok kapcsolata

A matematikában és az informatikában gyakran foglalkozunk igen/nem problémaosztályokkal, vagyis olyan problémák osztályával, amelyeknél a megoldás mindig vagy "igen," vagy "nem." Ezeknél azt vizsgáljuk, hogy létezik-e algoritmus (kiszámítási mód) az illető osztály összes problémájának megoldására. Church tézise szerint egy Turing-géppel ekvivalens erejű számítási modellel, a parciális rekurzív függvénnyel kiszámítható feladatok tekinthetők effektíve kiszámíthatónak. Ezek szerint a Turing-gép a lehető legáltalánosabb számítási eszköz, azaz minden, ami effektíve kiszámítható, kiszámítható Turing-géppel is. Ez utóbbi átfogalmazást Church-Turing tézisnek is hívják a szakirodalomban. A Church tézist, miszerint az effektíve kiszámítható függvények osztálya megegyezik a parciális rekurzív függvények osztályával, Alonzo Church fogalmazta meg 1936-ban. (Még azt is hozzátette, hogy aki ezzel nem értene egyet, annak ez a tézis legyen kihívás.) Ezt a tézist, illetve annak ekvivalens megfelelőit, így a Church-Turing tézist is ma a szakemberek többsége elfogadja. Tézisről, tehát egy olyan nem bizonyított állításról van szó, melynek igazolása formális matematikai eszközökkel nem lehetséges. Érvényességét a gyakorlat verifikálja.

A Church-Turing tézis értelmében egy igen/nem problémaosztályt megoldhatónak hívjuk, ha létezik olyan rögzített algoritmus (Turing-gép), mely az osztály tetszőleges problémája mint bemenő adat esetén eredményként megadja a helyes "igen" vagy "nem" választ. 1936-ban Turing azt az akkor meglepő eredményt kapta, hogy létezik ebben az értelemben megoldhatatlan feladatosztály. Az eredeti bizonyítás helyett mi Minsky 1967-ben közölt bizonyítását tárgyaljuk.

Akkor mondjuk, hogy egy Turing-gép valamely input szó hatására megáll, ha az input szó eleme a tekintett Turing-gép által felismert nyelvnek, azaz az input szóhoz tartozó kezdő konfigurációból kiindulva eljut egy végkonfigurációba. Mondjuk azt, hogy a Turing-gépek megállási problémája megoldható, ha létezik olyan T M ' Turing-gép, melynek egy alkalmas kódolási algoritmussal egy tetszőleges T M Turing-gép leírását és a T M gép egy w input szavának kódolt alakját input szóként megadva megáll, s megállva a T M ' szalagján olyan szó keletkezik, melyre alkalmas dekódolási eljárást alkalmazva egyértelműen megállapítható, hogy wL T M ', avagy sem. Más szóval, egyértelműen megállapítható, hogy a leírt T M Turing-gép a kérdéses w szó mint input szó hatására el tud-e jutni egy végkonfigurációba, avagy sem. Ha ilyen T M ' Turing-gép nem létezik, akkor mondjuk azt, hogy a Turing-gépek megállási problémája megoldhatatlan.

73. Tétel. (Turing tétel) A Turing-gépek megállási problémája megoldhatatlan.

Bizonyítás. Először eltekintünk a bekódolás kérdésének vizsgálatától, s feltesszük, hogy létezik olyan általános kódolási algoritmus, mely tetszőleges T M Turing-gép és annak w input szava esetén megad a gép egy l(T M) leírását és a w által meghatározott alkalmas c(l(T M), w) kódolt alakot mint egy rögzített ábécé feletti szót.

A bizonyítás indirekt. Tegyük fel, hogy létezik olyan T M ' Turing-gép, mely a c(l(T M), w) szót input szóként megkapva

(a) megáll és ekkor az "IGEN" válasz kódolt alakja olvasható a szalagján, ha T M megálla w inputra,

(b) megáll és ekkor a "NEM" válasz kódolt alakja olvasható a szalagján, ha T M nem állmeg a w inputra.

Ha T M ' létezik, megszerkeszthető az a T M '' Turing-gép, mely az l(T M) input szó hatására előállítja a c(l(T M), l(T M)) input szót,

majd ezután erre az input szóra a T M ' Turing-gép működését utánozza egyetlen módosítással: valahányszor a T M ' igen megállást ér el, a T M '' gép egyszerű végtelen ciklusba esik. Figyelembe véve a T M ' eredeti viselkedését, kapjuk:

T M '' az l(T M '') input szó hatására pontosan akkor áll meg, ha T M '' a l(T M '') input szó hatására nem áll meg. Ez nyilvánvaló ellentmondás, amivel (feltételezve, hogy létezik az univerzális kódolási eljárás,) a tétel igazolást nyert. ∎

74. Tétel. Létezik univerzális algoritmus, mely izomorfizmustól eltekintve egyértelműen megadja bármely Turing-gép és annak input szava leírását.

Bizonyítás. A bizonyítás során alkalmazott meggondolást Gödel-számozásnak, a kódolt alakot pedig a Turing-gép Gödel számának hívjuk. Megjegyezzük, hogy ismeretesek ezen módszernél jóval hatékonyabb univerzális kódolási módszerek is. (Az ismertetett módszert Gödel eredetileg axiómarendszerek vizsgálatára használta fel.)

Ismeretes, hogy minden természetes szám sorrendtől eltekintve egyértelműen felírható prímhatvány tényezős alakba (azaz páronként különböző prímszámok hatványainak szorzataként). Ezt a tényt fogjuk felhasználni. Tekintsünk egy T M=(Q, T, V, q 0, #, d, F) Turing-gépet, s legyen q 0, …, q m-1 az állapotok egy olyan (kezdőállapottal kezdődő) felsorolása, ahol alkalmas 0 ≤ k ≤ m-1 mellett {q 0, …, q k }=QF. Jelölje továbbá a 1, …, a n a szalagábécé betűinek egy felsorolását, s végül legyen D 1=(q 0, a 1), …, D k+1=(q k , a 1), D k+2=(q 0, a 2), …, D 2(k+1)=(q k , a 2), …, D n(k+1)=(q k , a n ).

(Megtesszük azt a nem túl lényeges megjegyzést, hogy a q 0, …, q k és az a 1, …, a n felsorolások már egyértelműenmeghatározzák a D 1, …, D n(k+1) felsorolást. Utóbbi alkalmazását csupán a módszer könnyebb megértése kedvéért vezettük be.)

Képezzük az T M Turing-géphez és ezekhez az elrendezésekhez a

(tetszőlegesen rögzített számrendszerbeli, például tízes számrendszerbeli) természetes számot, aholis 2 hatványa az állapotok számát, 3 hatványa a nem-végállapotok számát, 5 hatványa a szalagábécé betűinek számát jelöli, s minden további , , , i=1, …, n(k+1) prímhatvány-hármas esetén, aholis alkalmas q s ∈{q 0, …, q k }(=QF), a t ∈{a 1, …, a n } mellett D i =(q s , a t ) áll fenn, (u i , v i , w i )=(0, 0, 0) ha d(q s , a t ) nincs értelmezve, ha pedig d(q s , a t ) értelmezve van, akkor d(q s , a t )=(q s', a t', Merre ) esetén u i =s '+1, v i =t ', továbbá, mondjuk, w i =1 ha Merre=Bal, w i =2 ha Merre=Jobb, illetve w i =3 ha Merre=Helyben. Az így meghatározott g T M számot a T M Turing-gép Gödel-számának fogjuk hívni. Amennyiben a w input szó w=a i 1 a i f alakú, a c(l(T M), w) kódolt alak legyen (a rögzített számrendszerbeli)

g T M (p n(k+1)+4) i 1 …(p n(k+1)+d ) i f

természetes szám. Látható, hogy a szóban forgó kódolás (izomorfizmustól eltekintve) egyértelmű, s ha a nyert c(l(T M), w) természetes szám például tízes számrendszerbenvan megadva, akkor egy alkalmas tizenegy bemenő jeles gépnek inputként megadható (tizenegyedik bemenő jel a szóköz jel). ∎

9.2.1. Univerzális Turing-gép

Ebben a részben a Turing-gépeknek egy speciális fajtájával, az ún. univerzális Turing-géppel fogunk foglalkozni.

Az univerzális Turing-gép többféleképpen is megadható, mi itt most az egyik ilyen megvalósítást mutatjuk be.

Az UTM Turing-gépet univerzálisnak nevezzük a Turing-gépek osztályára nézve, ha minden TM Turing-géphez van olyan vT *, hogy minden sT *- ra a TM futásának eredménye az s inputon megegyezik az UTM futásának eredményével a v X s inputon (ahol XVT ).

A TM "programja" v (az UTM nyelvén), s pedig egy tetszőlegesszó. Ha TM az s inputot kapja, akkor ugyanazt csinálja, mint UTM a v programmal az s- en.

Az univerzális Turing-gép tulajdonképpen egy általános, elvont számítógép, ami minden Turing-gépet képes szimulálni, vagyis elvileg a programjának megfelelően feldolgozni az input szót. Ez azt jelenti, hogy van olyan gép, ami minden kiszámítható függvényt ki tud számolni.

Az alábbiakban egy példát adunk az univerzális Turing-gépre.

Tulajdonképpen a d átmenetfüggvényt kell megadnunk ami a Q×V véges értelmezési tartományon és a Q×V×{B a l, J o b b, H e l y b e n} véges értékkészleten van értelmezve, illetve egy másik Turing-gép leírásának (program) kódolását.

Legyen TM valamilyen Turing-gép, melynek n darab belső állapotavan, és a szalagábécéje m betűt tartalmaz. Tegyük fel, hogy TM -etkódolt formában adtuk meg (jelölje [TM] ezt a leírást). A továbbiakban vázlatosan ismertetjük, hogy hogyan tudjuk modellezni TM működését egy UTM univerzális Turing-géppel. Tegyük fel, hogy TM a v inputon (ennek kódja [v] )dolgozik. Először azt kell megadnunk, hogy adott [TM] és [v] esetén ezeket az információkat miképpen tároljuk az UTM szalagján (azaz mi lesz UTM kezdőkonfigurációja), majd pedig azt, hogy ezek hatására UTM hogyan fog működni.

Jelöljünk ki a szalagon egy mezőt, és írjunk ebbe a mezőbe egy rögzített X jelet a szalagábécéből. A szalagnak a kiválasztottmezőtől jobbra eső felét három részre osztjuk. Az első részt nevezzük pufferterületnek; ez közvetlenül az X jel utánkezdődik, legalább n+m+2 mezőt tartalmaz, és ezek mindegyikébe 0van írva. A pufferterülettől jobbra eső szalagrész legelső mezőjébe egy Y jelet teszünk a szalagábécéből, utána beírjuk TM kódolt formáját, [TM]-et, három 0-t téve a végére. A szalagnak ezen részét nevezzük TM kódolási területének. A harmadik rész a második résztől jobbra helyezkedik el. Az első mezőjébe egy rögzített Z jelet írunk a szalagábécéből, majd a v bemeneti szó [v] kódolása következik. A szalagnak e három részen kívül eső mezői (kezdetben) üresek.

A pufferterület arra szolgál, hogy mialatt TM valamelyik lépését szimuláljuk, ide másolhassuk TM pillanatnyi belső állapotának, illetve az éppen leolvasott TM -beli szalagjelnek a kódját. Az Y jel általában az előtt a rendezett ötös előtt fog állni, amely azt határozza meg, hogy milyen belső állapotban van TM , milyen szalagjelet olvasunk éppen, mivel kell ezeket kicserélni (új állapot és új szalagjel), s eközben milyen irányban mozduljon el TM olvasófeje a szalagon. A Z jel az TM szalagjára felírt jelekközül jelöli ki azt, amelyiket éppen olvasunk.

Az UTM -ben lezajló számítási folyamatot, mellyel a TM Turing-gép működését szimuláljuk az v bemeneti szóval, olyan szakaszokrabonthatjuk, melyek sorra megfelelnek a TM egyes konfigurációi közötti átmeneteknek.

Az UTM működésének egy ilyen szakasza az alábbi módon zajlik le. Az UTM univerzális Turing-gép először a pufferterület elejére másolja azt az 1-esekből álló blokkot, amely közvetlenül az Y jel utánkövetkezik - nevezzük ezt Y- blokknak -, majd a végére odaír mégegy X jelet. Ezután kitörli Y- t, és jobbra haladva megkeresi a Z- t tartalmazó mezőt. Amikor ezt megtalálta, akkor a Z utánkövetkező 1-esekből álló blokkot ( Z- blokkot) is átmásolja apufferterületre az előbb beírt második X jel után, majdvisszaírja Y- t a TM kódolt leírása, [TM] elé. Így apufferterületre az aktuális belső állapot és a szalagról éppen beolvasott jel kódja került. A következő lépésekben UTM az Y jelután következő két 1-es blokkot hasonlítja össze a pufferterületen levőkkel. Ezáltal azt ellenőrzi, hogy a TM gép soron következő konfigurációátmenetét az a rendezett ötös határozza-e meg, amelynek kódja az Y jel után van leírva. Ha a blokkokmegegyeznek, ez azt jelenti, hogy megtaláltuk a keresett ötöst. Ha nem, akkor UTM áthelyezi az Y jelet a következő rendezett ötöskódolása elé, majd újrakezdi a blokkok összehasonlítását. Abban az esetben, ha a TM leírásában szereplő ötösök közül egyik sem felel meg, UTM leáll a működésével (az eredeti TM is ugyanezt tenné a v inputra). Ha viszont megtaláljuk a keresett ötöst, akkor UTM kitörli a pufferterületet, majd az Y jelet átteszi az ötösben szereplőharmadik elem elé. Ezután kicseréli a Z után következő blokkotaz Y utáni blokkal, majd Y- t jobbra mozdítja el a rendezettötös negyedik elem elé. Miután UTM leolvasta ezt a negyedik elemet is, mely a TM olvasófejének elmozdulási irányát határozza meg, UTM átteszi a jelet az elem mögé, az ötödik elem elé. Attól függően, hogy a negyedik blokkban két vagy csak egy darab 1-est talált-e, az UTM egy blokkal jobbra vagy egy blokkal balra tolja el Z- t. Ha Z eredetileg a szalagszó bal szélén volt, és TM -nek balra kellettlépnie, akkor UTM a szó kódolását jobbra tolja, és egy üres mező kódjelét írja be a Z után. Ha pedig Z a szalagszó jobb szélénállt, s jobbra kellene elmozgatni, akkor UTM a szó végére írja egy üres mező kódját. Amikor tehát mindezzel végeztünk, az Y jelután álló 1-es blokk a TM aktuális belső állapotát jelzi, a Z utáni blokk pedig azt a szalagjelet, amelyet TM -nek a következő lépésben be kellene olvasnia. Minden készen áll tehát arra, hogy a TM következő lépését szimuláló szakasz megkezdődhessen.

Az UTM működésének egyes szakaszai így TM egy-egy lépését modellezik. UTM ezeken kívül még a következőket hajtja végre: a munka legelején a szalag mindhárom részében a 0-kat a saját üres-jeleire cseréli, a munka végeztével pedig, olyankor, amikor TM leállna, UTM még ellenőrzi, hogy TM -nek végállapota-e az az állapot, amelyben megállt, és ettől függően kerül saját maga is végállapotba, ill. nem végállapotba.

Minden Turing-gép működése szimulálható olyan Turing-géppel, amiben a szalagábécé bináris, vagyis Σ={0, 1}.

Az Univerzális Turing-gép létezése azt mutatja, hogy elvileg konstruálható olyan számítási eszköz, amely programozható és mindent ki tud számítani, ami kiszámítható. A gyakorlati megvalósulás felé a következő lépés a Neumann elv, amit a következő alfejezetben ismétlünk át.

Az absztrakt számítógép után lássuk a valódi gépek milyen ezzel nagyon rokon elveken működnek.

9.2.1.1. A Neumann-elv

A hagyományos számítógépek atyjának tekinthetjük Neumann Jánost, aki sok más tudományos tevékenysége mellett, a klasszikus számítógépek működésének alapelveit is megadta.

Ezek az elvek, amelyeknek megfelelően épült a legtöbb számítógép, a következőek:

  • A program legyen a belső memóriában (tárolt program elve): A programot alkotó utasítások kifejezhetők számokkal, azaz adatként kezelhetők. Ezek a belső memóriában tárolhatók, mint bármelyik más adat. Ezáltal a számítógép önállóan képes működni, hiszen az adatokat és az utasításokat egyaránt a memóriából veszi elő. A memória a numerikus adatokkal együtt tárolja a programot is, a vezérlőegység pedig végrehajtja az utasítások sorozatát.

  • A számítógép használja a kettes számrendszert és legyen teljesen elektronikus: A kettes számrendszert és a rajta értelmezett aritmetikai ill. logikai műveleteket könnyű megvalósítani kétállapotú áramkörökkel (pl.: 1- magasabb feszültség, 0 - alacsonyabb feszültség).

  • A számítógép legyen soros (szekvenciális) működésű: A gép az egyes utasításokat egymás után, egyenként hajtsa végre.

  • A számítógépnek legyen belső memóriája: A számítógép gyors működése miatt nincs lehetőség arra, hogy minden egyes lépés után a kezelő beavatkozzon a számítás menetébe. A belső memóriában tárolhatók az adatok és az egyes számítások részeredményei, így a gép bizonyos műveletsorokat automatikusan el tud végezni.

  • A számítógép legyen univerzális: A számítógép különféle feladatainak elvégzéséhez nem kell speciális berendezéseket készíteni. Ugyanis Turing bebizonyította, hogy az olyan gép, amely el tud végezni néhány alapvető műveletet, elvileg bármilyen számítás elvégzésére is alkalmas (Turing-gép).

Láthatjuk, hogy a Turing-gép jó összhangban van a Neumann elvvel és ezért méltán tekinthető a számítógépek elméleti modelljének.