2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.