4
$\begingroup$

I've seen a few references [1], [2], [3] that say that for a Turing Machine with transition function defined by:

$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$

the number of turing machines with $n$ states and $k$ tape symbols is $(2kn+1)^{kn}$.

However, looking at the definition, shouldn't it be $(2kn)^{kn}$ instead?

$\endgroup$
4
$\begingroup$

Perhaps they are counting the number of Turing machines with at most $n$ states. In any case, it's not a big difference. Usually one is only interested in an upper bound, and from that perspective there is no difference between the two expressions.

$\endgroup$
  • $\begingroup$ Thanks, I was just curious as to why there is that difference though. $\endgroup$ – Ryan Apr 7 '15 at 20:11

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.