0
$\begingroup$

I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now I am beginning to wonder whether it is actually decidable.

I have designed the following algorithm. Let $G_{M,x}$ be the configuration graph of $M$ on input $x$ (each node represents a snapshot of $M$, starting from $M(x)$). To decide whether on $x$ we use $m$ space, we visit, DFS-style, each node of $G_{M,x}$ starting from the first node. Each node can be computed from the prior node and we can memorize every node we have encountered so far into a data-structure. Now:

  • If we encounter a node which takes up at least $m$ space, we halt and say yes.
  • If $M$ halts before reaching size $m$ or if we encounter a cycle (i.e. find a node we already visited), we stop and say no.

We apply this algorithm for each $x \in \{0, 1\}^n$, looking for at least an $x$ on which we say yes.

Does this algorithm work? Why or why not? To me it sounds like it works, but I don't know how to prove it. I guess we need to prove that this algorithm actually decides the problem and that it always halts.

Informally, I believe a way to prove this would be to say that we only have finitely many snapshots which represent less-than-$m$-space configurations: in a finite time, either we encounter some of them more than once (so we enter in a cycle) or we exceed the $m$-space limit. Either way, we halt and answer the question.

$\endgroup$
  • 1
    $\begingroup$ Have a look at this question $\endgroup$ – Steven Jul 16 at 18:16
  • $\begingroup$ @Steven nice! thank you very much! do I have to close this question as a duplicate, now? $\endgroup$ – olinarr Jul 16 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.