# The Grzegorczyk Hierarchy

Now to the other end of the subject, computational complexity. The two ends aren’t going to meet in the middle, but the Grzegorczyk Hierarchy is so simple it should be at the start by natural justice, and it’s good to have in mind as a pleasant ending point while getting lost in pregroup theory.

If you want to ask yourself whether a problem is computable or not, you have to define what you mean by ‘computable’. It’s left as an exercise for the reader, basically. So the popular thinking is that effectively computable functions and recursive functions are the same thing – that is, every computable function should be recursive.

Furthermore, a slightly smaller class of functions, the primitive recursive functions, contains pretty much everything anyone’s interested in, and leaves out horror shows like the Ackermann function.

The idea is that you can start with a few really simple initial functions: zero; successor; projection, and the operations of composition and recursion, and end up with pretty much every function on the natural numbers that anyone’s ever thought up. (( before this was claimed and people tried to think of things that weren’t included in this class, anyway ))

A *primitive recursive* function is one which can be defined by finitely many compositions and recursions on the initial functions. A generally *recursive* function can be defined using unbounded minimisation as well, but remember that we’re deliberately ignoring those.

## Basic building bits

These are the functions we’ll begin with:

, the zero function$o(x)=0$ , the successor function$s(x)=x+1$ , the projection function${p}_{n}^{i}({x}_{1},\dots ,{x}_{n})={x}_{i}$ is an (n)-ary function which gives you the${p}_{n}^{i}$ $i$ ^{th}parameter passed in to it.

The projection function just gets round the problem of functions having different arities – different numbers of arguments. Real Red-Blooded Americans like Haskell Curry did everything with only unary functions in

Ok, so you’ve got your initial functions. Now I’ll let you define new functions by composing two you’ve already got together, so something like

means that$h=C(f,{g}_{1},\dots ,{g}_{m})$ .$h({x}_{1},\dots ,{x}_{n})=f({g}_{1}({x}_{1},\dots ,{x}_{n})),\dots ,{g}_{m}({x}_{1},\dots ,{x}_{n}))$ means that$h=R(f,g)$ , and$h(x,0)=f(x)$ (( Note that the definition defines for$h(x,n+1)=g(x,n+1,h(x,n))$ in terms of$n+1$ , instead of$n$ for$n$ . Also notice that we haven’t used any subtraction at all yet. It’ll appear eventually as a weird byproduct of addition. Finally, adjust this definition yourself for$n-1$ -ary functions$n$ ))$f$

The idea with recursion is that you add an extra parameter

## Complexity

Now we ask ourselves about complexity. Some functions are definitely harder to compute than others, so how do we define that in a rigorous way? Let’s look at the way functions are made – by composition or by recursion. Composing two functions together can only take as long as working one out then the other, so the time of computation is still on the same order of magnitude as the composed functions. Recursion, however, could entail an arbitrary number of computations of the basic functions, so this is the thing I think we need to pay attention to.

Simply counting the number of recursions involved in the definition of a function would be the obvious way to start, but how about

Anyway, a different angle of attack is needed, and a clever Polish mathematician thought of one.

## The Grzegorczyk Hierarchy

### The start

We’ll start with the initial functions, and try to create the class of all functions that are about as complicated as they are.

This class will be closed under composition, because we’ve decided composition doesn’t count for much. By composing the successor function with itself, we can get

Clearly allowing any recursion would get you the whole class of primitive recursive functions in one sweep, so I’ll say that you can define new functions by recursion, but only if they are bounded everywhere by some other function you’ve already got. So, a function

The class we’re creating is closed under bounded recursion. This doesn’t actually get us all that much. For example, we can’t have the addition function, because there is no constant

Boring starting class defined, let’s call it

### The hierarchy

What was holding us back in

What can we get now? Well, we can add arbitrarily many number together to start with, since

So taking

If we define suitable

Finally, we say that

Tedious souls can show that all of the elementary functions reside in

It turns out that the union of all the

## References

Computability and Unsolvability, Martin Davis