# Does a type-1 automaton always have to terminate?

For push-down automata it seems obvious to me that a program must always terminate (given the input is finite), because for each input symbol they advance until eventually they run out of symbols and then terminate.

The opposite is true for Turing machines as they read their input from the tape and are able to alter the position in the input string.

Linear bounded automata are basically Turing machines that have to operate on a bounded range on the tape. As far as I can see, that doesn't prevent you from writing a program for such a machine that just toggles between two states infinitely and thus never terminates.

Is this assumption correct? And can we infer anything about the language an automaton is able to accept from the property if it must terminate eventually? I'm a bit confused about the fact that type-1 languages are a subset of the decidable languages, where the decidable languages require an always halting Turing machine, but I can't find any such restriction for linear bounded automata.

Pushdown automata do not necessarily halt. They are not forced to read input each step, they can also do so-called $$\lambda$$-instructions where the tape is not advanced. Then we can have an infinite loop at a certain tape position.
• Are those $\lambda$-instructions equal to $\varepsilon$-transitions in DFAs? I've never heard of them. – siracusa Sep 30 '19 at 13:17
• Yes, $\varepsilon$ transitions, as they are called in Wikipedia for example. – Hendrik Jan Sep 30 '19 at 14:09