Primitive recursion

At this point, we have primarily discussed 1# computability for functions of words. Secondarily, we turned to computability of functions of numbers. We say “secondarily” here, becasuse the definition was indirect: to define computability of functions on numbers, we went through the somewhat artificial device of 1#. Since functions of numbers are so much more important than functions of words (at least to mathematics), we want to shift the focus in the subject. We start with a re-consideration of what it means to “compute in a simple sort of way” on thge natural numbers. Fairly soon, however, we return to 1# to connect it to what we do here.

!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *

Primitive recursive functions

Definition

Primitive recursive functions are functions \(N^k\to N\), where \(N\) is the set of natural numbers. So there are primitive functions of arity \(1\), \(2\), etc. There are also primitive recursive functions of arity \(0\) (for a technical reason.)

Primitive recursive terms are terms that denote primitive recursive functions.

We start with basic primitive recursive functions, as shown below:

z : this is the one-place function with value 0.

z_empty: this is the zero-place function with value 0.

s : this is the one-place successor function: \(f(n) = n+1\).

[proj, i, j] with i <= j: this is the ith projection on j variables.

Every primitive recursive function \(f\) has a fixed arity. That is, if \(f\) has arity \(k\), then \(f: N^k\to N\).

The way to understand the definition is that primitive recursive functions come with trees that show how they are built from the basic primitive recursive functions using the constructors of composition and primitive recursion.

Example

Here is the tree for a primitive recursive function:

Now we claim that this tree denotes the addition function \(f(m,n) = m+n\). To see this, we first note that the comp node denotes

\[ g(x,y,z) = s(pr^3_3(x,y,z)) = s(z) \]

Then the top of our tree denotes the function

\[\begin{split} \begin{array}{lclcl} f(m,n) & = & prog^1_1(n) & = & n\\ f(m,n+1) & = & g(m,n,f(m,n)) & = & f(m,n) + 1 \end{array} \end{split}\]

Then an easy induction shows that \(f(m,n) = m+n\) for all \(n\).

We presented this as if we drew the tree first and then figured out which function it denoted. In practice, of course, one goest the other way: start with a function of interest, and then craft a tree for it.

Example

The tree for multiplication is built on top of the one for addition:

But we could exhibit a single tree for multiplication that “goes all the way” and uses as leaves only the basic building blocks of primitive recursive functions:

We just replaced the red node labeled “add” with its tree.

Example

Here is the tree for exponentiation built on top of multiplication:

As always, we could take things all the way and make one big tree that shows how to build exponentiation from zero, successor, and the projections, using composition and primitive recursion.

Terms for primitive recursive functions

We want to distinguish between the trees and the functions which they denote (just as we were careful to do with programs).

Our next step is to “squash” the trees in order to make PR terms. These are syntactic objects, they are basically just a representation of the trees that we have seen. Here is a formal definition.

Definition

We define PR terms \(t\) together with their arities, and also their denotations.

z : this is the term of arity \(1\). It’s denotation \(den(t)\) is the constant function with value 0. That is \(den(z)(n) = 0\) for all \(n\).

z_empty: the denotation is the zero-place function with value 0.

s : \(den(s)\) is the one-place successor function: \(den(s)(n) = n+1\).

[proj, i, j] with i <= j: We take \(den([proj,i,j])\) to be the ith projection on j variables.

The two term constructors are

[comp, f, g_1, . . . , g_k]

[pr, f, g]

In these, comp stands for composition, and pr stands for primitive recursion.

In the composition term [comp, f, g_1, . . . , g_k], all the terms g_i must have the same arity, say \(n\). The term f must have arity \(k\) (the number of \(g\)s). The term [comp, f, g_1, . . . , g_k] has arity \(n\). The function which this term denotes is defined as follows. For numbers \(\overline{x} = x_1\), \(\ldots\), \(x_n\),

\[ \begin{array}{lcl} [comp, f, g_1, . . . , g_k](\overline{x}) & = & f(g_1(\overline{x}), \ldots, g_k(\overline{x})). \end{array} \]

For the primitive recursive terms [pr, f, g], we require that there is a number \(n\) such that the arity of \(f\) is \(n-1\) and the arity of \(g\) is \(n+1\). Then the arity of the term [pr, f, g] is \(n\). Its denotation is the function with the following properties:

\[\begin{split} \begin{array}{lcl} [pr, f, g](\overline{x},0) & = & f(\overline{x})\\ [pr, f, g](\overline{x},m+1) & = & g(\overline{x},m,[pr, f, g](\overline{x},m))\\ \end{array} \end{split}\]

add = [pr,[proj,1,1], [comp, s, [proj, 3,3]]]

mul = [pr, z, [comp, add,[proj, 3,3],[proj, 1, 3]] ]

exp = [pr, [comp, s, z], [comp, mul, [proj, 3,3],[proj, 1, 3]] ]

pred = [pr, z_empty, [proj,1,2]]

monus = [pr, [proj, 1,1], [comp, pred, [proj,3,3]]]

two_place_fn_value_one = [comp, s,[comp,z,[proj,1,2]]]  

zero_place_fn_value_one = [comp, s, z_empty]  

sgn =[pr, z_empty,two_place_fn_value_one]

sgn_bar =[pr, zero_place_fn_value_one, [comp,z,[proj,1,2]]]

chi_greater = [comp,sgn, monus] ## characteristic function of >

chi_lesser_or_equal = [comp,sgn_bar, monus] # characteristic function of (< or =)

chi_lesser = [comp,chi_greater,[proj,2,2],[proj,1,2]] ## characteristic function of <

chi_greater_or_equal = [comp, chi_lesser_or_equal,[proj,2,2],[proj,1,2]] ## characteristic function of >=

chi_equals = [comp, mul, chi_lesser_or_equal, chi_greater_or_equal ]

Converting PR terms to 1# programs

In a code cell, we can take the PR terms defined above and convert them to 1# code using the Python function program.

Please note that I am using the bb-representation of numbers.

program(add)

We also can check the programs out on examples. For this

onesharp(program(add), ['11','#1#1'])  # 3 + 10 = 13

onesharp(program(exp),['111','##1']) # this calculates 7^4 = 2401. Note that bin(2401) = 100101100001

Entering a primitive recursive term in the correct syntax, we can translate that term to a 1# program. The work here is sub-optimal in the sense that the 1# program associated to a term uses way more registers than what seems to be necessary. For example the program to determine whether or not an input number is prime uses 57 registers. On top of that, the programs that come from this implementation are very slow. My guess is that one or two applications of memoization should produce better 1# code. But I don’t really know this.

Other functions in this notebook

Here are some other functions in this notebook:

arity(t)

program(t)

in_place_program(t)

Note

The in_place_programs in this notebook do not halt according to [our earlier definition][haltDef.ipynb]. Instead, they preserve their inputs.

For example, run the program associated with add below as shown below it. (That is, take away the # from the beginning of the lines after the definition. The 2 inputs are preserved and the result goes in register 3.)

Syntax check

You can enter a line like the ones below to check that an expression really is a term, or to find an error.

The output can be long because the function syntax_check is recursive, and thus reports information about all the subterms of whatever you enter.

print(mul)
print("")

syntax_check(mul)

g = [comp, chi_equals, [proj,2,3], [comp, mul, [proj,1,3],[proj,3,3]]] 
# g tells if first x third = second
#print(arity(g))
#print(onesharp(program(g),['11','1##1','11']))

## for future use
greater_than_one = [comp, chi_greater, [proj,1,1], [comp, s, z]]
# gives output 1 if the input is >1 and gives output 0 if the input is 0 or 1

first_and_third_greater_than_one = [comp, mul,
                                      [comp, greater_than_one, [proj,1, 3]],
                                      [comp, greater_than_one, [proj,3, 3]]
                                     ]

first_third_second_proper = [comp, mul, g, first_and_third_greater_than_one]
# g tells if first x third = second, and both the first and third are >1

#onesharp(program(first_third_second_proper),['11','#11','#1'])

#onesharp(program(first_third_second_proper),['#','#','#1'])

The next box will get h_proper so that h_proper(m,p,n) = 1 if m > 1 and for some q <= n, q > 1 and m q = p. That is, I have changed h a litte so that it incorporates information about the “>1” conditions.

g3 = [comp, g, [proj, 1, 2], [comp, z, [proj, 1, 2]], [proj, 2, 2]]
p = program(g3)
onesharp(p, ['11','11111'])
k1 = [comp, add, [proj,4,4], 
      [comp, first_third_second_proper, [proj,1,4], [proj,2,4], [comp,s, [proj,3,4]]]]
k = [comp, sgn, k1] 

h_proper = [pr, g3, k1]

#onesharp(program(h_proper),['11','11','11'])
#onesharp(program(h_proper),['1#1','1111','11'])
## this asks if there is a number <= 3 such that 
## (a) the number is > 1
## and (b) if you multiply 5 by the number, you get 15.
## Since there is such a number (namely 2), we output 1.

Checking to see if the first 15 numbers are prime or not

proper_divisor = [comp, h_proper, [proj,1,2], [proj,2,2], [comp, pred, [proj,2,2]]]

pd_inverse_zero = [comp, proper_divisor, [proj,2,2],[proj,1,2]]
pd_inverse = [comp, mul, pd_inverse_zero, [comp, greater_than_one, [proj,2,2]]]

running_total_of_pd_inverse = [pr, [comp, z, [proj, 1, 1]], 
                                [comp, add, [proj, 3,3], 
                                [comp, pd_inverse, [proj, 1, 3], [proj,2, 3]]]]
#print(arity([comp, add, [proj, 2,2], pd_inverse]))                                  
#print(arity(running_total_of_pd_inverse))

is_prime =[comp,sgn_bar, [comp, running_total_of_pd_inverse, [proj, 1,1], [proj, 1,1]]]
prime_prog = program(is_prime)

# Gives output 1 if the input is a prime, and gives output # if the output is not a prime.
# It's wrong on 1.

# This takes several minutes in full, but in one minute you can see the first 10 or 11.

list = ['1', '#1', '11', '##1', 
             '1#1', '#11', '111', '###1', 
            '1##1', '#1#1', '11#1', '##11', 
             '1#11', '#111', '1111']
for i in range(15):
  x = list[i]
  b = onesharp(prime_prog,[list[i]])
  if b == '1':
    print(x + ' is prime')
  else:
    print(x + ' is not prime')  

Primitive recursive functions are …

Since the primitive recursive functions are an inductively defined class, we can prove things by induction. Here is what this means: to prove a property \(P(f)\) about all primitive recursive functions \(f\), we can

(1) Prove \(P(f)\) when \(f\) is one of the basic primitive recursive functions.

(2) Assume \(P(f)\), \(P(g_1)\), \(\ldots\), \(P(g_k)\), and then prove \(P([comp, f, g_1, \ldots, g_k])\).

(3) Assume \(P(f)\) and \(P(g)\), and then prove \(P([pr, f, g])\).

We turn to examples of proof by induction on the primitive recursive functions:

Total

Theorem 2

Every primitive recursive function is total.

So here \(P(f)\) is “\(f\) is a total function”.

It is clear that all of the basic primitive recursive functions are total, and it is also easy to see that the composition of total functions is total. So we are left with the closure of total functions under primitive recursion.

Computable by 1# programs

Theorem 3

Every primitive recursive function \(f:N^k \to N\) is 1#-computable.

In more detail:

1. For every primitive recursive \(f:N^k \to N\), there is a 1# program \(p\) such that for all \(\overline{x} \in N^k\),

\[ f(\overline{x}) = y \quad \mbox{ iff }\quad \langle\!\langle p \rangle\!\rangle(bb(x_1), \ldots, bb(x_n)) = bb(y) \]

2. For every primitive recursive \(f:N^k \to N\), there is a 1# program \(q\) such that for all \(\overline{x} \in N^k\),

\[ f(\overline{x}) = y \quad \mbox{ iff }\quad [\![ q ]\!](bb(x_1), \ldots, bb(x_n)) = bb(y) \]

Part 1 refers to programs which preserve their inputs. We prove this part by induction on the primitive recursive function \(f\). Then we infer 2 from it by “cleaning up”. Doing things this way is like strengthening an induction hypothesis, a widely-used trick in mathematics.

Majorized by the Ackermann function

Our last proof by induction on the PR functions pertains to the Ackermann function \(A(x,y)\) defined as follows:

\[\begin{split} A(x,y)\quadeq \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ A(x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ A(x-1,A(x,y-1)) & \mbox{otherwise} \end{array} \right. \end{split}\]

Lemma 1

For every primitive recursive function \(f:N^k \to N\) there is a number \(r\) such that for all \(x_1, \ldots, x_k\),

\[ f(x_1, \ldots, x_k) < A(r, \max_i x_i) \]

This lemma is proved by induction on the PR functions.

For the base cases of \(z\) and the projections, we can take \(r=0\). For the successor function, we can take \(r = 1\).

Consider a composition, say [comp, f, g_1, . . . , g_k]. By induction hypothesis, we have numbers \(r_i\) for \(g_i\) (for \(1\leq i \leq k\)), and we also have a number \(s\) for \(f\).

I won’t give this here, but you can find a short note that does the details on our Canvas page. Assuming this lemma, we can then easily infer what we really want:

Theorem 4

The Ackermann function \(A(x,y): N^2\to N\) is not primitive recursive.

Proof. Assume toward a contradiction that \(A(x,y)\) were primitive recursive. By the lemma, we have a number \(r\) so that

\[ A(x,y) < A(r, \max(x,y)) \]

for all \(x\) and \(y\). In particular, taking \(x = r = y\), we have \(A(r,r) < A(r,r)\).

Contradiction!