# More the number of for loops greater the problems solved

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

• Are you familiar with the LOOP programming language? – ttnick Apr 30 '20 at 6:49
• @ttnick I wasn't familiar with the LOOP language. I think it captures the essence of the question I wish to ask here. So LOOP syntax with only $i$ many invocations of LOOP would correspond to the kind of question I'm going for. The LOOP programming language in general captures the primitive recursive functions. Now I wish to know if there is something known about the more finer usages of the Loop syntax, the wiki article doesn't mention such a result. – Ramit Apr 30 '20 at 7:08

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