# Maximum number of configurations of Turing machine after $n$ moves

I came across following question:

What are maximum number of configuration of Turing Machine after $$n$$ moves?

$$k^n$$, where $$k$$ is a branching factor.

And that "branching factor" left me confused. So I gave some thoughts: Given $$Q$$ be total number of states, $$\Gamma$$ be a tape alphabet and two moves, left and right $$\{L,R\}$$, for every transition function, we have $$2^{Q\times \Gamma \times 2}$$ possible transitions at each of those $$n$$ moves. Thus, $$k$$ must be $$2^{Q\times \Gamma \times 2}$$. So, total number of configurations of Turing machine after $$n$$ moves must be $${(2^{Q\times \Gamma \times 2})}^n$$. Am I correct with this?

• The question should probably have been "What is the lowest upper bound on the number of configurations a general Turing machine can be in after $n$ moves?" Nov 12 '19 at 10:45

Note that you are bounding the maximal number of configurations, that the machine can be in, from above. To see it more clearly, when a TM $$M$$ runs on a finite word $$w$$ it induces a configuration tree $$G = \langle V, E\rangle$$ where:

• $$V$$ is the set of configurations that $$M$$ can be in when it runs on $$w$$,

• $$q_0w$$ is the initial configuration of $$M$$ on $$w$$ and it is the root of the configuration tree,

• and the edges in $$E$$ are defined such that $$u$$ is a child of $$v$$ whenever $$u$$ a consecutive configuration of $$v$$ (by consecutive we mean that it is possible to reach $$u$$ from $$v$$ without violating the transition function of $$M$$).

As you have mentioned, $$k$$ is a branching factor, and we usually mean by that the maximal branching degree in the configuration tree. In this aspect you're not correct, $$k$$ is at most $$|{Q\times\Gamma\times \{L, R\}}| = {2|Q|\cdot |\Gamma|}$$, and this follows from the definition of the transition function. Indeed, $$k$$ bounds from above the number of consecutive configurations (which is a subset of configurations) and not the number of all possible subsets of configurations of the TM.

Considering the configuration tree, it is a tree of height ($$n = |w|$$) with branching degree $$k \leq {2|Q|\cdot |\Gamma|}$$. Now its not hard to see that such a tree has at most $$k^n$$ leaves which bounds from above the number of configurations that $$M$$ can be in when it runs on a word $$w$$ of length $$n$$.

A thing worth mentioning is that, $$k$$ is a constant that does not depend on the input word $$w$$ (on $$n = |w|$$) or on a specific configuration tree, and we know that it exists. This sometimes makes life a bit easier as some algorithms/proofs rely on its existence to conclude some upper bounds.