SzamTud 2024.10.01

Lemma: $L$ rekurziv $⟺$ $L$ es ${\Sigma }_0^{\ast }-L$ is rekurzivan felsorolhato.
Biz.:
$⟹$ Trivialis: $L$ rekurziv $⟺$ $L-{\Sigma }_0^{\ast }$ rekurziv
Volt, hogy ha $L$ rekurziv, akkor rekurziv felsorohlato is.

$⟸$ $T_0,T$ Turing-gepek pontosan $L$ illetve ${\Sigma }_0^{\ast }-L$ szavain allnak meg
$T$ Turing-gep: Input lemasolasa a $2.$ szalagra
$T_0,T$ futtatasa parhuzamosan az elso kesz sdzalagon amelyike eloszor all meg annak az indexet kiirjuk outputkent ${\chi }_L$ kiszamolja

Tetel: $T$ $2$ szalagos univerzalis Turing-gep a $\Sigma$ abece felett.
Jelolje $L_T$ azon $w\in {\Sigma }_0^{\ast }$ szavak halmazat, melyekre $T$ leall ha mindket szalagjara $w$-t irunk.
Ekkor $L_T$ rekurzive felsorolhato de nem rekurziv.
Biz.:
Az hogy rekurzive felsorolhato konnyen belathato mert lezetik olyan Turing-gep ami pont $L_T$ szavain all meg.

$L_T$ nem rekurziv, mert ${\Sigma }_0^{\ast }-L_T$ nem rekurziv felsorolhato.
Tegyuk fel, hogy ${\Sigma }_0^{\ast }-L_T$ rekurziv felsorolhato, ekkor letezik olyan $k$ szalagos Turing gep amely pontosan ${\Sigma }_0^{\ast }-L_T$ szavain all meg. Ezt a $k$ szalagos Turing gepet meg tudjuk szimulalni egy $1$ szalagos Turing-geppel. Ezt az $1$ szalagos Turing-gepet meg tudjuk az eredeti $2$ szalagos univerzalis Turing-geppel szimulalni, legyen ennek a programja $p$.

$p\stackrel{?}{\in }{L}_T$
Ha $p\in L_T$ akkor $T$ megall a $(p,p)$ inputon, ami azt jelenti, hogy az $1$ szalagos Turing-gep megall a $p$ inputon, ami azt jelenti, hogy a $k$ szalgos Turing-gep megall a $p$ inputon. De azt mondtuk hogy a $k$ szalagos Turing-gep pontosan a ${\Sigma }_0^{\ast }-L_T$ szavain all meg.
Tehat ha $p\in L_T$ akkor $p\in {\Sigma }_0^{\ast }-L_T$ ami ellentmondas.

Kovetkezmeny: A $(T,w)$ parokat tartalmazo nyelv, ahol $T$ Turing-gep leall a $w$ szora nem rekurziv.
Biz.: Ha ez rekurziv akkor vegyunk egy $2$ szalagos univerzalis Turing-gepet. Ekkor eldonheto, hogy $T$ megall a $(w,w)$ inputra, tehat eldontheto, hogy $w\in L_T$. Az elozo tetel miatt $L_T$ nem rekurziv igy nem lehet ilyen.

Kovetkezmeny: Azon Turing-gepek leirasa amik megallnak az ures inputon nem rekurziv.
Biz.: Vegyuk $T^{\prime }$ Turing-gepet. Ami a kovetkezot csinalja:

1. Az inputot letorli es rairja $w$-t
2. $T$-t futtatja
   Ez megall az ures inputon pontosan akkor, ha $(T,w)$ megall.

Def.: Domino problema (Tiling problem)
Adott parketta keszlettel parkettazhato-e a sik?