1
$\begingroup$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to prove:

$$ L \notin \texttt{DSPACE}(f(n)) $$

How would I do this?

My first attempt was to reduce a language $L'$ from $\texttt{DSPACE}$ to the language $L$, but I don't know of any language in $\texttt{DSPACE}$ and I don't know if I can "simply" reduce it. Does anyone have a reduction that I see and try to understand?


The exact exercise specifies the language $L$: it is $\{ w\mid w \in T(M_w),M_w \text{ needs space |w|}\}$.

Also, we are given that $f(n) \in \Omega(\log{n})$.

$\endgroup$
0
$\begingroup$

Unfortunately, when you tried to ask a general question to get hints for your homework exercise rather than the solution, you turned the question into something too general to answer. I'll try to come back at some point and write something more useful, now that you've made the question more specific. Diagonalization is the usual technique, similar to how the halting problem is proven undecidable.


You're not going to prove that a completely generic language $L$ is not in $\mathrm{DSPACE}(f(n))$ for a completely generic function $f$. Any such proof is going to have to rely on some properties of $L$ and $f$: quite apart from anything else, if you fix a decidable language $L$, then there are infinitely many functions $f$ such that $L$ is in $\mathrm{DSPACE}(f)$ and, conversely, if you fix any "reasonable" function $f$, there are infinitely many languages in $\mathrm{DSPACE}(f)$. So you can't hope to prove $L\notin\mathrm{DSPACE}(f)$ as a generic result.

Second, saying "I don't know any languages in $\mathrm{DSPACE}$" is like saying I don't know any people who weigh kilograms (or pounds, if you prefer). It doesn't really mean anything until you specify how many kilograms or, correspondingly, what space bound you're talking about.

$\endgroup$
  • $\begingroup$ I edited the question, thanks for mentioning. I was trying to first get a general "how to" to see if I can figure out by myself. $\endgroup$ – gxor Jun 18 at 13:07
  • 1
    $\begingroup$ @gxor Aha -- good plan. Diagonalization is the usual method, along the lines of the proof that the halting problem is undecidable. $\endgroup$ – David Richerby Jun 18 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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