Universal Turing Machine:

• Given the description of a DTM T and an input string z, a universal TM simulates how T works on input z.
• What's required to be done?

-   How do we describe T and z on tape

• Use an encoding function

-   How do we simulate T

Encoding function

• Let T= (Q, Σ, Γ, δ, s) be a TM. The encoding function e(T) is defined as follows:

-   e(T)=e(s)#e(δ),

-   e(δ)=e(m1)#e(m2)#...#e(mn)#, where δ= {m1, m2,..., mn}

-   e(m)=e(p),e(a),e(q),e(b),e(d), where m = (p, a, q, b, d)

-   e(z)=1e(z1)1e(z2)1...1e(zm)1, where z=z1z2...zm is a string

-   e(Δ)=0, e(ai)=0i+1, where ai is in Σ

-   e(h)=0, e(qi)=0i+1, where qi is in Q

-   e(S)=0, e(L)=00, e(R)=000

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Universal Turing Machine in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.