1
$\begingroup$

In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after $2^{|f(x)|}$ steps on the machine $M$, reportedly to avoid infinite running time.

My question is: how is it that $2^{|f(x)|}$ steps is enough to tell if machine $M$ will run forever or not?

$\endgroup$
2
$\begingroup$

More precisely, if a deterministic Turing machine has an alphabet $\Sigma$, and a set of states $|Q|$ and consumes at most $f(|x|)$ space then the maximum number of configurations the machine can have is $$|Q|\times f(|x|) \times|\Sigma|^{f(|x|)}$$ This is because the maximum length of the tape portion (cells in fact used by the machine) is $f(|x|)$, the head of Turing machine at any time can be located on one of the $f(|x|)$ cells, the machine may be in $|Q|$ different states, and this portion of the tape can be filled in $|\Sigma|^{f(|x|)}$ different ways (using alphabet symbols).

If $q=|Q|$ and $|\Sigma| = 2$ (binary alphabet) then we have $$qf(|x|)2^{f(|x|)}$$ different configurations.

Each step of a Turing machine may change machine's state, tape content, or the position of the head. So after $qf(|x|)2^{f(|x|)}$ steps if the machine hasn't yet halted it must repeat the configuration: $\langle$ state, tape content, head position $\rangle$ meaning the machine will loop forever. So I would say it needs $O(f(|x|)2^{f(|x|)})$ steps rather than $O(2^{f(|x|)})$.

$\endgroup$
1
$\begingroup$

Your goal here is to show that $L$ (as defined in your wiki link) is decidable using $O(f(x))$ space.

If we were talking about the time hierarchy theorem (with an analogous $L$ having a time requirement rather than a space one), then it is clear how to decide $L$, simply simulate the given machine $M$ on its encoding for $f\big(|\langle M\rangle|\big)$ steps and see whether it rejects in this time. Now however, you want to do the same thing, but you cant use an argument like "simulate $M$ with $f\big(|\langle M\rangle|\big)$ space and see if it rejects", when do you stop?

The key point here is that a Turing machine with a binary alphabet who uses $O(f(n))$ space, either halts on a length $n$ input in $O\big(2^{f(n)}\big)$ time or doesn't halt at all. The reason being that the number of possible configurations of a Turing machine limited to $O(f(n))$ cells is $O\big(2^{f(n)}\big)$, assuming we are dealing with a binary alphabet (an exact upper bound depends on the number of states). Thus, if your machine doesn't halt in $O\big(2^{f(n)}\big)$ time on a length $n$ input, you can conclude that it has either gone into an infinite loop (a configuration was repeated), or will eventually use more than $O(f(n))$ space. When actually writing up the machine deciding $L$, you should obviously use exact bounds to avoid the asymptotic notation used here, but for the sake of explanation it doesn't really matter.

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