Construction of UTM

Without loss of generality, we assume the following for M:

• Q = {q1, q2, ….qn} where q1=initial state and q2=Final State
• τ = {σ1, σ2,,…σn} where σ represent blanks
• Select an encoding on which q1 is representable by 1, q2 by 11, and so on.
• Similarly, σ1 is encoded as 1, σ2 as 11, etc.
• Finally, let us represent R/W head directions by 1 for L (Left)  and 11 for R(Right).
• The symbol 0 will be used as a separator between 1s.

With this scheme, any transition of M can be given as : 

A Universal Turing Machine is a Turing Machine which when supplied with an appropriate description of a Turing Machine M and an input string w, can simulate the computation of w.