1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Are you familiar with the LOOP programming language? $\endgroup$ – ttnick Apr 30 '20 at 6:49
  • $\begingroup$ @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. $\endgroup$ – Ramit Apr 30 '20 at 7:08
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Hi @Yuval Filmus thanks for answering the question. $\endgroup$ – Ramit Apr 30 '20 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.