CSC 341: March 2, 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

Partial functions

The concept of a partial function generalizes the concept of a function. Given an element of its domain, a partial function yields at most one value for that argument, but may yield none. A partial function is said to be undefined at any member of its domain for which it yields no value.

In the universe of partial functions, what we have heretofore been calling functions are called total functions, and are simply the special case in which the partial function happens to be defined at every member of its domain. Under our definitions, all primitive recursive functions are total.

Partial functions can be used to model attempts at computation that never terminate, as in some of the nondeterministic automata that we have seen or in context-free grammars with rule sets like $\{S \rightarrow S\}$ .

The operations of generalized composition and generalized recursion, and all the operations that are defined in terms of those, can be extended to partial functions, with the convention that, when any of the component functions does not yield any value for the arguments it is given, the function defined by composition or recursion does not yield a value either. The effect is that undefinedness propagates through any attempt to compute a value, confirming the appropriateness of this idea as a model of a nonterminating attempt at computation.

[edit]

Unbounded minimization

To extend the concept of a primitive recursive function into the universe of partial functions, we need a new basic mechanism for defining functions, one that can sometimes yield non-total functions as results. The simplest such operation is the unbounded loop, implemented here specifically as unbounded minimization: a search, not constrained by any upper bound, for a value that satisfies a given predicate. If no natural number satisfies the predicate, then the search never terminates, and the function defined by unbounded minimization does not yield a value. Like composition and recursion, this idea can be generalized to allow any number of fixed arguments in addition to the argument that counts off the values tested in the search.

Examples: the definition of minus; the definition of mist.

A partial recursive function is a function that can be constructed from our primitives (zero, successor, and the projection functions) by generalized composition, generalized recursion, and generalized unbounded minimization. Clearly, all primitive recursive functions are partial recursive, as are minus and mist.

[edit]

Encoding partial recursive functions

It is not possible to encode functions, in the sense of assigning a different natural number to each one; there are just too many functions.

Examples of the diagonalization pattern:

There are more languages (on any one alphabet) than natural numbers.
There are more real numbers than natural numbers.
Any set has more subsets than elements.

The diagonalization proof that there are more total singulary functions than natural numbers.

However, partial recursive functions can be encoded, by associating numbers with the primitive functions and constructing numerical analogues of composition, recursion, and unbounded minimization. The mechanics are tedious, and the most straightforward way of designing the encoding leaves some natural numbers unassigned. Reassuringly, however, the mechanics of the encoding can all be expressed in primitive recursive functions. Section 11 basically shows how to build procedures as a structured data type in the notation we've developed for recursive function theory, with appropriate constructors, selectors, and type-testing predicates.

[edit]

Study questions

Suppose that we want to define a function improved-quotient, of valence 2, that is undefined when its second input is zero and outputs the same value as quotient otherwise. It would seem natural to write $\texttt{improved-quotient\ } \equiv \texttt{\ [?}_2 \texttt{\ [o}^1_2 \texttt{\ zero?\ pr}^1_2\texttt{]\ mist}_2 \texttt{\ quotient]}$ to achieve this. Why is this definition incorrect? What function does the right-hand side actually describe?
Given a partial recursive function $f$ of valence $n + 1$ , describe the conditions under which $\texttt{[oo}_n\ f\texttt{]}$ is undefined.
In encoding partial recursive functions, why don't we need to reserve separate encodings for functions defined using conditionals, bounded quantification, bounded summation, iteration, and so on?
The singulary function structural-complexity takes the encoding $e$ for a partial recursive function as argument and returns a natural number reflecting the structural complexity of the procedure that defines that function: 1 for any primitive, 1 plus the sum of the structural complexities of the components for any function defined by composition, 1 plus the sum of the structural complexities of the base and induction-step functions for any function defined by recursion, and 1 plus the structural complexity of the predicate to be satisfied for any function defined by unbounded minimization. Prove that structural-complexity is primitive recursive.

[edit]

Proposed Solutions

Going back to the definition of mist, mist $\equiv [ u_{0}$ zero $]$ . And if we look into the definition of bounded minimization $\overline{u_{p}}$ , we see that it applies zero to each input. The function is undefined everywhere in its domain. Here mist doesn't fit our purpose.
These functions don't need special encodings because bounded quantification, conditionals, and so on are just shorter ways of saying things that can be expressed using the notation that is already included in the encoding system.