HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can you diagonalize a language out of CSL?

Submitted by: @import:stackexchange-cs··
0
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.