16 tetel Szimuláció
Ebbe a tételbe az elfogadó Tg nem tuti, hogy kell, de szerintem kell, hogy kis fogalmunk legyen róla.
Elfogadó Turing gép:
T:?k, ?, Q,q,M, ?,F? F?Q elfogadó állapotok halmaza. T.-elfogadja ? -t, ha a ? K1……Kn számitás, K1 kezdo ? bemenet, Kn végkonfiguráció és Kn -hez tart. Belso állapot eleme F. ? abc, ?X ? feletti véges szavak halmaza. Véges nem üres halmaz: ? abc. R: ?(0,1)+ üres szó. Nyelv formális ténylegesen: ? abc feletti nyelv L??X . A Turing gép által felismert nyelv azon nyelv, amely L(?)={??? -t T. elfogadja} f: ?X ??X az f függvény a T. által kiszámított függvény, ha ? ? eleme ?X esetén az f(?) ?T(?). A függvény érték megegyeznek a Tg. kimenetével. T1 tg. Szimulálja a T2 tg-et, ha ? ? eleme ?X a T1 (?) = T2 (?)

T1 szimulálja T2 Turing-gépet, ha bármely w eleme ?* a T1(w)=T2(w).
Tétel: Bármely T tg-hez megadható egy T’ 1szalagos tg. , amelyik szimulálja a T-t.
Bizonyitás: T’ szalag abc-jét ??k a következoképpen definiálja ??=?K ?{0,1} K Pl: eredeti tg ?={0,1} ahol ?? elemei:
?*={01 02 03 04} 16 elemu(k=2) 3féle belso állapota van. Q’=Q1 v Q2 v Q3 .
Q1:végrehjtja az eredeti TG olvasási muveletét
Q2:visszaír
Q3:elmozgatja a fejeket
Ha T-nek volt egy q1 ? q2 /fej mozg/, q1?{(q1, a1,…,aK)? a1,…,aK ??}? Q1, (q1, a1,…,aK)? c1,…,cK, ?? , X1 ? {0,1}fej mozog ? (q1, a’1,…,a’K) ?( X1 – Xk) ?J,
Q1:beli állapot (q1,X1, ….Xk): hozzá tartozó állapot átmenet. (q1,X1, ….Xk) ? ( a1,…,aK, d1, ….,dk) ?(q1,Y1, ….Yk) ? ( a1,…,aK, d1, ….,dk) ?J ahol ? Yi ={ Xi ,ha d1 =0, a1,ha d1 =1 ( az állapotban tárolja az i ….szalag iró-olvasó feje alatti betut). Ezekkel az állapotokkal végigolvasuk az egész szalagot, így a szalag végére érve az állapot (q1,X1, ….Xk) azt fogja reprezentálni, hogy a ……… gép q állapotban lenne és X1, ….Xk jelek lennének az iró/olvasó fejek alatt.
Q2: ben volt q1(a1,…,aK) ? q2( b1,…,bK) ? ( m1,…,mK ) állapotunk, akkor (q1, a1,…,aK)? ?(q’1, a1,…,aK)?b ?(q’1, a1,…,aK) ? (X1, ….Xk , d1, ….,dk) ? (q’1, a1,…,aK) ? (Y1, ….Yk , d1, ….,dk) ?b, ahol a Yi ={ Xi ,ha d1 =0, b1,ha d1 =1 végig megy a szalagon és átirja a jeleleket.
Q3:beli állapot q1(a1,…,aK) ? q2 ( b1,…,bK) ? ( m1,…,mK ) állapotunk, akkor (q1, a1,…,aK)? ?(q’’1, a1,…,aK)?J?(q’’1, a1,…,aK) ? (X1, ….Xk , d1, ….,dk) ? (q’”1, a1,…,aK) ? (X1, ….Xk , e1, ….,ek) ?m ,ahol e1, ….,ek érték attól függ, hogy mi volt m1,…,mK értéke.( Egy kisebb lép..sorozattla szomszédos cellák érték is változik)
( )* ->q’*h q’ elemeQ q’=(q2,b1…bk)(négyszer kell átmenni a szalagon a szimuláláshoz)