How many Turing machines are there with $c$ characters and $n$ states?

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?

• Try to think of small examples (c=1, n=2 or c=2, n=1), check if you formulas are correct. – André Souza Lemos May 14 '15 at 0:00
• How can I ensure I generated all of them? – ruler501 May 14 '15 at 1:14
• 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. – André Souza Lemos May 14 '15 at 1:28
• 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? – anir Jun 26 '18 at 18:49

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.