# Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?

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.

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