0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Yes. ​ ​ $\endgroup$
    – user12859
    Commented Jun 8, 2016 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
    Commented Jun 8, 2016 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
    Commented Jun 8, 2016 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
    Commented Jun 8, 2016 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
    Commented Jun 8, 2016 at 8:46

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Jun 8, 2016 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
    Commented Jun 8, 2016 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
    Commented Jun 8, 2016 at 8:25
  • $\begingroup$ I have clarified the question a bit. $\endgroup$
    – user129186
    Commented Jun 8, 2016 at 8:32

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.