<p>My guess based purely on the definition: one answer might be "restriction of loops to <em>embarassingly parallel</em> <code>for</code> loops".</p>

<p>My working definition of "embarassingly parallel <code>for</code> loop" is one in which no iteration has any data dependency on any other iteration and there is a binary reducer function for aggregating the output (along with a base case). Bonus embarrassment points if the reducer function is associative, but I don't know if that distinction would limit the power of the language.</p>

<p>If we limit the allowable reducers to addition and multiplication, it seems likely to me that any program implemented under these restrictions can be written as an elementary recursive function (and vice versa). I'm less sure about more general reducers.</p>

<p>So a fun way to put it is that your language's only looping construct is MapReduce.</p>

<p>I am a non-expert in the area, but I'd like to propose this as a hypothesis and see what people's opinions are.</p>

<p><em>Edit</em>. To prove or disprove this fact, we could use a useful characterization from Meyer and Ritchie: A LOOP program implements an elementary function if it runs in time $O(2^{2^{\dots^{n}}})$ where $\dots$ represents a tower of some fixed size $k$.</p>

<p>This seems clearly true of parallel-<code>for</code> programs when the reducer function is limited to addition or multiplication, but seems to be untrue for a more broad choice of reducer. I would like to find that we can get the elementary functions whenever we restrict the reducer to run in polynomial time (multiplication is linear in this model), but I'll have to try to work it out.</p>

<p><em>Edit 2</em>. Right, so it looks like we should allow exactly the reducer functions that run in polynomial time in order to recover the elementary recursive functions.[1] Then we notice that this restriction is not that interesting, because the polynomial functions in this model are just those expressible by programs with a single <code>for</code> loop or a parallel-<code>for</code> loop with a non-looping reducer function. So we've basically just recovered the restriction that programs have up to two nested <code>for</code> loops, but we've just moved that restriction into the reducer function.</p>

<p><strong>Summary: Characterization seems to be true for reducers that run in polynomial time. It's unclear if this is at all interesting.</strong></p>

<p>[1]: On input $n$, let the reducer function run in time $O(n^k)$ for some $k$. We can roughly argue by induction that a program containing nested parallel-<code>for</code> loops runs in time $2^{2^{\dots^n}}$ for some constant-sized stack of exponents.</p>

<p>In an embarrassingly parallel <code>for</code> loop on input $n$, we can run up to $n$ iterations, each of which (since they're independent) runs in time up to $f(n)$. Suppose for induction $f(n) \in O(2^{2^{\dots^n}})$ for some constant-depth exponential stack.</p>

<p>If the reducer function is $p$, the <code>for</code> loop consists of $n$ compositions of $p$ on an input of size $f(n)$: $p(f(n),p(f(n),\dots))$. By assumption the running time on input size $x$ is bounded by $x^k$ for each step of the reducer, so it runs in time $O(f(n)^{k^n})$, which is asymptotically dominated by $f(n)^{2^{2^n}}$. By inductive assumption, $f(n)$ was bounded by $2^{\dots^n}$ for some constant-sized stack of exponents, so the same must be true for our running time.</p>

<p>And on the other hand, of course, if the reducer runs in exponential time, then this argument will fail and we'll get an exponential stack whose size depends on $n$, which means we can implement a non-elementary recursive function.</p>

CC BY-SA 3.0
2012-12-06T20:46:31.900Z
2012-12-08T04:58:57.213Z
2012-12-08T04:58:57.213Z
usul
<p>According to a classic result of Meyer and Ritchie (mentioned in the paper cited in the question), the elementary functions are characterized by LOOP programs in which the nesting depth of for-loops is restricted to be at most 2.</p>

CC BY-SA 3.0
2012-12-07T12:14:29.520Z
Thank you.  Following up on usul's follow-up, for _n_ >= 2, LOOP programs with nesting depth _n_ correspond to _n_+1-th set in the Grzegorczyk hierarchy.
Chris Pressey
CC BY-SA 3.0
2012-12-07T09:36:25.153Z
2012-12-07T09:36:25.153Z
Jan Johannsen
<p>The language of <code>while</code> programs can express the computably enumerable functions.  (This is true even if the only arithmetical operations on variables are, say, incrementation and decrementation.)</p>

<p>If <code>while</code> is replaced by <code>for</code>, making loops always bounded, the language can then express only the primitive recursive functions.</p>

<p>I recently became aware of the class of <a href="http://en.wikipedia.org/wiki/ELEMENTARY">elementary functions</a>, which are strictly below the primitive recursive functions, but still strictly above the exponential hierarchy.</p>

<p>Obviously it would be possible to define an imperative programming language which captures exactly the elementary functions, say by introducing operators for bounded sum and product.  However, my question is,</p>

<blockquote>
  <p>Is there a syntactic change to the language of <code>while</code> programs which restricts it to the elementary functions and which can be stated as simply as the (<code>while</code> -> <code>for</code>) restriction to primitive recursive functions?</p>
</blockquote>

<p>A restriction on <code>for</code> programs instead would also suffice, of course, and perhaps I should clarify that I'm not looking for something that is <em>absolutely</em> as simply-stated, just something with comparable simplicity which does not require the addition of extra operators or the like.</p>

<p><strong>Edit</strong>: An example of a representative <code>for</code> language is PL-{GOTO} from Brainerd and Landweber's "Theory of Computation" (1974), in which each program has a finite but unrestricted number of variables, each of which can contain a natural number, and which consists essentially of the following commands:</p>

<ul>
<li><code>X &lt;- 0</code> (assign 0 to a variable)</li>
<li><code>X &lt;- Y</code> (assign the value of <code>Y</code> to <code>X</code>)</li>
<li><code>X &lt;- Y + 1</code> (assign the successor of the value of <code>Y</code> to <code>X</code>)</li>
<li><code>LOOP X; ... END;</code> (repeat the contained block of code <code>X</code> times; does not alter <code>X</code>)</li>
</ul>

<p>The authors give a proof that this can express exactly the primitive recursive functions.  The language PL does not match the question perfectly, as it uses <code>GOTO</code> instead of <code>while</code>, and PL-{GOTO} is derived from PL by removing <code>GOTO</code> from it.  However, PL programs are just as powerful as <code>while</code> programs, and this <code>GOTO</code>-removal transformation is just as simply stated as replacing <code>while</code> with <code>for</code>.  (Arguably perhaps even a bit simpler.)</p>

<p><strong>Edit 2</strong>: <a href="http://en.wikipedia.org/wiki/Total_Turing_machine">http://en.wikipedia.org/wiki/Total_Turing_machine</a> suggests this result goes back to: Meyer, A.R., Ritchie, D.M. (1967), <em>The complexity of loop programs</em>, Proc. of the ACM National Meetings, 465.</p>

CC BY-SA 3.0
2012-12-06T13:14:00.167Z
Does your language have arrays? Presumably only variables holding natural numbers, and booleans. Anyhow, I always thought that the primitive recursive functions corresponded to `for` loops, but I have never seen a proof. Have you?
Andrej Bauer
CC BY-SA 3.0
2012-12-06T13:39:12.987Z
@AndrejBauer: I don't have a copy with me right now, but I believe Brainerd and Landweber give a proof in their textbook Theory of Computation (1974). They show a toy language, PL, which has both `LOOP` (what I've called `for`) and `GOTO`, is Turing-complete, but that without `GOTO` it can only express the p.r. functions.  I will edit the question to include a brief description of this language.
Chris Pressey
CC BY-SA 3.0
2012-12-07T09:53:26.647Z
Following up on Jan's answer, this is helpful: http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy
usul
<cc.complexity-theory><computability><pl.programming-languages>
Simply-stated restriction on imperative programming language that captures the elementary functions?
Chris Pressey
# Simply-stated restriction on imperative programming language that captures the elementary functions?

(Asked by: username_0 on 2012-12-06)

The language of `while` programs can express the computably enumerable functions. (This is true even if the only arithmetical operations on variables are, say, incrementation and decrementation.)

If `while` is replaced by `for`, making loops always bounded, the language can then express only the primitive recursive functions.

I recently became aware of the class of [elementary functions](http://en.wikipedia.org/wiki/ELEMENTARY), which are strictly below the primitive recursive functions, but still strictly above the exponential hierarchy.

Obviously it would be possible to define an imperative programming language which captures exactly the elementary functions, say by introducing operators for bounded sum and product. However, my question is,

> Is there a syntactic change to the language of `while` programs which restricts it to the elementary functions and which can be stated as simply as the (`while` -> `for`) restriction to primitive recursive functions?

A restriction on `for` programs instead would also suffice, of course, and perhaps I should clarify that I'm not looking for something that is *absolutely* as simply-stated, just something with comparable simplicity which does not require the addition of extra operators or the like.

**Edit**: An example of a representative `for` language is PL-{GOTO} from Brainerd and Landweber's "Theory of Computation" (1974), in which each program has a finite but unrestricted number of variables, each of which can contain a natural number, and which consists essentially of the following commands:

* `X <- 0` (assign 0 to a variable)
* `X <- Y` (assign the value of `Y` to `X`)
* `X <- Y + 1` (assign the successor of the value of `Y` to `X`)
* `LOOP X; ... END;` (repeat the contained block of code `X` times; does not alter `X`)

The authors give a proof that this can express exactly the primitive recursive functions. The language PL does not match the question perfectly, as it uses `GOTO` instead of `while`, and PL-{GOTO} is derived from PL by removing `GOTO` from it. However, PL programs are just as powerful as `while` programs, and this `GOTO`-removal transformation is just as simply stated as replacing `while` with `for`. (Arguably perhaps even a bit simpler.)

**Edit 2**: <http://en.wikipedia.org/wiki/Total_Turing_machine> suggests this result goes back to: Meyer, A.R., Ritchie, D.M. (1967), *The complexity of loop programs*, Proc. of the ACM National Meetings, 465.

**Tags:** cc.complexity-theory, computability, pl.programming-languages
> **Comments:**
> **username_1**: Does your language have arrays? Presumably only variables holding natural numbers, and booleans. Anyhow, I always thought that the primitive recursive functions corresponded to `for` loops, but I have never seen a proof. Have you?  
> **username_0**: @AndrejBauer: I don't have a copy with me right now, but I believe Brainerd and Landweber give a proof in their textbook Theory of Computation (1974). They show a toy language, PL, which has both `LOOP` (what I've called `for`) and `GOTO`, is Turing-complete, but that without `GOTO` it can only express the p.r. functions.  I will edit the question to include a brief description of this language.  
> **username_2**: Following up on Jan's answer, this is helpful: http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy  

---

## 2 answers

### Answer by username_3 on 2012-12-07. Score: 8 | Accepted answer

According to a classic result of Meyer and Ritchie (mentioned in the paper cited in the question), the elementary functions are characterized by LOOP programs in which the nesting depth of for-loops is restricted to be at most 2.

> **Comments:**
> **username_0**: Thank you.  Following up on usul's follow-up, for _n_ >= 2, LOOP programs with nesting depth _n_ correspond to _n_+1-th set in the Grzegorczyk hierarchy.  

---

### Answer by username_2 on 2012-12-06. Score: 1

My guess based purely on the definition: one answer might be "restriction of loops to *embarassingly parallel* `for` loops".

My working definition of "embarassingly parallel `for` loop" is one in which no iteration has any data dependency on any other iteration and there is a binary reducer function for aggregating the output (along with a base case). Bonus embarrassment points if the reducer function is associative, but I don't know if that distinction would limit the power of the language.

If we limit the allowable reducers to addition and multiplication, it seems likely to me that any program implemented under these restrictions can be written as an elementary recursive function (and vice versa). I'm less sure about more general reducers.

So a fun way to put it is that your language's only looping construct is MapReduce.

I am a non-expert in the area, but I'd like to propose this as a hypothesis and see what people's opinions are.

*Edit*. To prove or disprove this fact, we could use a useful characterization from Meyer and Ritchie: A LOOP program implements an elementary function if it runs in time $O(2^{2^{\dots^{n}}})$ where $\dots$ represents a tower of some fixed size $k$.

This seems clearly true of parallel-`for` programs when the reducer function is limited to addition or multiplication, but seems to be untrue for a more broad choice of reducer. I would like to find that we can get the elementary functions whenever we restrict the reducer to run in polynomial time (multiplication is linear in this model), but I'll have to try to work it out.

*Edit 2*. Right, so it looks like we should allow exactly the reducer functions that run in polynomial time in order to recover the elementary recursive functions.[1] Then we notice that this restriction is not that interesting, because the polynomial functions in this model are just those expressible by programs with a single `for` loop or a parallel-`for` loop with a non-looping reducer function. So we've basically just recovered the restriction that programs have up to two nested `for` loops, but we've just moved that restriction into the reducer function.

**Summary: Characterization seems to be true for reducers that run in polynomial time. It's unclear if this is at all interesting.**

[1]: On input $n$, let the reducer function run in time $O(n^k)$ for some $k$. We can roughly argue by induction that a program containing nested parallel-`for` loops runs in time $2^{2^{\dots^n}}$ for some constant-sized stack of exponents.

In an embarrassingly parallel `for` loop on input $n$, we can run up to $n$ iterations, each of which (since they're independent) runs in time up to $f(n)$. Suppose for induction $f(n) \in O(2^{2^{\dots^n}})$ for some constant-depth exponential stack.

If the reducer function is $p$, the `for` loop consists of $n$ compositions of $p$ on an input of size $f(n)$: $p(f(n),p(f(n),\dots))$. By assumption the running time on input size $x$ is bounded by $x^k$ for each step of the reducer, so it runs in time $O(f(n)^{k^n})$, which is asymptotically dominated by $f(n)^{2^{2^n}}$. By inductive assumption, $f(n)$ was bounded by $2^{\dots^n}$ for some constant-sized stack of exponents, so the same must be true for our running time.

And on the other hand, of course, if the reducer runs in exponential time, then this argument will fail and we'll get an exponential stack whose size depends on $n$, which means we can implement a non-elementary recursive function.


---

