HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What does the phrase "Simple For Loops" mean in computability theory?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thesimplewhattheoryloopsmeancomputabilityphrasefordoes

Problem

I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me?

The Phrase:
An upper bound of the number of iterations of every loop can be determined before entering the loop

The Wikipedia page

Solution

The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input:

x ← 0
for i from 1 to A(n,n):
    x ← x + 1
return x


This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time.

A better explanation is the LOOP programming languages. Every loop in LOOP runs $x_i$ times, where $x_i$ is a variable, and the number of iterations is the value of $x_i$ before the loop is run. For example:

LOOP x DO
      x ← x + 1
  END


is a problem that doubles $x$, and

z ← 0
  LOOP x DO
      z ← z + 1
  END
  LOOP y DO
      z ← z + 1
  END


is a problem that assigns $x + y$ to $z$.

A function can be computed in LOOP (using a reasonable input/output convention) iff it is primitive recursive. So if you only allow loops in which the number of iterations is the value of some variable just before the loop, then the resulting function will be primitive recursive, and furthermore, every primitive recursive function can be computed only using such loops.

Code Snippets

x ← 0
for i from 1 to A(n,n):
    x ← x + 1
return x
LOOP x DO
      x ← x + 1
  END
z ← 0
  LOOP x DO
      z ← z + 1
  END
  LOOP y DO
      z ← z + 1
  END

Context

StackExchange Computer Science Q#126254, answer score: 5

Revisions (0)

No revisions yet.