Universal Turning Machine A Universal Turing machine is a Turing machine (Tu) that works as follows: It is assumed to receive an input string of the form e(T)e(z), where T is an arbitrary TM, z is a string over the input alphabet of T , and e is an encoding function whose values are strings in {0,1}*. The computation performed by Tu on this input string satisfies following two properties: Tu accepts the string e(T)e(z) if and only if T accepts z. If T accepts z and produces output y, then (Tu) produces output e(y).
