2
$\begingroup$

Let

$$L_{\text{PSPACE}}=\{\langle M\rangle : M \text{ is a TM using a polyspace amount of memory}\}$$

Is $L_{\text{PSPACE}}$ decidable?


I don't think we can use Rice's Theorem because this doesn't seem to be a semantic property of TMs. I also don't see any reduction from the HALT problem, or other known undecidable languages like HALTONZERO. But my instinct tells me that this seems uncomputable because it seems like there shouldn't be any way to look at the instructions of a machine and figure out how much space it will ultimately consume.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

In fact, you can reduce the $\text{HALT}$ problem to deciding $L_{\text{PSPACE}}$.


Suppose $U$ is a fixed universal Turing machine constructed as in a usual textbook.

Let $\langle T\rangle$ be an input to the $\text{HALT}$ problem problem, where $T$ is a Turing machine.

Construct a Turing machine $U_T$ that is based on $U$. On an input $w$ of length $n$, $U_T$ will try simulating $T$ on empty input for $n$ steps, and if $T$ halts before $n$ steps, read next $2^n$ cells. Note that the construction of $U_T$ from $T$ can be specified algorithmically.

Then $T$ on empty input stops if and only if $U_T$ belongs to $\overline{L_{\text{PSPACE}}}$.

Since the $\text{HALT}$ problem is not decidable, neither is $\overline{L_{\text{PSPACE}}}$.

Since the $\overline{{L_{\text{PSPACE}}}}$ is not decidable, neither is ${L_{\text{PSPACE}}}$.


Exercises 1. Use diagonalization to show ${L_{\text{PSPACE}}}$ is not computably enumerable.

Exercises 2. Use diagonalization to show $\overline{{L_{\text{PSPACE}}}}$ is not computably enumerable.


Here is a good question and answers with similar content, Are runtime bounds in P decidable? (answer: no).

$\endgroup$
1
  • 1
    $\begingroup$ Gah, now I feel dumb, this makes a lot of sense. I kept thinking you need to check $M$ on every input to see how its space consumption grows. But the whole point of HALTONZERO and similar instances of uncomputable functions, is that you don't need to be able to decide it for every input, but even being able to make a decision for a finite number of inputs is sufficient! Thanks! $\endgroup$
    – Addem
    Dec 11, 2021 at 22:48

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.