# Relating memory complexity and decidablity

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.

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?

• Yes. ​ ​ – user12859 Jun 8 '16 at 6:15
• Well, on what basis are you saying this? Is this related to the fact there are finitely many configurations of the memory space? – user129186 Jun 8 '16 at 7:06
• 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? – Yuval Filmus Jun 8 '16 at 8:36
• 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.) – Raphael Jun 8 '16 at 8:41
• 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$? – user129186 Jun 8 '16 at 8:46

• 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$? – user129186 Jun 8 '16 at 8:21