Wikipedia https://en.wikipedia.org/wiki/Primitive_recursive function says.

“In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop).”

Where can I find a proof of this?
Who first proved it?
Link?

Thanks,
C-B

On Sunday, July 24, 2022 at 6:21:40 PM UTC-7, Charlie-Boo wrote:
> Wikipedia https://en.wikipedia.org/wiki/Primitive_recursive function says..
>
> “In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop).”
>
> Where can I find a proof of this?
> Who first proved it?
> Link?
>
> Thanks,
> C-B

What makes the recursion "primitive", though?

On 7/26/2022 8:11 PM, Jeffrey Rubard wrote:
> On Sunday, July 24, 2022 at 6:21:40 PM UTC-7, Charlie-Boo wrote:
>> Wikipedia https://en.wikipedia.org/wiki/Primitive_recursive function says.
>>
>> “In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop).”
>>
>> Where can I find a proof of this?
>> Who first proved it?
>> Link?
>>
>> Thanks,
>> C-B
>
> What makes the recursion "primitive", though?

I am pretty sure that it is this:
roughly speaking a function that can be computed by a computer program
whose loops are all "for" loops

More complex function that cannot be computed using only "for" loops are
not primitive.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 7/26/22 9:19 PM, olcott wrote:
> On 7/26/2022 8:11 PM, Jeffrey Rubard wrote:
>> On Sunday, July 24, 2022 at 6:21:40 PM UTC-7, Charlie-Boo wrote:
>>> Wikipedia https://en.wikipedia.org/wiki/Primitive_recursive function
>>> says.
>>>
>>> “In computability theory, a primitive recursive function is roughly
>>> speaking a function that can be computed by a computer program whose
>>> loops are all "for" loops (that is, an upper bound of the number of
>>> iterations of every loop can be determined before entering the loop).”
>>>
>>> Where can I find a proof of this?
>>> Who first proved it?
>>> Link?
>>>
>>> Thanks,
>>> C-B
>>
>> What makes the recursion "primitive", though?
>
> I am pretty sure that it is this:
> roughly speaking a function that can be computed by a computer program
> whose loops are all "for" loops
>
> More complex function that cannot be computed using only "for" loops are
> not primitive.
>

Nope, that isn't the definition, that is a proven result.

THe definition is later in the page starting at:

Definition[edit]
A primitive recursive function takes a fixed number of arguments, each a
natural number (nonnegative integer: {0, 1, 2, ...}), and returns a
natural number. If it takes n arguments it is called n-ary.

The basic primitive recursive functions are given by these axioms:

(the axioms don't copy to plain text but include Constant, Successor,
Project)

More complex primitive recursive functions can be obtained by applying
the operations given by these axioms:

(these don't copy either but include Composition, and the Primative
Recursive Operator)

(and then it ends with:)

The primitive recursive functions are the basic functions and those
obtained from the basic functions by applying these operations a finite
number of times.

So a primitive recursive function is one that you can build from the
defined basic functions (Constant, Successor, Projection) and the
operatiors (Composition and the Primative Recursive Operatior).

On 7/26/2022 8:31 PM, Richard Damon wrote:
> On 7/26/22 9:19 PM, olcott wrote:
>> On 7/26/2022 8:11 PM, Jeffrey Rubard wrote:
>>> On Sunday, July 24, 2022 at 6:21:40 PM UTC-7, Charlie-Boo wrote:
>>>> Wikipedia https://en.wikipedia.org/wiki/Primitive_recursive function
>>>> says.
>>>>
>>>> “In computability theory, a primitive recursive function is roughly
>>>> speaking a function that can be computed by a computer program whose
>>>> loops are all "for" loops (that is, an upper bound of the number of
>>>> iterations of every loop can be determined before entering the loop).”
>>>>
>>>> Where can I find a proof of this?
>>>> Who first proved it?
>>>> Link?
>>>>
>>>> Thanks,
>>>> C-B
>>>
>>> What makes the recursion "primitive", though?
>>
>> I am pretty sure that it is this:
>> roughly speaking a function that can be computed by a computer program
>> whose loops are all "for" loops
>>
>> More complex function that cannot be computed using only "for" loops
>> are not primitive.
>>
>
> Nope, that isn't the definition, that is a proven result.
>
> THe definition is later in the page starting at:
>
> Definition[edit]
> A primitive recursive function takes a fixed number of arguments, each a
> natural number (nonnegative integer: {0, 1, 2, ...}), and returns a
> natural number. If it takes n arguments it is called n-ary.
>
> The basic primitive recursive functions are given by these axioms:
>
> (the axioms don't copy to plain text but include Constant, Successor,
> Project)
>
> More complex primitive recursive functions can be obtained by applying
> the operations given by these axioms:
>
> (these don't copy either but include Composition, and the Primative
> Recursive Operator)
>
> (and then it ends with:)
>
> The primitive recursive functions are the basic functions and those
> obtained from the basic functions by applying these operations a finite
> number of times.
>
>
>
> So a primitive recursive function is one that you can build from the
> defined basic functions (Constant, Successor, Projection) and the
> operatiors (Composition and the Primative Recursive Operatior).

That sounds correct to me, without verifying that it is correct myself.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 2022-07-25 01:21:39 +0000, Charlie-Boo said:

> Wikipedia https://en.wikipedia.org/wiki/Primitive_recursive function says.
>
> “In computability theory, a primitive recursive function is roughly
> speaking a function that can be computed by a computer program whose
> loops are all "for" loops (that is, an upper bound of the number of
> iterations of every loop can be determined before entering the loop).”
>
> Where can I find a proof of this?

In is almost proven on that Wikipedia page. Most rules of the definition
don't need any kind of loop. In the rule that needs one the loop is
clearly bound by the value of the first argument so a for loop can be
used, with a bound that is known before the loop is started.

Mikko