[chc4]

There's a difference between pathologically high complexity functions and Turing completeness. Sub-Turing languages generally don't allow recursion or unbounded loops - your program is always making progress. Solving 3-SAT doesn't sound like it precludes sub-Turing completeness, since you'd have a finite number of solutions you're iterating over.

It's still useful for a config language because it makes it harder to accidentally make a config that (in practice) never terminates, and usually allows for easier static analysis and refactoring of the config files through immutability and purity.

[contravariant]

On the one hand you're right, though at some point 'arbitrarily long' and Turing complete become pretty similar. In fact an ordinary computer isn't entirely a Turing machine either, as its memory is limited.

Also it means you need to be careful about malicious input, you need to take countermeasures when you evaluate an expression from an untrusted source.

[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.