0
$\begingroup$

I came across following question:

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

The answer given was:

$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?

$\endgroup$
  • $\begingroup$ 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?" $\endgroup$ – Peter Taylor Nov 12 '19 at 10:45
1
$\begingroup$

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.

$\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.