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

Encoding partial recursive functions

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.

The encoding for zero is 0.
The encoding for successor is 1.
The encoding for a projection function $\texttt{pr}^m_n$ is $4 k + 2$ , where $k$ is the encoding for the pair $(m, n)$ .
The encoding for a composition $\texttt{[o}^m_n \ f\ g_0\ \ldots\ g_{m - 1}\texttt{]}$ is $4 k + 3$ , where $k$ is the encoding for the list $(m, n, \bar{f}, \overline{g_0}, \ldots, \overline{g_{m - 1}})$ .
The encoding for a recursion $\texttt{[v}_n\ f\ g\texttt{]}$ is $4 k + 4$ , where $k$ is the encoding for the list $(n, \bar{f}, \bar{g})$ .
The encoding for an unbounded minimization $\texttt{[}\mu_n\ p\texttt{]}$ is $4 k + 5$ , where $k$ is the encoding for the pair $(n, \bar{p})$ .

The type-testing predicates for zero, successor, and the projection functions are straightforward, but the testing for the validity of the operations that build up from these primitives is intricate enough that it has to be done in three stages. The first stage checks to make sure that the encoding belongs to the correct residue class. The second confirms that the valences of all the component functions match up correctly with one another and with the valence of the result. The third confirms that the components are themselves valid function encodings.

[edit]

Encoding computations

When we are given a construction procedure for a partial recursive function, and an appropriate number of arguments for that function, we can trace the steps by which the value that the function yields (if there is one) can be computed, by supplying the arguments to the primitives at the base of the construction procedure and tracing the ensuing data flow through the various composition, recursion, and unbounded minimization steps. It would be possible to keep a log of these steps, which would record and represent the computation.

The log doesn't have to be a text file; instead, it could be a hierarchically linked data structure in which each node has, say, four fields: one for the function being applied (encoded as in section 11), one for the list of inputs to the function, one for a list of the node's children (any subcomputations that are needed as pieces of the current computation), and one for the output or result of the computation -- the value that the function produces for the given inputs.

In the case of a partial function that is undefined for certain inputs, an attempt at a computation can be made, and one can imagine a data structure that would represent such attempts; but such a data structure would not have an output field and would not count as a computation.

When the function is a primitive, the list of subcomputations will be empty.
When it is defined as a composition, the list of subcomputations will have one element for each of the component functions.
When it is defined as a recursion, the list of subcomputations will have either one or two elements -- one in the base case, where the base function is applied, and two in the induction case, where the function itself must be applied recursively, and then the step function is applied to the result.
When the main function is an unbounded minimization, the length of the list of subcomputations is one greater than the number in the output field of the computation: The predicate must be applied repeatedly until a number that satisfies it is found, and each of those applications is a separate subcomputation.

Section 12 defines the data structure for computations, providing selectors and type predicates -- most importantly, a type predicate computation? that includes checks of the validity of the subcomputations as well, so that we can determine quite exactly whether a given natural number correctly encodes a possible computation, with an exactly specified function (encoded), inputs, and output.

[edit]

The universality theorem

The possibility of doing reflection inside the model -- of having partial recursive functions that describe, in a formal way, the behavior of partial recursive functions, has many surprising consequences. The first and most fundamental of these is the universality theorem, which a programmer might summarize by saying that it is possible to write an interpreter as a partial recursive function. Specifically: There is a partial recursive function apply takes as its inputs the encoding for a partial function $f$ and the encoding for a list $(x_0, \ldots, x_{n - 1})$ of inputs to $f$ and yields $f(x_0, \ldots, x_{n - 1})$ as its output (but is undefined if $f(x_0, \ldots, x_{n - 1})\uparrow$ ). In other words, apply is a universal function, in the sense that it can imitate any other function, given that function's encoding as an input datum.

One of the surprises is that, once we have computation?, the coding for apply is almost trivial, if we don't mind using brute force: We simply do an unbounded-minimization search through the natural numbers, looking for the encoding for a computation with the correct program and input fields. When and if we find one (and there will be at most one), we extract its output field. That's it!

This is, of course, a ludicrously inefficient way to write an interpreter, particularly since the encodings for computations are unbelievably gigantic numbers. The theorem is about what the model can do in principle, so implementation issues are not relevant.

[edit]

Study questions

There is one and only one natural number $z$ such that $\texttt{computation?}(z) = 1$ and $\texttt{program}(z) = 0$ . Find $z$ .
Is it possible for there to be two natural numbers $m$ and $n$ , such that (a) $\texttt{computation?}(m) = 1$ , (b) $\texttt{computation?}(n) = 1$ , (c) $\texttt{program}(m) = \texttt{program}(n)$ , (d) $\texttt{inputs}(m) = \texttt{inputs}(n)$ , and (e) $\texttt{output}(m) \not= \texttt{output}(n)$ ? Justify your answer.
If two computations have different program components, but the two programs encode the same partial recursive function, and the two computations have the same inputs field, do they necessarily have the same subcomputations and the same output?
The height of a computation is the level of maximum nesting of subcomputations within subcomputations -- 0 for a computation in which the program is a primitive, 1 plus the maximum height of the subcomputations for computations in which the program is a composition, a recursion, or an unbounded minimization. Prove that there is a primitive recursive function that takes the encoding for a computation as its input and outputs the height of the computation. (It should output 0 if given a number that does not encode a computation at all.)