World's most popular travel blog for travel bloggers.

Why can't configuration counting decide undecideable problems?

, , No Comments
Problem Detail: 

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

Asked By : so.very.tired

Answered By : Karolis Juodelė

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback