Turing Machine Enumeration

[JTHM]

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.

[philoctetes]

Take an enumerator for all Turing machines with a specific lexicographical ordering. Then when reaching the k-th machine in this ordering, simply check all permutations of its states and verify that no permutation gives you any machine whose place in the ordering is in {1,...,k-1}.

I'm not sure whether that answers #2 or not. If all you are checking is identity up to permutations of states, then that's fine. Remember, though, that determining whether two TMs in general have the same language is an undecidable problem.

[jareds]

Do you mind explaining your motivation a bit more? It is unusual in the first place to care about enumerating Turing machines without isomorphic duplicates, and even more unusual to care about the complexity of the enumeration.

You can see that philoctetes's method is in PSPACE, right? Bear in mind that being in a complexity class doesn't mean that it isn't in a smaller complexity class.

If you really want to investigate this, I would start out by investigating how efficiently you can enumerate non-isomorphic directed graphs, because this will be very closely related, and I doubt anyone has analyzed this in the context of enumerating Turing machines in particular.
Edit: I see that you are already looking along these lines in the math forum.

[JTHM]

Do you mind explaining your motivation a bit more? It is unusual in the first place to care about enumerating Turing machines without isomorphic duplicates, and even more unusual to care about the complexity of the enumeration.

You can see that philoctetes's method is in PSPACE, right? Bear in mind that being in a complexity class doesn't mean that it isn't in a smaller complexity class.

If you really want to investigate this, I would start out by investigating how efficiently you can enumerate non-isomorphic directed graphs, because this will be very closely related, and I doubt anyone has analyzed this in the context of enumerating Turing machines in particular.
Edit: I see that you are already looking along these lines in the math forum.

My motivation would take a very long time (about five printed pages) to explain in any depth. I'm researching this because I'm writing one of those many papers that shows, If we could only prove such-and-such a theorem, we could prove that P=NP or P!=NP, and depending on whether or not problem #2 is in NP, I may have to throw out most of what I've already written.

And yes, I can see that philoctetes' method is in PSPACE. I should have mentioned that I'm more interested in the time complexity than the space complexity.

[jareds]

My motivation would take a very long time (about five printed pages) to explain in any depth. I'm researching this because I'm writing one of those many papers that shows, If we could only prove such-and-such a theorem, we could prove that P=NP or P!=NP, and depending on whether or not problem #2 is in NP, I may have to throw out most of what I've already written.

And yes, I can see that philoctetes' method is in PSPACE. I should have mentioned that I'm more interested in the time complexity than the space complexity.

OK, fair enough. You may have a problem, depending on the structure of your proof. If you need to prove unconditionally that #2 is not in NP, you need to resolve an open problem, because we can't prove that P!=PSPACE. If a conditional proof that #2 is not in NP will suffice, you should probably tell us what the antecedent conditions could be.

[Yakk]

Things remain vague. The words "Like the one above", when you have two Turing Machines that you described above, is worse than useless. Please name your Turing machines.

What the hell does "like the one above" mean anyhow -- does it mean "for an arbitrary turing machine that obeys the previous restrictions (whatever they are), we want to be able to preserve the ordering yet skip the holes", or does it mean "it obeys the above restrictions, and returns a value for each natural number". The example just stresses this annoying ambiguity.