The naive way of deciding it it halts is executing it and keep track of all state between steps. If the machine halts, you're done, if it repeats a state, it's

The naive way of deciding it it halts is executing it and keep track of all state between steps. If the machine halts, you're done, if it repeats a state, it's looping. If you can represent a program with an LBA, it is by definition a context sensitive language and decidable. You could also show it by making a equivalent gramma for the language, that accepts the same input as the program. This gramma must be constructed in a certain way, and then you know it is a context sensitive language.