3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $n = |x|$, or does $n$ include more than the length of the input string? $\endgroup$ – Luke Mathieson Apr 26 '13 at 4:49
  • 1
    $\begingroup$ Also, an actual hint; if each tape square can contain $|\Sigma|$ different possible characters, how many different strings can you possibly have when you use at most $c\cdot n$ tape squares? $\endgroup$ – Luke Mathieson Apr 26 '13 at 4:52
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the help, its getting clearer now. Here's what I've got so far: The number of possible configurations is dependent on two things, the state, and the length of the tape. We know that the length of the tape is of size $c \cdot \left | x \right |$, and the total number of states would be the constant d. Since M always halts, the worst case scenario is that M halts in $O(2^{dn})$. $\endgroup$ – HappyCry Apr 26 '13 at 15:37
  • 1
    $\begingroup$ Yes, as long as you don't confuse the two $d$'s you use above. The main point in this question is that a TM that halts cannot repeat a configuration, so the runtime is bounded by the number of configurations. $\endgroup$ – Shaull Apr 26 '13 at 15:42

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.