patternMinor
Can you diagonalize a language out of CSL?
Viewed 0 times
cancsldiagonalizeyoulanguageout
Problem
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.
Solution
This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
Context
StackExchange Computer Science Q#143822, answer score: 4
Revisions (0)
No revisions yet.