jareds wrote: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 wrote: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.
Users browsing this forum: No registered users and 2 guests