Megoldások a hatodik óra pótgyakorlatához

1. A diagonális nyelv komplementerében kétféle w szó van:
(1) a w nem kódol Turing gépet vagy
(2) a w Turing gépet kódol és az M_w Turing gép a w szót elfogadja.
Az első esetet könnyű felismerni, minden szóról el bírjuk dönteni, hogy kód-e vagy sem.
A második esetben tegyük a következőt: kezdjük el futtatni az M_w-t a w szón. Ha elfogadja, fogadjuk el mi is a w-t, ha az M_w elutasítja vagy nem áll meg, akkor ne álljunk meg mi se.
Az így működő Turing gép (tehát ami először ellenőrzi hogy a w szó kód-e és ha igen, akkor a fenti dolgot teszi) pontosan a kívánt nyelvet fogadja el.

2. A teljes feladatsorban szerepel a megoldás a Turing gépek 8. feladatnál.

3. Adunk egy Turing gépet, ami éppen ezt fogadja el és mindig megáll. Ha az x szó nem kódol Turing gépet, akkor utasítsuk el. Különben meg a következő van. Nyilván elég egybetűs szavakra leellenőrizni, hogy azokkal elindítva elmozdul-e a fej, hiszen a többi betű már csak akkor jönne, ha elmozdul, de akkor azonnal elutasítunk. Ezért nézzük csak az egybetűs szavakat (meg még az üreset, na jó), ezekből véges sok van. Az egyszalagos Turing gép állapotát mindig leírja és a további működését meghatározza, hogy milyen állapotban van, hogy mi van a szalagon és hogy hol áll a fej. Mivel most azt teszteljük, hogy elmegy-e a fej az első mezôrôl, (ha elmegy azonnal elutasítunk) ezért csak azt kell észrevennünk, hogy ha még nem ment el onnan, akkor csak az állapotát birja váltogatni, meg azt, hogy mi van az első mezôn. Ez összesen is csak |Q|x|T| lehetőség. Vagyis, ha ennyi lépést várunk egy szónál és még nem ment sehova, akkor már nem is fog, mert akkor biztos, hogy végtelen ciklusban van. (Miért is? Azért, mert akkor ugyanott áll a fej és olyan állapoptban van a gép illetve olyan betű van az első cellában, ami már egyszer volt, akkor innen kezdve ugyanazt csinálja már amit az előbb tett, azaz nem megy sehova.) Ha minden max. egybetűs szóra ez van, akkor elfogadunk, ha egyszer is ellép, akkor elutasítunk.

4. A teljes feladatsorban szerepel a megoldás a Turing gépek 19. feladatnál.