Description of a Turing
Machine
23/45
Gist: Turing
machine representation using
a string over {0, 1}
• Assume
that TM M has the form M = (Q, S, G, R, q0, {q1}), where Q = {q0, q1, … , qm}, G = {a0, a1, … , an} so that a0= D
• Let d is the mapping from (Q È G È {S, L, R}) to {0, 1}*
defined as:
d(S) = 01, d(L) = 001, d(R) = 0001,
d(qi) = 0i+11 for all i = 0 … m,
d(ai) = 0i+11 for all i = 0 … n
• For every r: pa ® qbt Î R we define
d(r) = d(p)d(a)d(q)d(b)d(t)1
• Let R = {r0, r1, … , rk}. Then
d(M) = 111d(r0)d(r1)…d(rk)1 is the description of TM M