[Solved]: Proving that Turing Machine M runs in time $O(2^{dn})$

Problem Detail: 

I'm trying to solve this question in order to review for my exam, and this one has got me a bit stumped. From the looks of it, it seems like a fairly straight-forward question, but I can't figure out what steps to begin with.

Let $M$ be a linear-space Turing machine consisting of a single tape. We say $M$ is a linear-space Turing machine if M halts on every input, and if there are constants $c$ and $n_{0}$ such that for all inputs $x\in \Sigma^{\ast}$ of length $n\geq n_{0}$, $M$ running on $x$ visits at most $c\cdot n$ tape squares.

Prove that for some constant $d$, $M$ runs in time $O(2^{dn})$.

I have a couple of ideas to begin with. First, my intuition tells me that I just have to build an algorithm that runs according to those rules and accepts/rejects in time $O(2^{dn})$. Secondly, theres a hint that tells me to "consider the number of configurations", however, I'm not sure on how to incorporate that.

Thank you in advance for any help.

Asked By : HappyCry

Answered By : Shaull

Your intuition is problematic, for the following reason: you are given a specific machine $M$, not a language. Therefore, if you describe an algorithm that runs in $O(2^{dn})$ and decides the same language, you effectively prove that $L(M)$ is decidable in $O(2^{dn})$, but that does not imply that $M$ itself runs in that time frame.

As the hint suggests, consider the number of possible configurations of $M$: recall that a configuration of a TM consists of the contents of the tape, the position of the head, and the state. Given that the alphabet of the machine is fixed, and that the tape used in the run of $M$ on $x$ is of size $c\cdot |x|$, try to bound the number of possible configurations (expressed in the size of $M$ and $|x|$)

Now, recall that $M$ always halts. What does that mean about the sequence of configurations it goes through in its run on $x$?

Combining these two observations you will get the answer. Comment if you need more hints.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11561