Editing Universal Turing machine (section)

==Efficiency==
Without loss of generality, the input of Turing machine can be assumed to be in the alphabet {0, 1}; any other finite alphabet can be encoded over {0, 1}. The behavior of a Turing machine ''M'' is determined by its transition function. This function can be easily encoded as a string over the alphabet {0, 1} as well. The size of the alphabet of ''M'', the number of tapes it has, and the size of the state space can be deduced from the transition function's table. The distinguished states and symbols can be identified by their position, e.g. the first two states can by convention be the start and stop states. Consequently, every Turing machine can be encoded as a string over the alphabet {0, 1}. Additionally, we convene that every invalid encoding maps to a trivial Turing machine that immediately halts, and that every Turing machine can have an infinite number of encodings by padding the encoding with an arbitrary number of (say) 1's at the end, just like comments work in a programming language. It should be no surprise that we can achieve this encoding given the existence of a [[Gödel number]] and computational equivalence between Turing machines and [[μ-recursive function]]s. Similarly, our construction associates to every binary string ''α'', a Turing machine ''M<sub>α</sub>''.

Starting from the above encoding, in 1966 F. C. Hennie and [[Richard E. Stearns|R. E. Stearns]] showed that given a Turing machine ''M<sub>α</sub>'' that halts on input ''x'' within ''N'' steps, then there exists a multi-tape universal Turing machine that halts on inputs ''α'', ''x'' (given on different tapes) in ''CN'' log ''N'', where ''C'' is a machine-specific constant that does not depend on the length of the input ''x'', but does depend on ''M'''s alphabet size, number of tapes, and number of states. Effectively this is an <math>\mathcal{O}\left ( N \log {N}\right )</math> simulation, using [[Donald Knuth]]'s [[Big O notation]].{{sfnp|Arora|Barak|2009|loc=Theorem 1.9}} The corresponding result for space-complexity rather than time-complexity is that we can simulate in a way that uses at most ''CN'' cells at any stage of the computation, an <math>\mathcal{O}(N)</math> simulation.{{sfnp|Arora|Barak|2009|loc=Exercises 4.1}}