2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Instead of Wikipedia, I suggest picking up a textbook or lecture notes. $\endgroup$ – Yuval Filmus May 25 '20 at 16:14
  • $\begingroup$ @YuvalFilmus Can you suggest any in this field? $\endgroup$ – ARK1375 May 25 '20 at 16:18
  • $\begingroup$ There are many resources, but I don't know any of them well enough to recommend. $\endgroup$ – Yuval Filmus May 25 '20 at 19:24
  • 1
    $\begingroup$ ARK1375, t the moment, "simple for loops" doesn't appear in that Wikipedia page. Did you mean "basic for loop", which does appear there? (The answers that people have given assume you kno what a for loop is. If not, "simple for loops" is ambiguous; to understand it, you have to parse "for loops" as an idiomatic noun phrase that's modified by "simple". The phrase doesn't imply that there is something that loops can do that is simple for them to do. The phrase "basic for loop" on the page includes a link to the Wikipedia page for for loop, btw.) $\endgroup$ – Mars May 25 '20 at 23:05
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A bit mystified why this got downvoted without a comment. Haters gonna hate... $\endgroup$ – Yuval Filmus May 26 '20 at 10:44
1
$\begingroup$

This line is quite self describing. Still, let me explain a bit. for loops works in a specific range of values. For example: When you iterate over an array, knowingly or unknowingly you known the length of that array, which means that you know the no. of iterations your loop will perform.

Take a look at the pseudo code below:

FRUITS = ["APPLE", "BANANA", "MANGO"]

FOR FRUIT OF FRUITS
    PRINT FRUIT

Above, the for loop will run 3 times, hence you know the no. of iterations before you even start that.

I hope know you understood that line well.

$\endgroup$

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.