Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a constant and $p(n)$ a polynomial, can we decide whether $L_u \in R$ or not?

Memory complexity represents the largest difference of indices of used slots of the tape. So I believe $L_u \in EXPSPACE$, although here it is defined using a constant, whereas most articles use a 2 to the power of some polynomial. This is why I'm not sure about that fact.

Basically, what I'm asking is:

Is $L_u \in EXPSPACE$?

If it is, can this fact be used to derive whether $L_u \in R$, and how?

If not, how can the fact that $L_u \in RE$ and that the turing machine has a memory complexity of $c^{p(n)}$ be used to determine whether $L_u \in R$, and how?

  • 2
    $\begingroup$ Yes. ​ ​ $\endgroup$ – user12859 Jun 8 '16 at 6:15
  • $\begingroup$ Well, on what basis are you saying this? Is this related to the fact there are finitely many configurations of the memory space? $\endgroup$ – user129186 Jun 8 '16 at 7:06
  • $\begingroup$ I still have no idea what you're trying to ask. What exactly is the guarantee on the Turing machine? For inputs in $L_u$, what does it do? For inputs not in $L_u$, what does it do? $\endgroup$ – Yuval Filmus Jun 8 '16 at 8:36
  • $\begingroup$ Your first paragraph asks, "assuming I have a TM for L, is there a TM for L?". That's not a very interesting question. Below you ask something completely different. Please consolidate your post so that it makes sense as a whole. Please state exactly what your assumptions and proposed conclusions are. (Note that time/space complexity classes only make sense for decidable languages.) $\endgroup$ – Raphael Jun 8 '16 at 8:41
  • $\begingroup$ If I understand the difference between $RE$ and $R$ correctly, we know that the TM will halt and accept SOME inputs in $L_u$, but for some it might not halt at all. Similarly, it might not halt for any inputs not in $L_u$. This is the essence of the question, I think. Will the TM halt in a final state for all $w \in L_u$ and halt in a non-final state for all $W \notin L_u$? $\endgroup$ – user129186 Jun 8 '16 at 8:46

Any language accepted by a non-deterministic Turing machine is decidable, since non-deterministic Turing machines can be simulated by deterministic Turing machines. See for example the Wikipedia article.

There is some subtlety you might be worried about: the non-deterministic Turing machine might always halt (on a given input), but its running time could be unbounded, and then the trivial simulation which just tries all possible guesses wouldn't halt. Fortunately, König's infinity lemma shows that if the running time is unbounded, then there is some infinite computation, so the running time must be bounded.

| cite | improve this answer | |
  • $\begingroup$ Maybe I'm misunderstanding something or I asked the question incorrectly. I'm basically asking if the language $L_u \in R$, while we only know that $L_u \in RE$ and the fact about the space complexity. As far as I am aware, $L_u \in RE$ does not imply $L_u \in R$? $\endgroup$ – user129186 Jun 8 '16 at 8:21
  • $\begingroup$ Sorry, the use of verbs to express the difference between recursive and r.e. is beyond me. Usually "accepts" or "decides" denotes recursive, while "verifies" denotes r.e. $\endgroup$ – Yuval Filmus Jun 8 '16 at 8:24
  • $\begingroup$ Try to rephrase the question without using the verb "accepts", or the phrase "with memory complexity". Explain what you mean using more basic terms. $\endgroup$ – Yuval Filmus Jun 8 '16 at 8:25
  • $\begingroup$ I have clarified the question a bit. $\endgroup$ – user129186 Jun 8 '16 at 8:32

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.