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

Recursion Theory and Computability

Another name for Computability is Recursion Theory. For example, partially computable functions are called recursively enumerable (RE).

The term “recursively enumerable” arises from a chain of observations. Since every program, when compiled, becomes a finite string of characters - which are really just digits in some base arithmetic - that string can be read as a single natural number. Furthermore, no two distinct programs produce the same compiled string, so the correspondence is unique. By reverse engineering this, counting through all natural numbers is the same as enumerating all possible compiled codes that can run on a Turing machine. Since counting (i.e., this enumeration process) turns out to be trivially recursive - as will be discussed today - these codes, and by extension the partially computable functions they represent, were called recursively enumerable. The proper subset of these codes that always halt are the totally computable ones; their corresponding label in this terminology is simply recursive (mirroring how computer theory drops “totally” and just says “computable”).

The following explains why partially computable functions can be said to “connect” from one set of values (elements) to another where not every element of the second set has to connect to an element of the second set. Computer theory has a different angle on what is partial. From Turing’s perspective, a function does not map data values per se, but rather the underlying memory configurations. To Turing, the issue isn’t whether the user defined an aspect of the mapping or not (defined/undefined when the user is “happy” with the result), but rather whether the underlying configuration and its function is correct. If it is defined (independent of whether the user is happy), then the computer running the program is an effective computation. If it doesn’t halt, an infinite loop occurs and the computation does not yield a final configuration (output) value.

To reflect on these latter two situations, computer theory borrows the notion of partial/total. If a program can “compile” and is run on the Turing machine, then the code/function/program is called partially computable because we do not know yet whether or not the code will actually halt when given the initial tape (memory) configuration. This lack of knowledge is an outcome of the unsolvability of the halting problem, which states that no algorithm can determine whether or not an arbitrary piece of code will terminate given any initial tape/memory configuration. If in fact the program will always halt on any initial tape configuration (input), then the code/function/program is totally computable. This (hopeful) situation is considered the default, so computer theory just calls these codes “computable” (without explicit mention that they are total).

Note on Compiled Numbers and Code

This reverse engineering process demonstrates that each compiled number represents a different CODE - but this is not referring to what the code actually does, but rather to the programming language commands and the codes’ variable names that comprise the original code (which compiled into this number). Davis/Turing understood that more than one compiled number will represent the same underlying mathematical function, but what the code does is not Turing’s concern - only how he represents the code and more specifically how the code and the input/output values are stored in memory. That is why Turing is not concerned about the mathematical notion of a partial function, but rather whether the computer will do in that situation and its input is confined to that situation. Turing’s computer will always halt when running the code for that mathematical partial function. GIGO (Garbage In, Garbage Out) applies: if the computer does not act the way the user would like when given a partial function, do not blame the computer.

The question that computer theorists then concentrate on is how many features must this “recursion” process have. A first approach in the theory was to identify those basis/initial functions and corresponding mathematical techniques that can provide the ability to “recursively enumerate,” with the success of that approach guaranteeing that such a system of mathematics can generate computable functions. This more simplistic approach was called Primitive Recursive, but unfortunately Martin Davis and others before him showed that in fact Primitive Recursive functions are a proper subset of the computable functions. (A different lecture will discuss what is missing from this approach.)

In essence, the computer theorists were trying to construct a RISC (Reduced Instruction Set Computer) “chip” and had hoped that the “initial functions” (the built-in commands below), with the supplied techniques of composition and recursion, would be sufficient to “program” (generate) code of any computable function.

Primitive Recursive Functions

Initial Functions

Function	Name	Notes
$N(X) = 0$	Null	A constant function - the simplest possible function. Output is always 0 (no other constant value).
$S(X) = X + 1$	Successor	The simplest addition, which only adds 1 to the original value.
$U(X_1, \ldots, X_n) = X_i$	Projection	When given a multivariate function, returns one of its inputs $X_i$. Why is $U$ used? Some suggest it stands for Unpacking.

The Purpose of the Projection Function $U$

Computer theorists had a philosophical issue: given a mathematical function $f(X_1, \ldots, X_n)$, what gives us the authority to access the underlying $X_i$ values? To grant this privilege, computer theorists included the projection ($U$) function amongst the primitive initial functions.

$U()$ will be included in some of the first examples below, but because it tends to confuse reading the formulas in later examples, we will eventually omit it. This omission is for notational purposes only - technically $U()$ should appear throughout the formulas. This is analogous to other conventions in mathematics where notation is dropped once it is understood to be implicitly present: multiplication in algebra is written $XY$ rather than $X \cdot Y$; concatenation in formal languages drops the explicit dot operator; and regular expressions originally derived from set theory dropped the curly braces around sets. In each case, the operation is still there - it just gets noisy to write.

Essential Techniques

The two essential techniques for building primitive recursive functions are:

• Composition
• Recursion

Composition

$$h(x) = f(g(x))$$

Composition simply creates a pipeline of functions, where the output of one becomes the input of the next.

For example, to generate a constant $k$ (not explicitly provided by the initial functions - cf. the Null function above), use $k$ nested applications of $S$ over $N(X)$:

$$\underbrace{S(S(S(\cdots(N(X))\cdots)))}_{k \text{ applications of } S} = S^{(k)}(N(X))$$

Note: the notation $S^{(k)}(N(X))$ denotes composition of $S$ with itself $k$ times, which is different from $F(X^2)$ (algebra). This notation differentiates $F^2(x)$ (function composition) vs. $F(X^2)$ (algebraic squaring).

Recursion

Basic Form (Single User-Supplied Input)

Variable $Y$ keeps track of the recursion level; variable $X$ is simply a user-supplied input value.

$$\text{REC}(0, X) = h(X) \tag{Base Case}$$ $$\text{REC}(Y+1, X) = g(Y,\ \text{REC}(Y, X),\ X) \tag{Recursive Step}$$

• Base Case: Level 0 ($Y = 0$) is a regular (non-recursive) command. $h(X)$ is already known to be a primitive recursive function.
• Recursive Step: Defines the behavior of the function at level $Y+1$ in terms of the result at level $Y$. $g()$ is also already known to be a primitive recursive function.

To emphasize the point that $Y$ always changes, $\text{REC}$ usually changes, and $X_i$ never changes, Davis lists these in this order inside the parameter list of $\text{REC}$.

Three categories of information available to the recursive function at every step:

Category	Variable	Behavior
User-supplied auxiliary variable (input)	$X$	Never Changes throughout the process. (While general recursion allows $X$ to change at each level, primitive recursive does not.)
Level number	$Y$	Has to Change - initially $Y=0$, increases by 1 each step ($Y+1$)
Previous level’s output	$\text{REC}(Y, X)$	Typically Changes but is not a requirement

General Form (Many User-Supplied Inputs)

Variable $Y$ keeps track of the recursion level; variables $X_1, \ldots, X_n$ are user-supplied input values.

$$\text{REC}(0, X_1, \ldots, X_n) = h(X_1, \ldots, X_n) \tag{Base Case}$$ $$\text{REC}(Y+1, X_1, \ldots, X_n) = g(Y,\ \text{REC}(Y, X_1, \ldots, X_n),\ X_1, \ldots, X_n) \tag{Recursive Step}$$

• Base Case: Level 0 ($Y = 0$) is a regular (non-recursive) command. $h(X_1, \ldots, X_n)$ is already known to be a primitive recursive function.
• Recursive Step: Defines the behavior of the function at level $Y+1$ in terms of the result at level $Y$. $g()$ is also already known to be a primitive recursive function.

To emphasize the point that $Y$ always changes, $\text{REC}$ usually changes, and $X_i$ never changes, Davis lists these in this order inside the parameter list of $\text{REC}$.

Three categories of information available to the recursive function at every step:

Category	Variable	Behavior
User-supplied auxiliary variables (inputs)	$X_1, \ldots, X_n$	Never Change throughout the process
Level number	$Y$	Has to Change - initially $Y=0$, increases by 1 each step ($Y+1$)
Previous level’s output	$\text{REC}(Y, X_1, \ldots, X_n)$	Typically Changes but is not a requirement

Roles of $h$ and $g$

To summarize the structure: $h(X)$ (or $h(X_1, \ldots, X_n)$) provides the initial value at the base case (level 0). $g$ then takes all pieces of information available at each subsequent step - the current level number $Y$, the previous level’s output $\text{REC}(Y, X)$, and the user-supplied input $X$ - and produces the next level’s output. Together, $h$ and $g$ fully describe the behavior of the recursive function at every level.

Important Notes on These Definitions of Recursion

1. The user-supplied input is not really a requirement. We know that in programming one can initialize variables to values inside the code without reading in an input.
2. $X_i$ never changing is a requirement of this definition of primitive recursion, but in general, any variable can change throughout the execution of the code, even the variable that stores a read-in input value.