CSC 341: February 28, 2007

From CSWiki

1 Instructor's notes for the class session
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

Primitive recursive sets

A set of natural numbers is primitive recursive if, and only if, there is a singulary, primitive recursive predicate that yields 1 when applied to any member of the set and 0 when applied to any non-member. The predicate is called the characteristic function of the set.

A set of strings is primitive recursive if, and only if, the set of its encodings (as natural numbers) is primitive recursive.

All finite sets of natural numbers are primitive recursive.

The primitive recursive sets are closed under union, intersection, and complementation.

(A slightly harder theorem:) The primitive recursive sets of strings are closed under concatenation.

The primitive recursive sets of strings are closed under star.

All regular languages are primitive recursive.

All context-free languages are primitive recursive.

Not all primitive recursive sets of strings are context-free languages; for instance, $\{\texttt{a}^n \texttt{b}^n \texttt{c}^n \mid n \ge 0\}$ is primitive recursive but not context-free.

(Note: None of this material on primitive recursive sets is in the handout or in our textbook, so writing up proofs of the results announced above would be a particularly valuable contribution to the wiki.)

[edit]

Proofs for Primitive Recursive Set Theorems

A set of strings is primitive recursive if, and only if, the set of its encodings (as natural numbers) is primitive recursive.

If a set of string encodings is primitive recursive, then it is easy to find a characteristic function to describe the strings that are being encoded as a primitive recursive set. If the characteristic function for the set of string encodings is $C e$ , then define function $f$ that finds an encoding of a string. The new characteristic function for the set of strings can be defined as $C s = C e (f (x))$ .

All finite sets of natural numbers are primitive recursive.

A characteristic function to describe a finite primitive recursive set could be defined to compare each input to a set of numbers known to be members of the set. The function would be similar to "If input x is equal to a, b, or c, return 1. Otherwise, 0."

[edit]

Course-of-values recursion

The goal of course-of-values recursion is to obtain a simple way to define primitive recursive functions that are most naturally defined in terms of "non-consecutive" recursion -- the recursive definition uses applications of the function being defined to arguments that are smaller, and hence closer to the base case, than the current argument, but differ from the current argument by more than 1. List recursion provides lots of examples: Typically, in a function defined by list recursion, computing the value of the function for a non-empty list ls requires the value of the function for the cdr of ls (rather than for whatever list happens to be encoded by the predecessor of the encoding for ls).

There are also cases in which the most natural way to compute the value of a function requires the values of the function for all smaller arguments. A typical example is the Catalan sequence $1, 1, 2, 5, 14, 42, \ldots$ , in which the term $\texttt{Catalan}(n)$ at (zero-based) position $n$ is defined by

$\texttt{Catalan}(0) = 1,$

$\texttt{Catalan}(t + 1) = \sum_{i = 0}^t \texttt{Catalan}(i) \cdot \texttt{Catalan}(t - i).$

Incidentally, this function has some importance for computer scientists: $\texttt{Catalan}(n)$ is

the number of different shapes for a binary tree with $n$ leaves,
the number of different ways of parenthesizing an algebraic expression containing $n$ binary operators,
the number of different orders in which you can do $n$ stack pushes and $n$ stack pops without ever trying to pop an empty stack

and also has many other combinatorial interpretations.

Course-of-values recursion begins with a function $g$ that expresses the way in which each value of the desired function $f$ depends on its arguments and on the list of its previous values (arranged with the "most recent" value at the beginning of the list). Thus the valence of $g$ will be one greater than the valence of the desired function $f$ .

Using $g$ , our plain vanilla kind of recursion can be used to define $\ddot{f}$ , a function that always returns the code for a pair, with the car of the pair being the value of $f$ for the given arguments, and the cdr being the encoding for a list of values of $f$ for all values of the last argument less than the given one. The base case of this recursion works because we can just give $g$ the encoding for the empty listas its final argument, and cons the result with the encoding for the empty list to get the pair that $\ddot{f}$ should return. For the induction step, since we have access to the previous result of $\ddot{f}$ , we can both use the entire pair as the cdr of the current result, and also use it as the last argument to $g$ when we compute the car of the current result.

Applications of course-of-values recursion: decrement-last, last, all-but-last, folding, mapping.

[edit]

Study questions

1. Give an informal argument to show that, for any primitive recursive set $S$ of strings, the set $\{w^\mathcal{R} \mid w \in S\}$ of reversals of members of $S$ is primitive recursive.

  It has already been shown that the functions string-length, string-ref, concatenate are primitive recursive.  Using these functions and course-of-value recursion, 
  a primitive-recursive string-reverse function can be defined.  The base case takes a string of length one and returns   that string.  The recursion case 
  takes the last value of the string string-ref  $s$  (predecessor (string-length))) and concatenates to it the values-so-far of string-reverse.  
  By composing this function with any primitive recursive string, the reverse of that string is also primitive recursive, and so the objective is accomplished.

2. Prove that the set $\{2, 3, 5, 7, 11, \ldots\}$ of prime numbers is primitive recursive.