0
$\begingroup$

This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of those are unique, when I asked on IRC it was suggested that most of them are duplicates. Unique and valid in this case means that it is the only Turing machine included that when given the specific input terminates with the same tape, same position, and in the same accepting/rejecting state. Valid means they will accept/reject at some point regardless of input.

Some ideas I had to limit it are that some states might be unreachable and hence simplify down to one with less states. This reduces it by $$(3(c+1)(n+1))^{(c+1)(n-1)}$$ different machines. This is true because for each machine one state smaller you can effectively leave it as is, just modify it by adding $c+1$ new transitions from a new state. Since you didn't modify any of the other states this is unreachable and won't affect execution, therefore they are functionally equivalent. The reason this won't apply to all below it is that they are included in the count for $n-1$. If they were padded to $n$ states and they started with $i < n-1$ states they would have to have $n-1$ states somewhere along the line as they were building up and therefore already be included.

Are there any other ways to remove equivalent programs?

$\endgroup$
  • $\begingroup$ If you were satisfied by the answer you were given before, it would be appropriate to recognize it. $\endgroup$ – André Souza Lemos May 14 '15 at 19:50
  • 1
    $\begingroup$ A second observation is that an assertion like the one you propose should be proved (or refuted). By presenting us what admitedly is just a guess, and expecting the rest to be handed out to you, you are in fact bypassing the entire learning process. $\endgroup$ – André Souza Lemos May 14 '15 at 20:07
  • 1
    $\begingroup$ Ok, I hadn't noticed it. No need to add another answer, yours is ok. I should say that this second problem is a lot more complicated than the other one. For starters, define explicitly what is a unique Turing machine. Then you can list the transformations that produce equivalent machines, according to your definition (permutation of symbols, for instance). Only then can the combinatorial problem be adressed. $\endgroup$ – André Souza Lemos May 14 '15 at 22:33
  • 1
    $\begingroup$ Again, try to solve it for small $n$ and $c$. Machines that loop are not valid? $\endgroup$ – André Souza Lemos May 14 '15 at 22:39
  • 1
    $\begingroup$ @AndréSouzaLemos By valid I mean that they give a finite result. Infinite loops won't definitively give a finite result. I can remove that requirement if it makes it much easier. $\endgroup$ – ruler501 May 14 '15 at 23:13

Your Answer

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

Browse other questions tagged or ask your own question.