# Prove it is undecidable that a Turing machine accepts at least one input w in space $|w|^2$

This question is part of the undecidable lecture by Jeff Erickson.

$$\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in space }|w|^2\}$$

We should prove that this language is undecidable. So what i tried is to create a new TM $$M'$$ where $$M'$$ moves $$|w|^2$$ steps to the right and than tries to accept $$w$$. So in my opinion that would solve the Accept Problem which we know is undecidable.

My problem with this is that we don't actually get $$w$$ as an input we just ask if there is a word that accepts after $$|w|^2$$ steps. And i don't really know how to handle this.

Let $$\text{AnySpaceSquare}$$ denote the language in the question.

Let us reduce the well-known undecidable language $$\text{Accept} :=\{\langle M, w\rangle\mid\text{Turing machine }M\text{ accepts }w\}$$ to $$\text{AnySpaceSquare}$$.

Suppose a TM $$M$$ and a word $$w$$ is given. Construct TM $$M'$$ so that upon any input, it will simulate $$M$$ on input $$w$$, ignoring the input completely.

1. Upon any input $$v$$, $$M'$$ erases that input.
2. $$M'$$ writes $$w$$ on the tape. (So, $$M'$$ should have $$w$$ hard-encoded in its states and transitions.) Up to now, $$M'$$ should use at most $$\max(|v|,|w|)+1$$ spaces.
3. $$M'$$ runs as if it were $$M$$.
4. If the simulated $$M$$ accepts/rejects/runs forever/whatever, so does $$M'$$ respectively.

Let us check the map $$\langle M, w\rangle\to \langle M'\rangle$$.

• If $$\langle M, w\rangle\not\in \text{Accept}$$, $$M'$$ never accepts.
So $$\langle M'\rangle\not\in\text{AnySpaceSquare}$$.
• Otherwise, $$\langle M, w\rangle\in \text{Accept}$$.
Let us say $$M$$ accepts $$w$$ in $$n$$ steps. These $$n$$ steps use at most $$n+1$$ spaces. Pick any word $$v$$ that is long enough, $$M'$$ should accept $$v$$ within $$|v|^2$$ spaces. In fact, any word at least $$n+|w|+1$$ long would be fine.
So, $$\langle M'\rangle\in\text{AnySpaceSquare}$$.

Hence, if we could decide $$\text{AnySpaceSquare}$$, we could also decide $$\text{Accept}$$.

Exercise. $$\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in time }|w|^2\}$$ is undecidable.