# 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, 2012 at 12:37

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.