[blonde_ocean]

How do you mean sub-Turing languages don’t allow recursion? Aren’t context-free languages, for example, literally recursive?

[remexre]

"Arbitrary recursion" is the correct claim; e.g. Coq allows recursion, but has restrictions so all programs terminate.

[codebje]

I assume GP means general recursion.

Recursion in a pushdown automata (the equivalent machine for a CFL) is bounded by the input words being consumed, since each state transition consumes one input token. Since all input words are finite, indefinite recursion is excluded.