Megoldások a hatodik gyakorlathoz 1. (a) Egy nagy X, utána meg az input szó. (b) A palindrómákat, azaz az olyan szavakat, amik visszafele olvasva is ugyanazok. (c) Lesz két új állapot: q6 és q7. Amikor q5-be mennénk az eredeti géppel, akkor menjünk q6-ba és ebben az állpotban menjünk vissza a második szalag elejére, közben üresre írva, azaz törölve minden mezőt. Ha meglátjuk az X-et, akkor annak a helyére írjunk 1-et és menjünk q5-be. Ezzel elintéztük, hogy ha elfogadunk, akkor 1-et írunk az output szalagra (ami most a második). Kell még, hogy kiürítsük a második szalagot és írjunk 0-t, ha elutasítanánk. Ez az eredeti gépnél akkor van, ha q3-ban nem két egyformát olvasunk. Ezekre az esetekre az új gépnél menjünk q7-be, töröljük először végig jobbra a második szalagot, majd menjünk vissza az elejére és közben töröljünk, amíg X-et nem látunk, azt írjuk át 0-ra. Ezzel kész. 2. A jegyzetben le van írva. 3. A teljes feladatsorban szerepel a megoldás a Turing gépek 5. feladatnál. 4. A teljes feladatsorban szerepel a megoldás a Turing gépek 6. feladatnál. 5. Igen. A Turing gép, ami mindig megáll és épp ezeket a kódokat fogadja el a következő: először is leellenőrzi, hogy az adott szó $x\char93 y$ alakú-e, és hogy x egy Turing gép kódja-e. Ha nem, akkor elutasít, ha igen, akkor a következőt teszi. Elindítja Mx-et y-on. Ha a gép helyben maradna vagy balra menne, akkor elutasít. Ha mindig megy jobbra, akkor az y hosszával azonos időben leér a szóról és üreseket kezd olvasni. Itt is ha helyben marad vagy balra megy, akkor elutasítjuk a szót. Ha mindig megy jobbra, akkor legkésőbb |Q| lépés után ugyanabban az állapotban lesz, mint egyszer már volt korábban az üresek olvasása közben. Tehát végtelen ciklusban van, a gép, azaz most már biztosan mindig jobbra fog gyalogolni. Tehát elég elindítani és figyelni |y|+|Q| lépést: ha addig csak jobbra megy, akkor elfogadunk, ha nem, akkor elutasítunk. 6. Megmutatjuk, hogy ha ez a nyelv rekurzív lenne, akkor rekurzív lenne a megállási nyelv is, azaz az azon $x\char93 y$ szavakból álló nyelv, ahol x egy egyszalagos Turing gép kódja és Mx megáll y-nal indítva. Erről meg tudjuk, hogy nem rekurzív. Tegyük fel tehát, hogy van egy olyan M Turing gépünk, ami minden $x\char93 y$ párról megmondja, hogy az Mx kétszalagos gép y-nal indítva változtat-e az első szalagon. Az M Turing gép segítségével készítünk egy olyan M' Turing gépet, ami mindig megáll és akkor fogad el, ha az $x\char93 y$ input szó olyan, hogy az Mx egyszalagos gép y-on megáll. Az M' gép a következőt tegye: leellenőrzi, hogy $x\char93 y$ olyan pár-e, ahol x egy egyszalagos kódja. Ha nem, akkor elutasít, ha igen akkor megy tovább és az Mx egyszalagos Turing géphez elkészíti a következő kétszalagos M'x gépet: ez az inputszót átmásolja második szalagra, majd ott elkezd úgy működni, mit az eredeti egyszalagos gép. Ha az eredeti gép megállna, akkor M'x ír az első szalagra valamit és megáll, különben nem ír és nem áll meg. (Tehát ez az így elkészített kétszalagos M'x gép pontosan akkor ír az első szalagra, ha az input szón az egyszalagos M-x gép megáll.) Tehát az M' TG elkészíti ezt az M'x gépet az $x\char93 y$ bemenethez majd meghívja meghívja az M Turing gépet és megkérdi, hogy az így kapott kétszalagos M'x Turing gép ír-e az első szalagjára az y szóval indítva. Mivel az M mindig megáll és választ ad, megtudjuk, hogy ír-e vagy sem. Ha ír, akkor M' elfogad, ha nem ír, akkor elutasít. A fentiek értelmében ez az M' gép mindig megáll és éppen a megállasi nyelvet fogadja el, ami nem lehetséges. 7. Adunk egy M' Turing gépet, ami elfogad egy x szót, ha van hozzá jó y, különben meg nem áll meg. Ez az M' gép arra az M gépre épül, ami az L nyelvet ismeri fel. Ez az M gép elfogadja az L szavait, a többi szóra meg vagy nem áll meg vagy elutasít. Lényegében végigpróbálgatjuk az összes y szót az x-hez és ha találunk jót, akkor elfogadjuk az x-et, ha nem akkor meg nem állunk meg. A jó y keresése a következő módon megy: felveszünk egy táblázatot, aminek a sorai a természetes számoknak felelnek meg, az oszlopai meg az ábécé feletti szavaknak (mondjuk lexikografikus sorrendben). Így a táblázat két irányban is végtelen. Ebben lépkedünk a jegyzetben is vázolt átlós eljárás szerint (először az(oka)t a ponto(ka)t látogatjuk végig, ahol a sor és oszlopindexek összege 1, aztán azokat ahol az összeg kettő, stb.) Ha az (i,j) mezőn vagyunk, akkor futtajuk az M gépet $x\char93 y_j$-n i lépésig. Ha az M ezalatt elfogad, akkor mi is elfogadjuk x-et, ha nem fogad el, akkor megyünk tovább a következő (i,j) párra. Ha van az x-hez jó y, akkor előbb-utóbb elfogadjuk az x-et, ha nincsen, akkor meg nem állunk meg. 8. A teljes feladatsorban szerepel a megoldás a Turing gépek 23. feladatnál.