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.

Likewise, linear bounded automata may loop, and do not always halt. However, they can be simulated by a Turing machine, which stores each configuration, and tests for loops. That is not efficient of course, but can be done. In that way we get halting machines, but of a different type.

  • $\begingroup$ Are those $\lambda$-instructions equal to $\varepsilon$-transitions in DFAs? I've never heard of them. $\endgroup$
    – siracusa
    Sep 30 '19 at 13:17
  • $\begingroup$ Yes, $\varepsilon$ transitions, as they are called in Wikipedia for example. $\endgroup$ Sep 30 '19 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.