So I was reading about Universal Turing Machines http://www.scholarpedia.org/article/Tur ... ng_machine
, and a question occurred to me that I was hoping XKCD might be able to answer.
To quote from the article:
"It is possible to give an effective (computable) one-to-one pairing between natural numbers and Turing machines. This is called an effective enumeration. One way to do this is to encode the table of rules of each Turing machine in binary, in a canonical way... One can construct a Turing machine to decide whether a given binary string x encodes a Turing machine."
So we can construct TM's from single numbers. Okay, that's obvious enough. But consider the two following problems:
1) A bijective effective enumeration that returns a Turing machine that, were you to visualize it as you would a directed graph, with the states being nodes and the transitions being edges, would be non-isomorphic to any other Turing machine that this function would return on any other input. (Informally, an enumeration that on no two distinct inputs will ever return Turing machines that are essentially the same but with relabeled states).
2) An effective enumeration like the one above, but that returns a Turing machine for every natural number. So, for example, if numbers 1, 5, 7, and 10 would be the first four numbers that represent Turing machines to problem #1, an algorithm implementing problem #2 would return the inputs that were returned for 1, 5, 7, and 10, but would do so for inputs 1, 2, 3, and 4.
Now, I know that these functions are computable, but does anyone know what complexity classes these problems belong to? Are they in P? NP? EXPTIME? Does any algorithm implementing these functions appear in the literature?
Thanks in advance for any help you can give.