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 the upper 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.