Newsgroups: sci.math
From: eclrh@sun.leeds.ac.uk (Robert Hill)
Subject: Re: help:primitively recursively functions
Date: Tue, 20 Jan 1998 17:19:30 +0000 (GMT)

In article <69ra19$l88@everest.vol.it>, "Mauro Panarello" <mpanare@tin.it> writes:
> I  need some informations on P.R. functions.
> 1. can you explain in some words what are exactly ?
> 2. is the following function a P.R. function? why?:
>         M(x1,x2)= 1 if x1 < x2
>                            0 else
> thank you wery much
> Mauro (italy).

The usual term in English is "primitive recursive", though "primitively
recursive" might have been more grammatical.
   
PR functions arise in the theory of computability.
I think the name may have been first used by Goedel in his famous
paper on undecidable sentences.

They are usually defined as taking one or more natural numbers as
arguments and giving a natural number as a result, but they
can also be defined in other contexts (e.g. functions that operate on
any integers (positive or negative) or on strings). 

You can find a definition, examples and a few references at
http://public.logica.com/~stepneys/cyc/p/primrec.htm.
(This is the first of 700 references that I found by an AltaVista
search for "primitive recursive".)  They are also defined in many books
on logic or computability.

The general idea is that we say that 

(i)  certain extremely simple functions are PR
     (e.g. constant functions; 
           the successor function s where s(x) = x+1;
           projection functions such as f where f(x,y,z,t) = y)
               
(ii) functions obtained by composing PR functions are PR
     (e.g. if f and g are PR, then so is h where h(x,y,z) = f(x, g(y,z)))

(iii) a simple sort of inductive definition is allowed.
      For example, if we wanted to define x + y for all natural numbers,
      in terms of the successor function s,
      we could do it by induction on y:

      x + 0 = x
      x + s(y) = s(x+y)

      This shows that addition is a PR function.
      
(iv) A function is PR only if it follows from (i), (ii), (iii).

Yes, your function M is primitive recursive.  I'll leave it to you
to work out why. 

There are other, equivalent ways of defining PR functions.
I'll mention one that may be easier to think about if you've done any 
computer programming, 

Imagine an idealised computer which works with natural numbers, 
and can store any natural number however big it may be.

A PR function is one that can be computed on this machine
using a simple programming language containing 
variables, constants, arithmetic operators and expressions, 
assignment statements, input and output statements, 
conditional (IF) statements, and the FOR statement discussed below.

(To avoid passing outside the natural numbers we have to modify the
definition of subtraction, and we have to do only whole number division,
but these are minor details.)   

The important thing is that the language does not have a general 
WHILE...DO statement (or a GO TO statement).  The only way to get 
a loop in this language is to use a FOR statement:

FOR i FROM a TO b DO ( sequence of statements ) END_DO 

and the important thing about the FOR statement is that, when it is executed,
the values of a and b are worked out once only at the start.

The important thing that you cannot do in this language is execute a series
of statements multiple times, and decide when to stop on the basis of
a value calculated during those statements.  If you were allowed to do this,
you would be able to compute any recursive function, primitive or not.

-- 
Robert Hill

University Computing Service, Leeds University, England

"Though all my wares be trash, the heart is true."
  - John Dowland, Fine Knacks for Ladies (1600)