4.3. Turing-gépek megadása

Egy Turing-gép megadása a definícióban szereplő ötös leírását jelenti. és esetében ez nem jelent különösebb kihívást, viszont az átmenetfüggvény meghatározása kicsit több erőfeszítést igényel. Mivel azonban véges halmazon értelmezett, véges halmazba képező függvényről van szó, szerencsére több egyszerű lehetőségünk is adódik rá.

A különböző reprezentációk használatát két Turing-gép különböző megadásával szemléltetjük.

Az első Turing-gép által megvalósított feladat a ábécé fölötti szavakon végrehajtott paritásellenőrző bites kódolás. Ez egy tipikus transzformációs feladat. Kezdőszelettartó, viszont nem hossztartó átalakítás. A leképezés lényege, hogy a bemenő szóban megszámoljuk az jeleket és a szót kiegészítjük egy új jellel úgy, hogy a keletkezett szóban az -esek száma páros legyen. Ez a transzformáció az egyik legegyszerűbb, de az egyik leghatékonyabb és széles körben alkalmazott hibafelismerő kódolás.

Pl. Paritásbit hozzáfűzése:

Be: Ki:

Be: Ki:

A tényleges alkalmazásoknál általában feltételezik, hogy az egyes kódszavak azonos hosszúságúak, de a példában nem élünk ezzel a megszorítással.

A második Turing-gép segítségével azt ellenőrizzük, hogy a bemenő szó megfelel-e a paritási feltételnek, azaz páros sok található benne. Ha igen, akkor elfogadjuk, ha nem, akkor sérültnek tekintjük.

4.3.1. Táblázatos reprezentáció:

A táblázatos reprezentációban az átmenetfüggvényt többféleképpen is megadhatjuk. Egyik lehetőség, hogy a táblázat oszlopait állapotokhoz, sorait bemenetekhez (az író-olvasó fej által beolvasott értékekhez) rendeljük, a cellák tartalma pedig a függvényértékeket tartalmazza a megfelelő argumentumok esetén.

A táblázat természetesen hiányos is lehet, amennyiben az átmenetfüggvény nem mindenütt definiált.

Pl. Paritásbit hozzáfűzése

A szakasz elején megadott feladat megoldására alkalmas Turing-gép a következő:

ahol , , és :

Figure 4.2. Paritásellenőrző bit hozzáfűzése a bemenő szóhoz

Paritásellenőrző bit hozzáfűzése a bemenő szóhoz

A Turing-gép állapota végállapot, a kezdő állapot és egyben annak jelzésére szolgál, hogy az eddig megvizsgált jelsorozatban páros sok található. A állapot jelentése, hogy az eddigi vizsgálatok során páratlan sok található. A és állapotok az író-olvasó fej továbbítására és a paritásérték megjegyzésére szolgálnak.

Egy konkrét bemeneten a Turing-gép a következő számítást végzi el:

Be:

Figure 4.3. Kezdő konfiguráció: Kezdő konfiguráció:

Kezdő konfiguráció:

Figure 4.4. 


Figure 4.5. 


Figure 4.6. 


Figure 4.7. 


Figure 4.8. 


Figure 4.9. 


Figure 4.10. 


Figure 4.11. 


Figure 4.12. 


Figure 4.13. 


Figure 4.14. 


Figure 4.15. 


Figure 4.16. 


Látható, hogy a Turing-gép számításának leírása így meglehetősen kényelmetlen, bár könnyen feldolgozható. Sokkal egyszerűbb az eredeti definíciónak megfelelően a konfigurációk leírásával megadni.

Figure 4.17. A Turing-gép számítása a A Turing-gép számítása a bemeneten bemeneten

A Turing-gép számítása a bemeneten

Pl. Paritásbit ellenőrzése

ahol , , és :

Figure 4.18. Paritásellenőrző bit tesztelése

Paritásellenőrző bit tesztelése

A Turing-gép állapota elfogadó-, míg elutasító állapot, azaz és a kezdő állapot és egyben annak jelzésére szolgál, hogy az eddig megvizsgált jelsorozatban páros sok található. A állapot jelentése, hogy az eddigi vizsgálatok során páratlan sok található. A és állapotok az író-olvasó fej továbbítására és a paritásérték megjegyzésére szolgálnak.

Egy konkrét bemeneten a Turing-gép a következő számítást végzi el:

Be:

Figure 4.19. Kezdő konfiguráció: Kezdő konfiguráció:

Kezdő konfiguráció:

Figure 4.20. 


Figure 4.21. 


Figure 4.22. 


Figure 4.23. 


Figure 4.24. 


Figure 4.25. 


Figure 4.26. 


Figure 4.27. 


Figure 4.28. 


Figure 4.29. 


Figure 4.30. 


Figure 4.31. 


Figure 4.32. 


Figure 4.33. 


Figure 4.34. 


A Turing-gép számításának leírása a konfigurációi segítségével:

Figure 4.35. A Turing-gép számítása a A Turing-gép számítása a bemenetenbemeneten

A Turing-gép számítása a bemeneten

4.3.2. Gráfreprezentáció:

4.3.3. Turing-gép megadása felsorolással:

Az átmenetfüggvény megadható a definiált argumentumokon felvett értékek felsorolásával is.

A paritásbit generáló Turing-gép átmenetfüggvénye:

A paritásbit ellenőrző Turing-gép átmenetfüggvénye:

4.3.4. Példák

1. A bemenő szót tükröző Turing-gép: .

2. A bemenő szót megduplázó Turing-gép: .

3. A bemenő szót, mint bináris számot eggyel megnövelő Turing-gép: , ahol .

4.3.5. Feladatok

1. Adjunk meg egy Turing-gépet, amelyik a szót írja a szalagra!

2. Adjunk meg egy Turing-gépet, amelyik a szót írja a szalagra!

3. Adjunk meg egy Turing-gépet, amelyik a bemenő szót invertálja, azaz minden -t -ra, minden -t -re cserél!

4. Adjunk meg egy Turing-gépet, amelyik a bemenő szóban páronként megcseréli a jeleket!

Pl.

5. Adjunk meg egy Turing-gépet, amelyik a bemenő szóról eldönti, hogy melyik jelből található több! Ha -ból, akkor , ha -ből, akkor , illetve ha egyenlőek, akkor állapotban áll meg.