Algoritmuselmélet gyakorlat (6)

1. Legyen M a következő Turing gép: $M=(Q,T,I,\mbox{ü},\delta,q_0,F)$, ahol
k=2, $Q=\{q_0,q_1,q_2,q_3,q_4,q_5,\}$, $T=\{X,0,1,\mbox{ü}\}$, $I=\{0,1\}$, $F=\{q_5\}$,
$\delta:\,\,$

áll	1.sz.	2.sz.	1.sz		2.sz		új áll
q0	0	ü	0	H	X	J	q1
	1	ü	1	H	X	J	q1
	ü	ü	ü	H	ü	H	q5
q1	0	ü	0	J	0	J	q1
	1	ü	1	J	1	J	q1
	ü	ü	ü	H	ü	B	q2
q2	ü	0	ü	H	0	B	q2
	ü	1	ü	H	1	B	q2
	ü	X	ü	B	X	J	q3
q3	0	0	0	H	0	J	q4
	1	1	1	H	1	J	q4
q4	0	0	0	B	0	H	q3
	0	1	0	B	1	H	q3
	1	0	1	B	0	H	q3
	1	1	1	B	1	H	q3
	0	ü	0	H	ü	H	q5
	1	ü	1	H	ü	H	q5

(a) Mi lesz a 2. szalagon a q₂ állapotban?
(b) Mi L_M, azaz milyen 0-1 -sorozatokat ismer fel M?
(c) Hogyan módosítható M, hogy a megfelelő 0-1 értékű függvényt számolja ki?

2. Bizonyísuk be, hogy $R=Re\cap coRE$!

3. Rekurzív-e a prímszámokból (pl. bin. ábrázolás) álló nyelv?

4. Bizonyítsuk be, hogy: $L_1,\;L_2$ rekurzív (rekurzíve felsorolható) $\Longrightarrow$ $L_1\cup L_2,\;L_1\cap L_2$ és az $L:=\{xy\in I^*\;:x\in L_1,\;y\in L_2\}$ (egymás után írás) nyelv rekurzív (r.f.).

5. Rekurzív-e az a nyelv, ami azon $x\char93 y\in I^*$ szavakból áll, melyekre létezik M_x (az x szóval kódolt Turing gép), M_x egyszalagos, és a feje az y input esetén a szalagján csak "jobbra" lépéseket tesz (sohasem teszi meg a "helyben" illetve "balra" lépéseket)?

6. Álljon az L nyelv azon $x\char93 y\in I^*$ párokból, melyekre az M_x kétszalagos Turing gép létezik, és M_x az y input esetén nem változtatja meg az első szalagjának a tartalmát (azaz M_x futása során az első szalagján végig az $y\mbox{\it üü}\ldots$ sorozat található)! Bizonyítsuk be, hogy az L nyelv nem rekurzív!

7. Álljon L szópárokból: $L\subseteq\{x\char93 y\vert x,y\in \{0,1\}^*\}$. Tegyük fel, hogy L, mint egy $\{0,1,\char93 \}$ feletti nyelv rekurzíve felsorolható. Bizonyítsuk be, hogy az

$L_1=\{x\in\{0,1\}^*\vert~\mbox{létezik olyan } y\in\{0,1\}^*, \mbox{ hogy } x\char93 y\in L\}$

nyelv is rekurzíve felsorolható!

8. Mutassuk meg, hogy van olyan $f:I^*\rightarrow N$ függvény, ami nem rekurzív, de amire a következő $g:I^*\rightarrow \{0,1\}$ függvény rekurzív: g(y)=1, ha f(y) páratlan és g(y)=0, ha f(y) páros!

Megoldások