# How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine which differs all Turing machines enumerated. But how to encode a Universal Turing machine to an Integer such that this Universal Turing machine is enumerable?

There are many ways to encode Turing machines. Essentially, this is possible because a TM $$M$$ is specified by a finite amount of information just like a computer program is completely specified by its source code which in the end is just some binary string in your computer's memory (and note that we can interpret any binary string as a natural number if we put a $$1$$ in front to account for leading zeroes). For more information on this I recommend the corresponding section of the first chapter of "Computational Complexity: A Modern Approach" by Arora and Barak as well as the wikipedia article on description numbers which also gives an explicit coding if you are looking for one.
• Is that true? a general Turing machine's move function is $(q,a)\rightarrow (q',a',d)$ which can be encoded as $01^q01^a01^{q'}01^{a'}01^d0$. However, to encode an Universal Turing machine you need to specific its move function first, and then to encode its move functions to binary string. Sep 7 at 4:24