For a language $L$, you can talk about the complexity of a Turing machine $M$ which decides $L$. Can you talk about the time complexity of the language $L$ itself, i.e. say $L$ has complexity $f(n)$ iff
- There exists a Turing machine deciding $L$ in time $O(f(n))$
- All Turing machines deciding $L$ have complexity $\Omega(f(n))$
Under what conditions does a language have a (time or space) complexity in this way? Does it matter if you relax $O()$ and $\Omega()$ to ignore sublogarithmic, or logarithmic, or polynomial factors?
I am aware of some languages that do not have complexity, i.e. there is no single Turing machine which attains the lower bound on running time. For example, in the decision procedure for WS1S requires time at least $2 \uparrow \uparrow O(n)$, yet for any machine $M$ deciding WS1S, there is another such machine $M'$ which is exponentially faster than $M$.
