In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we could use the LBA and the finite countable set of possible configurations to diagonalize a TM out of this set or something along those lines.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
answered Sep 10, 2021 at 16:22