All (mathematical) functions we meet in real world programs are
primitive recursive. I learned long ago that even though this is true it
doesn't mean we can in programming restrict ourselves to primitive
recursive definitions of primitive recursive functions -- with a
primitive recursive definition calculating either min(1,1000) or
min(1000,1) will take at least 1000 steps (on the straightforward
evaluation strategy). The problem is, I seem to have completely
forgotten where I learned this. Perhaps someone can jog my memory?

-- 
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, dar�ber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Aatu Koskensilta <aatu.koskensilta@uta.fi> writes:

> All (mathematical) functions we meet in real world programs are
> primitive recursive.

If you think about the functions you learn in school and even high
school, this is correct, though it become debatable when you talk about
functions over real numbers, as these can not be calculated exactly on a
digital computer.  But you can certainly compute arbitrarily good
approximations of these using primitive recursion.

> I learned long ago that even though this is true it
> doesn't mean we can in programming restrict ourselves to primitive
> recursive definitions of primitive recursive functions -- with a
> primitive recursive definition calculating either min(1,1000) or
> min(1000,1) will take at least 1000 steps (on the straightforward
> evaluation strategy). The problem is, I seem to have completely
> forgotten where I learned this. Perhaps someone can jog my memory?

Only the most naive primitive recursive defintion of these functions
(using unary number representation) will take that many steps.  With
binary number representation, you can do it in time linear in the number
of bits of the inputs (which is as good as you can get even with full
recursion).

When computer sicentists use unary number representation, they only care
about whether it is possible to compute a certain function using a
certain computational model, not how fast it can be done.  If they care
about this, they will use binary representation and be very careful
about what constitutes a step in the execution.

I don't recall any specific primitive recursive function where it has
been proven that it can be computed asymptotically faster using full
recursion than primitive recursion.  I don't recall any proves to the
contrary either, though, so it is possible that some such exist, in the
same way that it is possible that there are functions that can be
calculated in polynomial time on a nondeterministic TM but requires
exponential time on a deterministic TM.  It is fiendishly hard to prove
that a certain function requires superpolynomial time to compute.

	Torben