patternMinor
What does the phrase "Simple For Loops" mean in computability theory?
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
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:
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:
is a problem that doubles $x$, and
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.
x ← 0
for i from 1 to A(n,n):
x ← x + 1
return xThis 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
ENDis a problem that doubles $x$, and
z ← 0
LOOP x DO
z ← z + 1
END
LOOP y DO
z ← z + 1
ENDis 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 xLOOP x DO
x ← x + 1
ENDz ← 0
LOOP x DO
z ← z + 1
END
LOOP y DO
z ← z + 1
ENDContext
StackExchange Computer Science Q#126254, answer score: 5
Revisions (0)
No revisions yet.