Lecture 14: Primitive Recursive Functions and Recursion Theory - CSCI 381 Goldberg

Administrative Updates

Homework: There is homework involved with this lecture (particularly regarding Question 3 and Question 4 on recursive function complexity), but the instructor is not collecting it for grading. However, students should think through these problems carefully and are welcome to send explanations via email.

Reading Assignment: Students should read items 14, 15, and 16 (Boolean predicates: less than or equal, greater than, less than, greater than, equal) on their own. These will be covered in detail on Wednesday.

Primitive Recursive Functions (Basic)

Overview

Today we will embark on the notion of “recursion” as it is used in computer theory, specifically to design primitive recursive functions. This approach at first glance will seem different than programming recursion as seen in the following simple recursive code for factorial:

int fact(int num) {
    if (num < 0) return -1; //flag to indicate an input value where not defined
    if (num == 0) return 1; //base case

    //recursive step; Note: the level to be determined is num in terms of level num-1
    return num * fact(num - 1);
}

The above code is a top-down approach but recursion in computer theory is a bottom-up approach as we will now explore. (Is there a difference? We will discuss in a different lecture.)

Remember that primitive recursive was an early attempt to model all computable functions using a RISC chip (Reduced Instruction Set Computer). Since computers did not yet exist, early computer theorists were asking: what is the minimum set of built-in functions and operators needed to compute all possible Turing-equivalent computations? The original hope was that the computer they wanted to build would only require a few initial functions and techniques (the ones listed above) and the two operators (composition and recursion) to achieve all possible computable functions. By keeping the instruction set minimal, they could design a simpler computer that would still be capable of universal computation.

Initial Functions

Function	Description	PRIM
$N(x)$	always returns 0	//PRIM#1
$S(x)$	returns $x + 1$	//PRIM#2
$U_{i,n}$	return the $i$th element from a list of $n$ numbers (and does not change any values)	//PRIM#3

The $U$ function deserves special attention. It solves a technical but important problem: how do you access values that are embedded in the parameter list of a function you’re calling? The $U_{i,n}$ function takes $n$ parameters and extracts the $i$th element, similar to indexing into a one-dimensional array. While it may seem simple, it is essential for granting access to the inside of parameter lists, which is necessary for building more complex primitive recursive functions.

Techniques Provided

Composition

Composition of functions means that the output of one function becomes the input of the next function. Think of it as a daisy chain or a pipelining of functions: each function takes an input and provides an output, which then becomes the input to the next function in the list. This process continues through the entire chain.

Recursion (as described next)

This type of recursion has three categories of information at its disposal (disposal means can be thrown away; this term is accurate here to emphasize that one is not required to use all the information provided):

	Single Variable	Multivariable
INFO#1	Static Input $x$	$x_1, \ldots, x_n$
INFO#2	Previous Level Number $y$	$y$
INFO#3	Previous Level’s Output $\text{REC}(x, y)$	$\text{REC}(x_1, \ldots, x_n, y)$

The next level $(y+1)$ computes the next value using a function $g$ that has all three categories available: $g(y), [\text{REC}(x_1, \ldots, x_n, y)], [x_1, \ldots, x_n]$. The key insight is that the function $g$ has no obligation to use all three pieces of information—it can use whichever subset is necessary. This flexibility is crucial for building diverse recursive functions, and the emphasis on “disposal” reminds us that unused information can simply be discarded.

Limitations and Extensions

Davis (and others) show that in fact this approach is NOT sufficient to mathematically model ALL possible computable functions. So, perhaps if we had one more Initial Function and/or one more Basic Technique (Operator) and add it to the definition to Primitive Recursive, the augmented system will then describe all computable functions. In a future class, we will present Davis who shows that the Initial Functions are in fact sufficient, but we are missing another operator. In anticipation of that discussion, Davis introduces a Primitive Recursive Class (PRC) that includes all functions that can be formulated by the initial functions utilizing composition and recursion, BUT can also use extra initial functions and/or extra operators. We will be leading up to the primitive recursive function that Davis realizes is too constrained for all computable functions.

Examples

Addition

$\text{ADD}(x, y)$ //ADD is recursive Successor (S) //PRIM#4

• Base case: $\text{ADD}(x, 0) = U_{1,2}(x, 0)$ (which equals $x$)
• Recursive case: $\text{ADD}(x, y+1) = S(\text{ADD}(x, y))$ (which equals $(x+y) + 1 = x + (y+1)$)

Level	$x$ // input	$y$ // input	$\text{ADD}(x, y)$ // previous level	$S(\text{ADD}(x, y))$ // future level	$\text{ADD}(x, y+1)$ // output
0	$x$	0	-	-	$x$
1	$x$	1	$x$	$(x)+1$	$x+1$
2	$x$	2	$x+1$	$(x+1)+1$	$x+2$
3	$x$	3	$x+2$	$(x+2)+1$	$x+3$
4	$x$	4	$x+3$	$(x+3)+1$	$x+4$
5	$x$	5	$x+4$	$(x+4)+1$	$x+5$

Multiplication

$\text{MULT}(x, y)$ //MULT is recursive Addition (ADD) //PRIM#5

• Base case: $\text{MULT}(x, 0) = N(x)$ (which equals $0$)
• Recursive case: $\text{MULT}(x, y+1) = \text{ADD}(\text{MULT}(x, y), x)$ (which equals $x \cdot y + x = x \cdot (y+1)$)

Level	$x$ // input	$y$ // input	$\text{MULT}(x, y)$ // previous level	$\text{ADD}(\text{MULT}(x, y), x)$ // future level	$\text{MULT}(x, y+1)$ // output
0	$x$	0	-	-	0
1	$x$	1	0	$(0)+x$	$x$
2	$x$	2	$x$	$(x)+x$	$2x$
3	$x$	3	$2x$	$(2x)+x$	$3x$
4	$x$	4	$3x$	$(3x)+x$	$4x$
5	$x$	5	$4x$	$(4x)+x$	$5x$

Exponentiation

$\text{POWER}(x, y)$ //PRIM#6

• Base case: $\text{POWER}(x, 0) = S(N(x))$ (which equals $1$)
• Recursive case: $\text{POWER}(x, y+1) = \text{MULT}(\text{POWER}(x, y), x)$ (which equals $x^y \cdot x = x^{(y+1)}$)

Level	$x$ // input	$y$ // input	$\text{POWER}(x, y)$ // previous level	$\text{MULT}(\text{POWER}(x, y), x)$ // future level	$\text{POWER}(x, y+1)$ // output
0	$x$	0	-	-	1
1	$x$	1	1	$(1) \cdot x$	$x$
2	$x$	2	$x$	$(x) \cdot x$	$x^2$
3	$x$	3	$x^2$	$(x^2) \cdot x$	$x^3$
4	$x$	4	$x^3$	$(x^3) \cdot x$	$x^4$
5	$x$	5	$x^4$	$(x^4) \cdot x$	$x^5$

Note: It is because of this base case that Davis defined $0^0 = 1$, eventhough mathematics states that $0^0$ is indeterminate and cannot be defined. Davis had to do this since ALL primitive recursive functions must be total since they were an attempt to model all computable functions which are total. Remember that Turing maps a memory configuration (called the “input”) to another memory configuration (called the “output”). As an input, the value 0 has a valid memory configuration (a string of 0s).

Factorial

$\text{FACT}(x, y)$ //PRIM#7

• Base case: $\text{FACT}(0) = S(N(x))$ (which equals $1$)
• Recursive case: $\text{FACT}(y+1) = \text{MULT}(\text{FACT}(y), S(y))$ (which equals $y! \cdot (y+1) = (y+1)!$)

Level	$y$ // input	$\text{FACT}(y)$ // previous level	$\text{MULT}(\text{FACT}(y), S(y))$ // future level	$\text{FACT}(y+1)$ // output
0	0	-	-	1
1	1	1	$(1) \cdot (0+1)$	1
2	2	1	$(1) \cdot (1+1)$	2
3	3	2	$(2) \cdot (2+1)$	6
4	4	6	$(6) \cdot (3+1)$	24
5	5	24	$(24) \cdot (4+1)$	120

Questions to Ponder

(Q#1) We start with $0$ ($N(x)$) and we add one ($S(x)$); all functions seem to be increasing. Where is Predecessor, which subtracts one and is the basis for subtraction?

Answer (Davis): The predecessor function is actually embedded within the recursion schema itself. When we compute the next level $y+1$, we have access to the previous level number $y$, which is precisely the predecessor (minus one) of $y+1$. This may seem like a sharp or abstract answer, but it reveals an important insight: the $U$ function extracts $y$ from the available information, effectively giving us the predecessor of the current level. Therefore, the machinery to compute $\text{PRED}$ and achieve subtraction is already present in the basic recursive structure.

(Q#2) We have Multiplication. Where is the Division operator? (To whatever extent that integer division can provide.)

(Q#3) If one recalls how we program factorial in actual code, the main recursive call is $n*\text{fact}(n-1)$ which is a top-down computation, but ALL primitive recursive functions are bottom-up, starting at base case 0 and then computing the next level $(y+1)$. Are these the same process?

Answer: This will be discussed in a different lecture.

(Q#4) We will show that each recursive function (similar to any of the above) can be implemented by a single for-loop. Specifically:

• Addition is Recursive Successor (built-in $S$ function applied repeatedly)
• Multiplication is Recursive Addition
• Exponentiation (Power) is Recursive Multiplication

This creates a triple-nested for-loop structure using only built-in commands like $n(x) = 0$ and $s(x) = x+1$. We know from algorithm analysis that built-in commands have constant time complexity $O(1)$ (as opposed to library calls/APIs).

At first glance, the answer seems straightforward:

• Addition would appear to be $O(n)$ (one for-loop calling the constant-time successor function)
• Multiplication would appear to be $O(n^2)$ (nested for-loops: outer loop runs $n$ times, inner loop is addition which is $O(n)$)
• Power would appear to be $O(n^3)$ (Power is recursive multiplication)

However, what is the true time complexity of this code? Is it actually $O(n^3)$? (Hint: This is a much harder problem than it seems to be.) The straightforward analysis may not capture the actual computational behavior due to the specific way these functions are composed recursively.

(Q#5) What happened to negative numbers?

Answer: Turing’s conceptualization of functions is fundamentally different from the algebraic perspective. In Turing’s view, functions are not about arithmetic values per se, but about mapping one memory configuration to another. A memory configuration is a finite string of symbols (in the binary case, a string of 0s and 1s). The value 0 is the smallest possible memory configuration (represented as all 0s), and there is no negative configuration—all memory configurations are naturally interpreted as non-negative integers. Therefore, negative numbers play no role in the theory since every valid input (a finite string of memory) can be represented by a natural number.

Primitive Recursive Functions (Advanced)

Overview

We now continue our development of Primitive Recursive functions. At the end of our discussion on primitive recursive, we will get the impression on just how expressive/powerful primitive recursive functions are.

Additional Primitive Recursive Functions

Predecessor

$\text{PRED}(y)$

• Base case: $\text{PRED}(0) = N(\text{``X''})$ (which equals $0$)
• Recursive case: $\text{PRED}(y+1) = y$ using $g(y, \text{PRED}(y)) = U_{1,2}(y, \text{PRED}(y))$

Note: PRED is built-in “cutoff” of 0 for outputs. //PRIM#8

Key Insight: A sharp observation from Davis is that the predecessor function is actually embedded within recursion itself. Recall that when computing the next level $y+1$ using the recursive schema, we have access to three categories of information: the static input, the current level number $y$, and the previous level’s output. When computing at level $y+1$, the previous level number is $y$, which is precisely the predecessor of $y+1$. Therefore, the subtraction operator (minus one) is inherently available through the recursive structure, even though it is not explicitly listed as a basic technique.

Cutoff Subtraction

$$\text{SUB}(x, y) \text{ written as } x \ominus y \text{ (the ``o'' denotes zero --- the result floors at 0)}$$

• Base case: $\text{SUB}(x, 0) = x$
• Recursive case: $\text{SUB}(x, y+1) = \text{PRED}(\text{SUB}(x, y))$

We must use cutoff subtraction rather than ordinary subtraction because in the context of Turing machines and memory configurations, all values are non-negative integers. There is no representation for negative numbers—all memory configurations are interpreted as natural numbers. Therefore, when $y > x$, the subtraction would result in a negative value, which is impossible. The notation $x \ominus y$ indicates that if the result would be negative, we instead return 0. This “cutoff” at zero ensures the function remains total and always produces a valid memory configuration.

Note: Built-in “cutoff” of 0 for outputs. //PRIM#9

Absolute Difference

$|x - y|$

$$\text{ADIFF}(x, y) = \text{SUB}(x, y) + \text{SUB}(y, x)$$

• //PRIM#10
• Composition alone
• $\text{SUB}(y, x)$ is technically $\text{SUB}(U_{2,2}(x, y),\ U_{1,2}(x, y))$ using projection functions

Boolean Predicates

The next set of nine primitive recursive functions are all Boolean Predicates.

Boolean Predicates $P(x)$ or $P(x_1, \ldots, x_n)$ have some requirements:

1. Output is 0/1 where 0 represents FALSE and 1 represents TRUE
2. Boolean Predicate is a Total mapping/function. (Hardware people debate this and allow a partial function.)
3. The inputs are 0/1. Karp requires this but Davis does not.

Not Equal to Zero

$\alpha(x)$ //Boolean returning 0 or 1

$\alpha(x) = 1 \ominus x$ //akin to NOT in C-based programming where TRUE is >= 1 //Composition alone

Behavior: The $\alpha$ function outputs 1 if and only if $x = 0$, and outputs 0 for all $x \geq 1$. Here’s why: when $x = 0$, we compute $1 \ominus 0 = 1$. When $x = 1$, we compute $1 \ominus 1 = 0$. When $x > 1$, the cutoff subtraction gives $1 \ominus x = 0$ (since we cannot go below zero).

//PRIM#11

Equality

$x = y$

$\text{EQ}(x, y) = \alpha(|x - y|)$ //Boolean returning 0 or 1 //Composition alone

Behavior: The $\text{EQ}$ function returns 1 if and only if $x = y$, and returns 0 otherwise. Here’s the reasoning: when $x = y$, the absolute difference $|x - y| = 0$, so $\alpha(0) = 1$. When $x \neq y$, the absolute difference $|x - y|$ is some positive value, so $\alpha(\text{positive value}) = 0$.

//PRIM#12

Next Steps

The next lecture will continue with the rest of the boolean predicates.