<p>Having just asked a <a href="https://cstheory.stackexchange.com/questions/14641/simply-stated-restriction-on-imperative-programming-language-that-captures-the-e/14655">very similar question</a>:</p>

<p>The language of <code>for</code> programs can express exactly the primitive recursive functions -- see Meyer, A.R., Ritchie, D.M. (1967), <em>The complexity of loop programs</em>, Proc. of the ACM National Meetings, 465.  (I found a copy online <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9311&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">here</a>.)</p>

<p>The complexity class for the p.r. functions is called <strong><a href="http://en.wikipedia.org/wiki/PR_%28complexity%29" rel="nofollow noreferrer">PR</a></strong>.</p>

CC BY-SA 3.0
2012-12-07T12:23:02.520Z
2012-12-07T12:23:02.520Z
2017-04-13T12:32:28.080Z
Chris Pressey
<p>This is the language <a href="http://en.wikipedia.org/wiki/BlooP_and_FlooP" rel="nofollow">Bloop</a> as describes by Hofstaedter.</p>

CC BY-SA 3.0
2012-10-14T17:55:56.617Z
2012-10-14T18:06:10.353Z
2012-10-14T18:06:10.353Z
bloop
<p>I've written an unpublished paper that describes FOR-programs.</p>

<p>FOR-programs are programs that only contain bounded for loops and basic operations (assignment, addition, multiplication, etc.). A bounded for loop is a for loop with a bound on the number of times that it can loop. This bound is fixed before entering the for loop for the first time and is not changed until the loop completes. </p>

<p>Is there a complexity class that captures this type of programs? Since the number of for loops in a program is known in advance, the time complexity is of course limited to $O(n^k)$ with $k$ nested for loops. Thus, all FOR-programs run in polynomial time. Are there additional limitations to this class of programs?</p>

CC BY-SA 3.0
2012-10-13T18:03:33.043Z
These sound like the primitive recursive functions.
Yuval Filmus
CC BY-SA 3.0
2012-10-13T23:05:00.223Z
These programs are not bounded to polynomial time. If you interpret the input (perhaps expressed in binary) as an integer, it may be polynomial in the value of the integer; but not in the length of its representation. For instance, a program `unsigned int identity(unsigned  int x) { unsigned int y; for (y = 0; y < x; y++); return y; }` performs $x$ iterations, which requires $\Omega(x) = \Omega(2^n)$ time, where $n = |x|$ is the length of the representation of $x$, i.e. $n = \lceil \log_2(x+1) \rceil$ for $x \geqslant 0$.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-14T09:40:36.587Z
Related: http://cstheory.stackexchange.com/questions/5120/programming-languages-for-efficient-computation
Radu GRIGore
CC BY-SA 3.0
2012-10-14T23:31:37.853Z
@NieldeBeaudrap: true (I was more interested on the effects on arrays: what if the counters can't be modified before they are used on arrays, but somehow I didn't post that part).
willeM_ Van Onsem
CC BY-SA 3.0
2012-10-14T23:52:16.777Z
@CommuSoft: what you mean is still not clear. Do you mean that the input must be an array, and all loops are in terms of the size of the array? Please revise your question to state quite precisely what it is that you mean, because it is quite likely to have a bearing on what the answer will be.
Niel de Beaudrap
<cc.complexity-theory><pl.programming-languages>
Is there a computation class describing FOR-programs, what are the limitations?
willeM_ Van Onsem
# Is there a computation class describing FOR-programs, what are the limitations?

(Asked by: username_0 on 2012-10-13)

I've written an unpublished paper that describes FOR-programs.

FOR-programs are programs that only contain bounded for loops and basic operations (assignment, addition, multiplication, etc.). A bounded for loop is a for loop with a bound on the number of times that it can loop. This bound is fixed before entering the for loop for the first time and is not changed until the loop completes.

Is there a complexity class that captures this type of programs? Since the number of for loops in a program is known in advance, the time complexity is of course limited to $O(n^k)$ with $k$ nested for loops. Thus, all FOR-programs run in polynomial time. Are there additional limitations to this class of programs?

**Tags:** cc.complexity-theory, pl.programming-languages
> **Comments:**
> **username_1**: These sound like the primitive recursive functions.  
> **username_2**: These programs are not bounded to polynomial time. If you interpret the input (perhaps expressed in binary) as an integer, it may be polynomial in the value of the integer; but not in the length of its representation. For instance, a program `unsigned int identity(unsigned  int x) { unsigned int y; for (y = 0; y < x; y++); return y; }` performs $x$ iterations, which requires $\Omega(x) = \Omega(2^n)$ time, where $n = |x|$ is the length of the representation of $x$, i.e. $n = \lceil \log_2(x+1) \rceil$ for $x \geqslant 0$.  
> **username_3**: Related: http://cstheory.stackexchange.com/questions/5120/programming-languages-for-efficient-computation  
> **username_0**: @NieldeBeaudrap: true (I was more interested on the effects on arrays: what if the counters can't be modified before they are used on arrays, but somehow I didn't post that part).  
> **username_2**: @CommuSoft: what you mean is still not clear. Do you mean that the input must be an array, and all loops are in terms of the size of the array? Please revise your question to state quite precisely what it is that you mean, because it is quite likely to have a bearing on what the answer will be.  

---

## 2 answers

### Answer by username_4 on 2012-12-07. Score: 4 | Accepted answer

Having just asked a [very similar question](https://cstheory.stackexchange.com/questions/14641/simply-stated-restriction-on-imperative-programming-language-that-captures-the-e/14655):

The language of `for` programs can express exactly the primitive recursive functions -- see Meyer, A.R., Ritchie, D.M. (1967), *The complexity of loop programs*, Proc. of the ACM National Meetings, 465. (I found a copy online [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9311&rep=rep1&type=pdf).)

The complexity class for the p.r. functions is called **[PR](http://en.wikipedia.org/wiki/PR_%28complexity%29)**.


---

### Answer by username_5 on 2012-10-14. Score: 3

This is the language [Bloop](http://en.wikipedia.org/wiki/BlooP_and_FlooP) as describes by Hofstaedter.


---

