# Is $2^n$ steps enough to tell if DTM will run forever?

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?

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|)})$.
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.