More the number of for loops greater the problems solved

Question

This is more a formal language theory question.

Imagine a setting where you are given a very basic programming language where variable assignments etc are taken care of without any of the iteration capabilities. The only iteration capability of this primitive language is having a for loop. I'm not sure if there is already such a language defined in literature, if yes, I'd be happy to know its name. Let an instance of this language be called a program. And I think we can understand that a program is usually written to solve a problem or a set or problems that can be solved by the same program with very minor modification to the program for each specific problem.

Now my question is. Let $P_i$ be the set of problems that can be solved by programs in the given primitive programming language that uses at most $i$ many for loops.

We understand $P_i \subseteq P_{i+1}$.

But can we write down a proof of $P_1 \subset P_2$? that is prove a separation !

I know this is "too wordy" may be someone can help formalise this question. And if someone can point out to relevant literature that already exists on this problem, it'd be a great help.

Its like the complexity resource being targeted here is the "for loop".

Answer 1

Let us consider the LOOP programming language. For a program $f$, denote by $f_{\max}(n)$ the maximal value of a variable at the end of the program, given that initially, all variables are at most $n$. If $f$ has only one loop then $f_{\max}(n) = O(n)$. In contrast, using two nested loops you can compute the product function, and the resulting program $g$ satisfies $g_{\max} = \Theta(n^2)$. This separates $P_1$ and $P_2$.

More generally, $f_{\max}$ can be bounded in terms of the maximum nesting depth of loops in $f$. If the maximum nesting depth is $d$, then the growing rate of $f_{\max}$ is comparable to the $d$th level of the Ackermann hierarchy. This allows us to separate $P_i$ and $P_{i+1}$ for every $i$.