Prove a function is primitive recursive

Question

Hey,

I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I really don't know how to go about doing so.

For example:

Let $\pi (x)$ be the number of primes that are $\le x$. Show that $\pi (x)$ is primitive recursive.

How do you go about proving this formally? And, in general, what are the necessary conditions to prove if something is or is not primitive recursive.

Note: this isn't homework, I've pulled the question out from a list of examples we have been given :)

Answer 1

This is not an exact answer, but it helps to quickly determine in many cases that a given function is primitive recursive. The idea is to use a reasonable programming language in which your function can be expressed more easily than with "raw" arithmetic and primitive recursion. Of course, the programming language must be limited enough to prevent unbounded searches and other constructs that lead to general recursion. I mention here just one easy possibility.

Suppose a function $f : \mathbb{N} \to \mathbb{N}$ is computed by a simple imperative program in polynomial running time (actually, as Grigory points out in his answer, any primitive recursive bound will do). More precisely, the program is allowed to use basic arithmetic operations, boolean values, variables, arrays, loops, and conditional statements. Then the function $f$ is primitive recursive.

The reason that such a program can only define a primitive recursive function is that the entire execution of the program may be encoded by a number $N$ whose bit size is bounded by a polynomial $p(n)$, where $n$ is the input. Because verifying that a number encodes the execution of a simple imperative program is primitive recursive, we can perform a bounded search up to $2^{p(n)}$ to find the number $N$ (such a bounded search is primitive recursive) and extract the answer from it.

Let us apply this to your question. The following Python program computes the function $\pi(n)$ and uses just a couple of loops and basic arithmetic (we could replace the remainder function % with another loop). Its running time is quadratic in $n$, assuming all basic operations are constant time:

def pi(n):
   '''Computes the number of primes which are less than or equal n.'''
   p = 0 # the number of primes found
   k = 2 # for each k we test whether it is prime
   while k <= n:
       j = 1 # possible divisors of k
       d = 0 # number of divisors of k found
       while j <= n:
           if k % j == 0: d = d + 1
           j = j + 1
       if d == 2: p = p + 1
       k = k + 1
   return p

Therefore your function is primitive recursive.

Answer 2

A conceptually simple test for whether a function is primitive recursive is whether or not you can write it in Bloop.

The crucial point is that the loop control flow structure forces you to say in advance how many times it will loop.

Here's some example code for working with primes written in Bloop.

Answer 3

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive.

Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(y)$ is also primitive recursive. Then adapt this to prove what you want.

In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly. I'd love to hear about non-trivial sufficient conditions of a general nature, though...

There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are not primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.

Answer 4

There is a theorem that says that any function computable on a Turing machine in time that is a primitive recursive function of the length of the input is primitively recursive.

This theorem you can find here: http://en.wikipedia.org/wiki/Primitive_recursive_function

Your function is primitively recursive because it can be computed in $O(n^2)$ time (here $n$ is the length of the input) on a computer using some programming language like C++. The difference between the time needed to implement this algorithm in C++ and on a Turing machine is polynomial in the length of the input so the resulting time needed for implementation on a Turing machine is polynomial in $n$.

[edit] Proving that function is not primitive recursive is harder. There is a proof with diagonalization method that shows that there exists some not primitively recursive function. To construct some explicit function it can be noted that if function grows too fast than it is not primitively recursive. Ackerman's function has the right growth rate for this.

Answer 5

There is a theorem that says that any function computable on a Turing machine in time that is a primitive recursive function of the length of the input is primitively recursive.

This just mentioned result is a really powerful theorem with numerous applications.

It easily yields results like this one.

Assume g,h,p are prim rec. Then f is prim rec where

f(x,y)=g(x,y) if x times y is 0 and f(x+1,y+1)=h(x,y,f(x,f(x,p(x,y))),f(x+1,y)).

Trying to figure out "direct solutions" is more or less impossible.

So my recommendation: If course of values recursion and simultaneous recursion don't work try the theorem above.