patternMinor
Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?
Viewed 0 times
whyarewithstatesandmachinessymbolsturingthere2kn
Problem
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?
$\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?
Solution
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.
Context
StackExchange Computer Science Q#41117, answer score: 4
Revisions (0)
No revisions yet.