# Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this:

Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.

I could see that linear-bounded automaton is directly below decider in the article's ordering. If this is the case, then that means every computation on a LBA will halt at some point (since every LBA would be a decider). But I feel that there may be some computation which can run on a LBA at the same time never to halt. For example we can write a computation on LBA which would

1. read the first symbol on the tape and move right;
2. read the next symbol and move back left.

This (useless) computation (which is obviously a LB computation) would run indefinitely oscillating left and right and never halt and hence cannot be a decider. Where am I thinking wrong?

• Deciding a CSL is independent of whether there are non-terminating LBA: there only has to exist an LBA for it. – Raphael Oct 17 '12 at 12:37

First, all context-sensitive languages are decidable, since they can be accepted by a LBA (as you said), and a Turing machine is more powerful than a LBA.

However, you were asking about something else. Can there be LBA that cycles? The answer is yes. You gave an example. However, you can modify every LBA $M$ to a Turing machine $M'$ that accepts the same language but never cycles. To see this, observe, that you can simulate $M$ on $M'$ and keep track of all configurations the LBA has attained so far. If there is one configuration that shows up twice, you detected a cycle. In this case you stop rejecting. The important thing here is that the LBA uses on linear space, and hence the number of its configurations is bounded.

• If anyone still did not understand this answer, I suggest you refer to Slide 3-4 of this presentation for additional explanation. – bongubj Oct 17 '12 at 6:19

I suggest you take a look at this book: Introduction to Languages and the Theory of Computation by John E Martin

page 283: There are still open questions concerning context-sensitive languages, such as whether or not every CSL can be accepted by a deterministic LBA.

• How does this answer the question? Context-sensitive languages are all decidable, irrespective of whether you need deterministic or nondeterministic linear space. – Yuval Filmus Dec 14 '17 at 9:08