2
$\begingroup$

By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept.

We can assume every $n$-state Turing machine has $(c+1)n$ transitions going to either another non-accepting state, reject, or accept, that is that it has a transition for every state and character on the tape. It can either move to the left, right or not shift each transition. I tried some myself to figure out how many Turing machines there were and got the two following incompatible results.

We have $(c+1)n$ transitions and each transition has $3(n+2)(c+1)$ different options. Encoding it as a 5 tuple I get $3n(n+2)(c+1)^2$, but taking from options for transitions for each transition gives me $((c+1)n)^{3(n+2)(c+1)}$

Is either of these correct and if so why?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Try to think of small examples (c=1, n=2 or c=2, n=1), check if you formulas are correct. $\endgroup$ – André Souza Lemos May 14 '15 at 0:00
  • $\begingroup$ How can I ensure I generated all of them? $\endgroup$ – ruler501 May 14 '15 at 1:14
  • 1
    $\begingroup$ Its a simple combinatorial problem. That is why I suggested that you tried for small cases, where you can almost count the combinations manually. You are not far from the solution. $\endgroup$ – André Souza Lemos May 14 '15 at 1:28
  • $\begingroup$ Please, can someone explain how this formula compares with the one which I come up with?: For set $Q$ of $n$ states, $\Gamma$ tape alphabet and transition function $\delta:Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\} $, I can deduce the number of Turing machines that can be prepared equals $n|\Gamma|(2n|\Gamma|+1)$ ($2$ for $\{L,R\}$ and $1$ for dead configuration). How this equals $(3(c+1)(n+2))^{(c+1)n}$ in accepted answer? Are their any different assumptions? $\endgroup$ – anir Jun 26 '18 at 18:49
2
$\begingroup$

The answer is $(3(c+1)(n+2))^{(c+1)n}$. You get this by considering all functions of the type $(Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R, N\}$. Where $Q$ is the set of states, $F$ is the set of final states, $\Gamma$ is the alphabet including the blank character, and $L$, $R$, $N$ are the left shift, right shift, and no shift respectively. You can view this as a problem of picking $|(Q \setminus F) \times \Gamma| = (c+1)n$ elements from a set of cardinality $|Q \times \Gamma \times \{L, R, N\}| = 3(c+1)(n+2)$ with replacement.

|cite|improve this answer
$\endgroup$

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.