2
$\begingroup$

I know it might sound like a silly question, I just can't get my head around it...

I just read that $DSPACE(f(n))\subseteq DTIME(n\cdot 2^{O(f(n))})$.
The proof for it relies heavily on the fact that for a given $L\in DSPACE(f(n))$, the turing machine $M_L$ (which decides $L$ while consuming no more than $p(|x|)$ memory space for some polynomial $p$ and input $x$), under the assumption that it decides $L$, cannot have the same exact configuration twice (otherwise it's stuck in an infinite loop), and therefore, we can bound the runtime of $M_L$ by counting the number of possible configurations, which is $n\cdot 2^{O(f(n))}$.
The thing is this;
If ($M_L$ decides $L$) $\Rightarrow$ (There are no two similar configurations in $M_L$)
Why doesn't (There are two similar configurations in $M_L$) $\Rightarrow$ ($M_L$ won't decide $L$)?
Why can't configuration counting decide $A_{TM}$, for example? ($A_{TM}=\left\{(M,w)|M(w)=ACCEPT \right\}$)

$\endgroup$
4
$\begingroup$

Configuration counting can certainly detect infinite loops. But only if space is bounded. A TM could write non-repeating nonsense on the tape and never get caught.

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