15. Arithmetical Complexity of Sets of Functions

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

We are going to lift the whole theory constructed so far to sets of functions instead of sets of numbers. This may seem hopeless, since finite "machines" cannot accept infinite inputs in finite time. But they can "chew" on as much of the infinite input as is necessary in order to draw a conclusion. That will be out guiding idea.

Recursive Functionals

We want to define a formalism in which

f[A, n, k, m](f, y) » y.

is a "partial recursive" mapping from k number arguments and m function arguments to some number using oracle A. If we do it by adding a line to our earlier numbering, the rest of the theory will still work out the way it did before, since the constructions are based on derivation trees. The idea is that "nature" provides the infinite arguments f, not all at once but "piecemeal" as required. We can model this by adding an "evaluation function"

eval(i, x) = f_i(x)

to our derivation trees as follows. The fine print handles the nuisance case in which no functions are given and we ask for the value of a function that runs off the end of the list. While we are at it, we may as well make computation relative to a function.

k = 0 Þ f[g, n, k] = n;
k > 0 Þ

lh(n) = 0 Þ f[g, n, k, m] = C(o, p_1,k);
lh(n) = 1 Þ f[g, n, k, m] = C(s, p_1,k);
lh(n) = 2 Þ f[g, n, k, m] = p_{min(d(n,
0),
k),
k};
lh(n) = 3 Þ f[g, n, k, m] = C(f[d(n, 0), lh(d(n,1))], f[d(d(n, 1), 0), k], ..., f[d(d(n, 1), lh(d(n, 1)) -.1), k]);
lh(n) = 4 Þ f[g, n, k, m] = R(f[d(n, 0), k -. 1], f[d(n, 1), k + 1]);
lh(n) = 5 Þ f[g, n, k, m] = M(f[d(n, 0), k + 1]);
lh(n) = 6 Þ f[g, n, k, m] = C(g, p_1,k);
lh(n) = 7 Ù m = 0 Þ f[g, n, k, m] = C(o, p_1,k);
lh(n) = 7 Ù m > 0 Þ f[g, n, k, m] = C(f_{min(d(n, 0), m),}p_1,k);
lh(n) > 7 Þ f[g, n, k, m] = C(o, p_1,k).

Note that we can define primitive recursive functionals by dropping the lines for the oracle and the minimization operator.
Thus, the diagonal functional

F(g, x) = -sg(g(x))

is primitive recursive and searching for a zero in a given function

F(g) = my g(y) = 0

is partial recursive.
Now we can define recursive and r.e. relations of functions in the usual way. So

R(f) Û f(0) = 0.

is recursive and by the operator version of the projection theorem the following relation is r.e.:

P(g) Û $x f(x) = 0.

Notice that the former requires us to look at just a particular position, while the second requires that we search "nature" until we find what we are looking for.

A relation [functional] is of type (i, j) just in case it has it has i function arguments and j numerical arguments.

Setting things up this way makes it immediately apparent that a universal relation, s-m-n theorem, and recursion theorem can be shown for partial recursive functionals (just add the new clause to the Kleene predicate).

There are just a few details to observe in the construction.

As in the case of oracle computation, the resource bound t should also bound the inputs queried to the input functions.
Code sequences of functions as follows: <f₁, ..., f_n>(x) = <f₁(x), ..., f_n(x)>.
Restriction of a function: f|n = {(x, y): x £ n Ù f(x) = y}.
Restriction of a sequence: f|n = (f₁|n, ..., f_k|n).

If everything is set up in the obvious way, keeping the preceding ideas in mind, we have the result that the universal predicate depends only on initial segments.

U[g](n, t, y, <f>, <x>) Û U[A](n, t, y, <f|t>, <x>).

The functional universal theorem says:

f[g, n, k, m](f, x) » d(mz U[g](n, d(z, 0), d(z, 1), <f|d(z, 0)>, <x>), 1).

As a consequence,
Proposition 1:

f[g, n, k, m](f, x) » y Û $n"g f | n Ì g Þ f[g, n, k, m](g, x).

Exercise 1: convince yourself of any of this that you aren't quite sure of.

Here is a nice result that links topology with computability. Define

F is partial continuous Û "n, F^-1(n) is open.

Proposition 2:

F is partial continuous Û F is partial recursive in some f;
S is open Û S is r.e. in some f;
S is closed Û S is co-r.e. in some f;
S is clopen Û S is frecursive in some f;

Proof: 1. Suppose F is partial recursive in some f.
By proposition 1, the pre-image of each value n is a union of fans.
The union of these fans over the values of F is therefore open.
So F is partial continuous.

To reduce irrelevant clutter, I will show the converse for type (1, 0) functionals.
Suppose F is partial continuous.
The idea is to construct an f that encodes the performance of F on each fan.
Recall the ff indexing q[0], q[1], ... of finite functions from our discussion of the Rice-Shapiro theorem.
Define

f(x) = n + 1 if "g Î [q[x]], F(g) » n and
f(x) = 0 otherwise.

By the continuity of F,

F(g) » n Û $k. f(k) > 0.

Thus

F(g) » f(mx [f(x) > 0 Ù q[f(x)] Í g]) -. 1.

Since q[f(x)] Í g is recursive, F(g) is partial f-recursive.

2, 3, 4: Exercise 2: Show that each open set in Baire space is the domain of a partial continuous functional and apply 1.
-|
Exercise 3: Construct a set of functions that is not recursive in any function.

The Arithmetical Hierarchy on Baire

Once we have r.e. relations of functions, the definition of the arithmetical hierarchy proceeds just as before. The hierarchy theorem still works because the levels are already separated by type (0, 1) relations (sets of numbers).

We also have everything we need for many-one and Turing reducibility, so we have degrees and completeness over relations of mixed type. Some results come for free from topology. The contrapositives of the following results allow us to use the epistemological arguments of the preceding chapter to establish arithmetical lower bounds on sets of functions.

Proposition 3:

S_n[f](S) Þ S_n(S).
P_n[f](S) Þ P_n(S).
D_n[f](S) Þ D_n(S).

Proof: We already showed that sets r.e. in a function are open.
The inductive step is also easy because quantification amounts to a countable union.
-|

Here's a nice question. What is the complexity of

REC(f) Û f is recursive?

Exercise 4: Strut your stuff. Prove an arithmetical completeness theorem for this example. Follow the logic of our bumping pointer analysis of Rec in the preceding chapter 13.