However, Turing-incomplete sublanguages can be very helpful in practice, for the same reason that a `for` loop is very helpful even though it is not essential and we can solve all of our problems with `goto` which is ultimately what our compilers generate anyway. Why do most people prefer `for` to `goto`? because with the former, you pick up a writer's discipline which makes it harder to create infinite loops and to accidentally miss parts of the data structure.
Well, in any Turing-incomplete subset, it is impossible to make an infinite loop and usually very hard to miss parts of the data structure (since there is usually only a few ways to enter that data structure that the computer can prove won't halt) -- and, if you want, you can build tooling which checks your algorithms to guarantee these things. It guarantees that even any recursive handling you do with the data structure is not going to be infinite.
With that said, there are some examples of perfectly valid algorithms which don't nicely support that sort of structural recursion, e.g. if you can "jump down" to a much smaller (and sometimes hardly-related) data structure rather than incrementally descending into it. A great example of this is the GCD algorithm,
function gcd(x, y) {
if (y < x) {
return gcd(y, x);
}
return x == 0 ? y : gcd(y % x, x);
}
We can easily prove that this halts for positive integers by simply looking at the second parameter; each recursive call makes it strictly closer to 0, which means that it must hit 0 and stop recursing. But a Turing-incomplete subset would probably balk at both of the recursive calls, if, say, we tried to encode integers as lists of booleans to get a "binary"-ish representation: it will say "hey, you can't recurse on gcd(y, x) or gcd(y % x, x), because you're supposed to be going in gcd(x, y) from x to a substructure of x, but y and y % x are not substructures of x!"You might be able to do it by encoding everything as a list of nulls and then first invoking some sort of decrement-increment step to swap x and y, then doing something similar for the modulus, but it means that your runtime might be something like min(x, y) * max(x, y) or something -- ugly.