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.

Also note that universal TMs are still "normal" TMs which just happen to satisfy some properties and hence can also be encoded the same way as all other TMs.

  • $\begingroup$ Please give an encode of unversal Turing machine to support your assertion $\endgroup$ Sep 5 at 17:54
  • $\begingroup$ The wikipedia page I linked explicitly constructs this as I pointed out. Have you read it? $\endgroup$ Sep 5 at 18:55
  • $\begingroup$ The wikipedia you given gives the encoding of general Turing machine, but I did not find the encoding of Universal Turing machine. $\endgroup$ Sep 6 at 19:26
  • $\begingroup$ A universal TM is just a normal TM. I don't understand your problem. $\endgroup$ Sep 6 at 21:11
  • $\begingroup$ 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. $\endgroup$ Sep 7 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.