Zakódování Turingova stroje
23/45
Myšlenka: Popis Turingova stroje pomocí řetězce obsahující nuly a jedničky
• Předpokládejme,
že TS M má tvar M = (Q, S, G, R, q0, {q1}), kde: Q = {q0, q1, … , qm}, G = {a0, a1, … , an} tak, že: a0= D
• Nechť d je zobrazení z (Q È G È {S, L, R}) do {0, 1}* ,
definováno:
d(S) = 01, d(L) = 001, d(R) = 0001,
d(qi) = 0i+11 pro všechna
i = 0 … m,
d(ai) = 0i+11 pro všechna i = 0 … n
• Pro
každé r: pa ® qbt Î R definujeme:
d(r) = d(p)d(a)d(q)d(b)d(t)1
• Nechť R = {r0, r1, … , rk}. Potom
d(M) = 111d(r0)d(r1)…d(rk)1 je zakódování TS M