Implementation of UTM

A  UTM Mu then has an input alphabet = {0, 1} and the structure of a multi-tape TM.

• Mu looks first at the contents of Tape 2 and Tape 3 to determine the instantaneous description (ID) of M.
• It then consults Tape1 to see what M would do with this ID.
• Finally, Tape 2 and Tape 3 will be modified to reflect the result of the move.

If no transition for a given ID is formed, Mu halts as M must :

• In either case, Mu behaves as M would.
• If M halts, when presented with string w then Mu will halt when presented with the encoded M and the encoded string on its tape.
• Moreover, the final string Mu .s tape will be the encoding of the string.
• When M halts, Mu can tell if it is in the single accepting state and so moves to an accepting state of its own ( or not).

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.