Chapter 5. Kiszámíthatóság-elmélet

A kiszámíthatóságelmélet azzal a problémakörrel foglalkozik, hogy milyen módon lehetne a lehető legpontosabban megfogalmazni és körülírni az algoritmussal megoldható feladatokat. Megoldható-e egyáltalán minden feladat valamilyen algoritmussal? Van-e különbség megoldások között? Lehetséges-e, hogy egy feladatot csak részben lehet megoldani? Hogyan lehet ezt pontosítani, és mi a jelentése?

A vizsgálatokhoz szükségünk lesz néhány fogalomra. Az egyik ilyen az univerzális Turing-gép, a másik - pontosabban másik kettő - pedig a rekurzív - illetve rekurzív felsorolható - nyelvek fogalma.

5.1. Univerzális Turing-gép és az univerzális nyelv

A mindennapokban használatos számítógépeket univerzálisnak nevezzük azon tulajdonságuk miatt, hogy nem csak egy konkrét feladat megoldására használhatók, hanem bizonyos korlátok között tetszőleges célra. Ez a képességük azon múlik, hogy alapvető működésük kiegészítéseként programokat rendelhetünk hozzájuk, futtathatunk rajtuk. A Turing-géppel kapcsolatos vizsgálataink egyik kiindulópontja az volt, hogy ez a modell a Church-Turing tézis szerint minden algoritmus leírására alkalmas. Ennek megfelelően felvetődik a kérdés, hogy ha mindent leírhatunk vele, tekinthető az univerzális számítógéppel analógnak? Ennek vizsgálatához először is szükségünk van a tulajdonság pontos definíciójára.

5.1. Definíció

Legyen  egész. Egy  Turing-gépet univerzálisnak nevezünk 
a -szalagos Turing-gépekre nézve, ha minden  
               -szalagos 
Turing-géphez létezik  szó, amire  esetén. 
Itt   egy megfelelő elválasztójel.

Az előző definícióban leírt univerzális Turing-géptől tehát azt várjuk el, hogy az adott szalagszámhoz tartozó összes Turing-gépet legyen képes szimulálni egy megfelelő segédszó segítségével. A számítógépekkel való analógiát követve ez a segédszó tekinthető a Turing-gép programjának. Az egyszerűség kedvéért a későbbiekben ezt így is fogjuk nevezni.

A definícióhoz kapcsolódóan azonnal felvetődik a kérdés, hogy létezik-e egyáltalán ilyen Turing-gép valamilyen -ra. A választ a következő tétel adja meg.

5.2. Tétel

Minden  egész esetén létezik a -szalagos Turing-gépekre nézve 
univerzális Turing-gép.

Bizonyítás

A bizonyítás konstruktív.

Rögzítsük értékét. Hasonlóan a szimulációs tétel bizonyításához, ha a bizonyítás minden lépését precízen szeretnénk végrehajtani, nagyon sok apró technikai részletre kellene odafigyelnünk, ezért újfent csak a bizonyítás vázlatát nézzük meg.

A konstrukció során egy olyan Turing-gépet hozunk létre, amelyik képes tárolni a szimulálandó Turing-gép programját és annak aktuális konfigurációit is. Ezt olyan módon fogjuk megoldani, hogy az univerzális Turing-gépünket szalagosnak választjuk. Az első szalagot úgy használjuk, mint ha azok a szimulált Turing-gép szalagjai lennének. A . szalagon fogjuk tárolni a programot, a -en pedig a szimulált Turing-gép aktuális állapotát.

Az egyszerűség kedvéért tételezzük fel, hogy a szimulált Turing-gép szalag-abc-je is rögzített. Ez nem jelent különösebb megszorítást, hiszen jól ismert, hogy minden abc leképezhető a abc-re úgy hogy a különböző betűknek különböző azonos hosszúságú jelsorozatok felelnek meg. Ezáltal a leképezés egy egyértelműen dekódolható kódolást valósít meg, amivel a feladatok (nyelvek) a két abc között átalakíthatók.

Az univerzális Turing-gépet jelöljük -val.

Ahhoz, hogy a működését megértsük, először is a szimulálandó Turing-gép programját kell meghatároznunk.

A program lényegében a Turing-gép megadását, egészen pontosan átmenetfüggvényének felsorolásos leírását jelenti. Amilyen komponensei vannak, azokat egy egységesített nyelven leírjuk.

Legyen a szimulálandó Turing-gép ,

elemszáma és feleltessük meg elemeinek a számokat úgy, hogy -höz a -t rendeljük. A számokat megfelelő módon ábrázolhatjuk a abc-ben, viszont a bizonyítás során továbbra is a $q$ szimbólumokat fogjuk használni az állapotok jelölésére.

Ekkor a programjának szerkezete a következő:

, ahol és a átmenetfüggvény egy adott argumentumát és a felvett értékét tartalmazza. Egy ilyen egységet egy utasításának nevezünk. Pontosítva a leírást alakú, ha . A programban szükségszerűen az összes lehetséges argumentum esetére definiálnunk kell az utasításokat.

kezdő konfigurációjaként beállítjuk a szalagtartalmát az első szalagra, majd a . szalagra -t (azaz az -nek megfelelő állapotot) írunk.

működését a következő fázisokra bonthatjuk:

1. fázis: Megállási feltétel ellenőrzése.

Megvizsgáljuk, hogy szerepel-e a . szalag tartalma a felsorolt végállapotok között. Ha igen, végállapotba állítjuk a Turing-gépet. Ha nem, folytatjuk a 2. fázis végrehajtásával.

2. fázis: Állapotkeresés.

Ebben a fázisban, megkeressük a programszalagon a következő utasítást, amelyiknek argumentum részében szerepel a . szalagon tárolt állapot.

Mivel a Turing-gép definíciójánál feltételeztük, hogy minden konfigurációból tovább tudunk lépni, ha nem végállapotban van, ezért mindig fogunk ilyen utasítást találni.

3. fázis: Bemenet keresés.

Miután azonosítottuk, hogy a megfelelő állapothoz tartozó utasításnál járunk, leellenőrizzük, hogy az szalagokon az író-olvasó fej alatti szimbólumok megegyeznek-e az utasítás argumentumában szereplő megfelelő szimbólumokkal. Ha megegyeznek továbblépünk a 4. fázisba, ha nem, visszalépünk a 2-hoz.

4. fázis: Végrehajtás.

A megtalált végrehajtandó utasítás értékrészéből a benne szereplő állapotot a helyére másoljuk a . szalagon, majd az értékrész fennmaradó részének megfelelően az első szalagon a szükséges módosításokat (szimbólumok cseréje illetve író-olvasó fejek mozgatása) végrehajtjuk.

5. fázis: Következő lépés előkészítése.

A . és . szalagon az író-olvasó fejet előre mozgatjuk, majd folytatjuk a végrehajtást az 1. fázissal.

Látható, hogy az 1. fázis első konfigurációi kölcsönösen egyértelműen megfeleltethetők a szimulálandó Turing-gép számításának konfigurációinak. Ennek következtében a Turing-gép pontosan a számításának megfelelően változtatja az első és . szalag tartalmát. Megállni pontosan akkor áll meg, amikor a is megállna, a kimenete pedig ekkor megegyezik kimenetével.

Azaz tényleg a tételben megfogalmazottaknak megfelelő Turing-gépet konstruáltunk. ✓

5.3. Megjegyzés

Az előző fejezetben leírtak alapján minden -szalagos Turing-gép 
szimulálható -szalagossal. 
Az összes -szalagos Turing-gép szimulálható az -szalagos 
Turing-gépekhez tartozó univerzális Turing-géppel, amely szintén 
szimulálható egy -szalagossal. 
Ezek után megállapíthatjuk, hogy van olyan  szalagos Turing-gép, 
amelyik minden Turing-gépet tud szimulálni. Ha nem említjük külön, 
univerzális Turing-gépnek ezt a Turing-gépet fogjuk nevezni,
és -val fogjuk jelölni.

5.4. Definíció

A  univerzális Turing-gép által felismert nyelvet univerzális 
nyelvnek fogjuk nevezni, és -val jelöljük. Formálisan:
.

Az univerzális nyelv a definíciója szerint azon szavakból áll, amelyeket az univerzális Turing-gép elfogad. Az univerzális Turing-gép viszont azon szavakat fogadja el, amelyek alakúak, ahol egy Turing-gép programja, pedig egy olyan bemenet, amelyet a -hez tartozó Turing-gép elfogad. Ezek alapján, visszatérve az eredeti kiindulási vizsgálatainkhoz, úgy tekinthetjük, hogy az összes algoritmussal megoldható feladatot tartalmazza az összes megoldásával együtt. Érezhető, hogy egy meglehetősen összetett nyelvet definiáltunk univerzális nyelvként. Ráadásul a nyelv abból a szempontból extremális, hogy minden megoldható feladat-megoldás párt tartalmaz, így nem bővíthető tovább. Nem véletlen, hogy a későbbiekben alaposabban megvizsgálva, alapvető fontosságú eredményekhez jutunk általa.