4.5. Turing-gépek összefűzése

Egy konkrét feladat megoldása Turing-gép segítségével a legtöbb esetben nem nyilvánvaló. Megadható azonban néhány művelet a Turing-gépeken, amelyek segítségével Turing-gépek felhasználásával új Turing-gépeket hozhatunk létre. Ezen műveletek hatásának megismerésével egyszerűbbé válik a modell használata, a bizonyítások megértése. Segítségével a jóval hétköznapibb eljáráselvű programozáshoz hasonló megoldásokat és gondolkodásmenetet követhetjük, megtartva a matematikai precizitás lehetőségét.

4.15. Definíció (Turing-gépek összefűzése [kompozíciója])

Legyen  és  két Turing-gép.
Tegyük fel, hogy .
A  (vagy  Turing-gépet a következőképpen definiáljuk:
, ahol , , ,
   és .
Itt

ahol
, minden  és  esetén, valamint
 minden  esetén és .

4.16. Megjegyzés

A  függvények uniója itt a 2. fejezetben értelmezett módon relációk 
uniójaként tekinthető.

4.17. Tétel

Az előbbi definícióban adott  Turing-gépre ,
azaz a  Turing-gép lényegében a  és  Turing-gépek egymás utáni 
"futtatásával" kapható meg.

Bizonyítás

Legyen egy tetszőleges hosszúságú szó, számítása a bemeneten ,

számítása a bemeneten . Ha megáll a bemeneten, legyen

és számítása a bemeneten .

A definíció alapján, mivel , így .

Ugyancsak a definíció szerint, ha , akkor , azaz ameddig , addig

.

Ez alapján, ha nem áll meg -n, akkor az sem áll meg.

Ha , ahol , akkor a Turing-gép megáll. Ebben az esetben

, azaz a szalag tartalma . definíciója alapján ilyenkor továbbszámol, a -nek

megfelelően, azaz először átmegy a $K=(s_t,w_1,a,w_2)$ konfigurációba, majd a következő lépések során

az író olvasó fejet a szalag elejére viszi. Ha azt eléri, átmegy a konfigurációba

- itt -, ami viszont megegyezik a konfigurációval. Mivel , ha ,

ezért innentől kezdve , azaz ha nem áll meg -n, akkor sem fog megállni, egyébként

pedig .

Figure 4.36.  és kompozíciója és és kompozíciója kompozíciója

és kompozíciója

Felismerő Turing-gépek segítségével a feltételes végrehajtás (feltételes eljáráshívás) struktúráját is modellezni tudjuk.

4.18. Definíció (feltételes elágazás)

Legyen ,  és  három Turing-gép.
Tegyük fel, hogy  ,  ,  ,
  ,   .
A  Turing-gépet a következőképpen definiáljuk:
, ahol ,
, ,
   és .
Itt 
, ahol
, minden  és  esetén,
, minden  és  esetén,
 minden  és  esetén valamint
, ahol .

4.19. Megjegyzés

Többszörös elágazás is definiálható, ha -et nem két, hanem 
több részre partícionáljuk, és mindegyiknek megfeleltetünk egy 
új Turing-gépet.

4.20. Tétel

Legyen  és  és a  válaszát jelöljük
  -gyel, ha a  bemeneten -beli állapotban, illetve
  -vel, ha a  bemeneten -beli állapotban áll meg.
Az előbbi definícióban adott  Turing-gépre
, ha  válasza a  bemeneten , illetve
, ha  válasza a  bemeneten .

Bizonyítás

Legyen egy tetszőleges hosszúságú szó, számítása a bemeneten ,

számítása a bemeneten . Ha megáll a bemeneten, legyen

és számítása a bemeneten ,

míg számítása a bemeneten .

A definíció alapján, mivel , így .

Ugyancsak a definíció szerint, ha , akkor , azaz ameddig , addig

.

Ez alapján, ha nem áll meg -n, akkor az sem áll meg.

Ha , ahol , akkor a Turing-gép megáll. Ebben az esetben

, azaz a szalag tartalma . definíciója alapján ilyenkor továbbszámol, a -nek

megfelelően.

a.) Ha , akkor először átmegy a konfigurációba, majd a következő lépések során

az író olvasó fejet a szalag elejére viszi. Ha azt eléri, átmegy a konfigurációba

- itt -, ami viszont megegyezik a konfigurációval. Mivel , ha ,

ezért innentől kezdve , azaz ha nem áll meg -n, akkor sem fog megállni, egyébként

pedig

b.) Ha , akkor először átmegy a konfigurációba, majd a következő lépések során

az író olvasó fejet a szalag elejére viszi. Ha azt eléri, átmegy a konfigurációba

- itt -, ami viszont megegyezik a konfigurációval. Mivel , ha

ezért innentől kezdve , azaz ha nem áll meg-n, akkor sem fog megállni, egyébként

pedig .

Figure 4.37.  , és feltételes kompozíciója, , és feltételes kompozíciója és , és feltételes kompozíciójafeltételes kompozíciója

, és feltételes kompozíciója

Amennyiben egy Turing-gépet előre megadott számban többször egymás után szeretnénk végrehajtani, egy kicsit pontosítani kell a definíción, mivel az egyszerű kompozíciónál feltettük, hogy az összefűzendő Turing-gépek állapothalmazai diszjunktak.

4.21. Definíció (rögzített ismétlésű ciklus)

Legyen  egy Turing-gép. A  Turing-gépet
definiáljuk úgy, hogy a  megfelelő komponenseit helyettesítjük egy 
megfelelő, -vel ellátott komponenssel. (Azaz átjelöljük az összetevőit.)
Ezzel a jelöléssel legyen .
Általánosan:
Legyen  és
, ha .

4.22. Megjegyzés

Az egyszerű összefűzés definíciója utáni tétel alapján . 
Iteratív módon alkalmazva , ahol az egymásba ágyazás 
mélysége . ( jelölése pontosan megegyezik a függvénykompozíciónál 
hagyományosan elfogadottal.)

A -nel jelölt Turing-gép a  Turing-gép -szer egymás után történő
végrehajtásaként értelmezhető. 

A programozásnál megszokott utasítások közül már csak a feltételes (végtelen) ciklus konstrukciója hiányzik.

4.23. Definíció (iteráció)

Legyen  és ,  .
A  Turing-gépet a következőképpen definiáljuk:
, ahol , , ,  és
.
Itt

, ahol
, minden ,  esetén,
,  és . 

4.24. Megjegyzés

Ha , akkor  semmilyen bemeneten nem áll meg 
(= végtelen ciklus).

4.25. Tétel

            ,
azaz  tekinthető a  Turing-gép iteratív végrehajtásának.

Bizonyítás

Legyen egy tetszőleges hosszúságú szó, számítása a bemeneten ,

számítása a bemeneten . Ha megáll a bemeneten, legyen

és számítása a bemeneten

A definíció alapján, mivel , így .

Ugyancsak a definíció szerint, ha , akkor , azaz ameddig , addig

Ez alapján, ha nem áll meg -n, akkor az sem áll meg.

Ha , ahol , akkor a Turing-gép megáll. Ebben az esetben

, azaz a szalag tartalma .

definíciója alapján, ha , akkor továbbszámol, a -nek

megfelelően, ha , akkor megáll.

Ha tehát , akkor először átmegy a konfigurációba, majd a következő lépések során

az író olvasó fejet a szalag elejére viszi. Ha azt eléri, átmegy a konfigurációba

- itt -, ami viszont kezdőkonfigurációja a bemenőszóval.

Innentől kezdve , azaz pontosan úgy viselkedik, mintha -t a bemeneten

indítottuk volna..

Figure 4.38.  iterációja iterációja

iterációja

4.26. Megjegyzés

A különböző típusú összefűzések definíciójából elhagyhatjuk az 
író-olvasó fej előremozgatását. Ebben az esetben a következő 
Turing-gép végrehajtása a szalag azon pozíciójából folytatódik,
ahol az előző abbahagyta a számolást. A legtöbb esetben ez a 
változat könnyebben használható, így viszont a függvények 
kompozíciójaként való értelmezés nem lenne helytálló.

Ezen összefűzések segítségével, ahogy a definíciók előtt is említettük, egyszerűbb Turing-gépekből komplikáltabb és komplikáltabb gépeket építhetünk, úgy tekintve az építőelemekre, mintha eljárások lennének.

Ilyen egyszerűbb gépek (a teljesség igénye nélkül) a következők lehetnek:

Összetett Turing-gépek

Példa:

Legyen a lehetséges bemenő szavak halmaza és legyenek adottak a következő egyszerű Turing-gépek:

1. : megvizsgálja az író-olvasó fej alatti jelet; ha az , akkor "igen", ellenkező esetben "nem" választ ad.

2. : megvizsgálja az író-olvasó fej alatti jelet; ha az , akkor "igen", ellenkező esetben "nem" választ ad.

3. : megvizsgálja az író-olvasó fej alatti jelet; ha az , akkor "igen", ellenkező esetben "nem" választ ad.

4. : egy cellát balra lép

5. : egy cellát jobbra lép

6. : -t ír a szalagra

7. : -et ír a szalagra

8. : -et ír a szalagra

Konstruáljuk meg belőlük az összefűzési műveletek segítségével azt a Turing-gépet, amelyik a bemenő szóból elkészíti a szót!

Először készítsük el azt a Turing-gépet, amelyik a szalagon levő szó (jobboldali) végére áll:

.

Hasonlóan adható meg a szó elejére álló is:

Az a Turing-gép, amelyik jobbra haladva megkeresi az első jelet, a következőképpen adható meg:

.

Az a Turing-gép, amelyik balra haladva megkeresi az első jelet, a következőképpen adható meg:

.