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
- read the first symbol on the tape and move right;
- 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?