14.  Recursive Operator Theory

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

Until now, we viewed computation as a mechanically directed process arising from a discrete, finite input.  This seems rather limited in scope, however.  Animals and robots don't get single inputs and produce single outputs; they receive a potentially infinite stream of inputs from the environment and they generate a potentially infinite stream of responses to it.  At any given time, the agent receives only some finite chunk of the full information afforded in the limit.  But nonetheless, this piece-meal processing of an infinite input determines a mapping from infinite objects to infinite objects.  Such a mapping is called a recursive operator.

For obvious reasons, recursive operator theory serves as the basis of computational learning theory, a computational account of learning from experience.  Since this is a recursion theory class we will look at the basic theory first and then apply it to questions about learning.

Recursive operator theory connects standard anaysis with computability.  The basic idea is that a machine chewing on initial segments of an infinite sequence has many of the properties of a continuous function on the reals, which determines its value (an infinite decimal expansion) by chewing on initial segments of an infinite decimal expansion.

A Little Point-Set Topology

A topological space is a pair (X, X), where X is a set and X is a collection of subsets of X satisfying:
  1. X(X)
  2. X(Æ)
  3. X is closed under finite intersection.
  4. X is closed under arbitrary union.
A set is open (in the space) just in case it is in X.
A set is closed just in case is complement is open.
A clopen set is both closed and open.
A basis for a topological space is a collection of sets that generates the open sets of the space when closed under arbitrary union.
A space is separableÛ it has a countable basis.

Cute example:  X has two elements a, b.
X = {{a, b}, {a}, Æ}.
Thus, {a} is open but not closed and {b} is closed but not open.

Standard example:  Let R be the real numbers.
A half-open interval is a set of form [x, y) = {z: x £z<y}.
An open set is a union of half-open intervals.

The "open" and "closed" talk is justified by the fact that in real line, each open interval (x, y) is open (but not closed) and each closed interval [x, y] is closed but not open.  In the real line, the only clopen sets are the trivial sets R, Æ.

Exercise 3:  Topology arose in the foundations of analysis, as an epistemological grounding for the calculus.  Unfortunately, the usual presentation in terms of disks with dotted borders obscures the deeply epistemological character of the subject.  Here is a way of seeing the epistemological dimension of topology directly. Argue informally that the collection of all "empirically verifiable hypotheses" constitutes the open sets of a topological space.  What do you think the points in the space correspond to?  What sorts of cognitive limitations would screw up your argument?

We will be interested primarily in a different space:

Our example: Let F be the set of all partial unary functions.
Let [q] denote the set of all partial functions extending q.
Fan = {[q]: q is a finite function}.
Let O consist of sets formed by taking arbitrary unions of elements of Fan.
Let Pit = (F, O).

Pit stands for "positive information topology".  The open sets in Pit may be thought of as hypotheses about finite functions that could be verified by "seeing" some finite amount of the function.  The closed sets may be thought of as hypotheses that are refutable by means of such information.

Exercise 2:  Show that Pit is a topological space.

Exercise 3:  Show that each singleton {f} is closed but not open in Pit.  Hint: think about the complement.
Show that each fan [q] is clopen in Pit.

If we think of open sets as "neighborhoods", then a limit point of a set is a point that is so close that every neighborhood around it catches some of the set.  Let S be an arbitrary subset of X.  Define:

z is a limit point of S in (X, X) Û "A, X(A) ÙA(z) ÞAÇ S¹ Æ.
z is an interior point of S in (X, X) Û $A, X(A) ÙA(z) ÙA Ç ØS = Æ.
z is a boundary point of S in (X, X) Û z is a limit point of S and of ØS.
Proposition 0 (Duality):  z is a limit point of S Û z is not an interior point of ØS.

Proof:  By the form of the definition.
-|

Proposition 1:  Either z is an interior point of S or an interior point of ØS or a boundary point of S.

Proof:  By duality, a limit point of both S and ØS is an interior point of neither.
-|

More epistemology: in Pit, a limit point z of a set S is a partial function f such such that any finite information qÍ f drawn from z is consistent with S.  So no information about z could possibly refute S!  Thus, the zero constant function (the sun will always rise) is a limit point of its complement (the sun will stop rising some time).  The everywhere undefined function Æ is a limit point of every set (null information can be extended in every possible way).  That is why the everywhere undefined function was such a potent source of undecidability arguments in chapter 8.

That doesn't pose any difficulty if S is true in z (i.e., z  is an element of S).  But what if z  is not an element of S?  Then any information received from world (in z which S is false) is consistent with the truth of S.  That is the classical problem of induction!

The problem of induction is the problem of missing limit points!
An interior point is a partial function that eventually affords evidence verifying S.  A boundary point of S is not an interior point but it is a limit point, so it poses the problem of induction  either for S or for ØS.Here is a striking statement:
The problem of induction for S arises precisely only in the boundary of S.
These concepts provide a more intuitive characterization of open and closed sets.

Proposition 2: A is closed ÛA contains each of its limit points.

Proof:  Suppose A is closed.
Suppose ØA(z).
 ØA is open (definition of closed).
 ØA contains z but misses all of A.
So z is not a limit point of A.

Conversely, suppose A contains all of its limit points.
Then for each point z in ØA, there is an open set S[z] that contains z but misses all of A.
The union Èz Î A S[z] exhausts ØA and misses all of A.
-|

Proposition 3: A is open Û each point of A is an interior point.

Proof: Suppose A is open.
Suppose A(z).
Then A witnesses that z is interior to A.

Conversely, suppose that each point z of A is an interior point.
Then for each z, there is an open set S[z] Í A that contains z.
The union Èz Î A S[z] exhausts A and contains only elements of A.
Hence, the union is precisely A.
-|

The closure of A = cl(A) =  {z Î X: is a limit point of A}.
The interior of A = int(A) = {z Î X: is an interior point of A}.
The boundry of A = bdry(A) = {z Î X: is a boundary point of A}.
Proposition 4:
  1. cl(A) = the least closed superset of A.
  2. int(A) = the greatest open subset of A.
  3. bdry(A) = cl(A) - int(A).
Proof:  1. Suppose z is a limit point of A.
Then by the definition, z is a limit point of B.
Apply proposition 3.
So each closed superset of A contains z.
So the least one does.

Conversely, suppose z is an element of each closed superset of A.
So in particular, z is an element of A.

2. From 1, by duality.

3.  By proposition 1.
-|

Maps and Continuity

The concept of open set is mainly employed to define continuity.  Geometrically, continuity reflects stretching and shrinking without tearing or pasting.  Epistemically (and more fundamentally) it reflects an empirical process according to which approximations of the output are produced in response to increasing information about the input (perhaps with a time lag).
Let F: X ®X.
Now define:
F is continuous Û" open S, F-1(S) is open.
Geometrically, if there is a "gap"or discontinuity in the graph of a unary function defined everywhere on the reals, the pre-image of an open interval containing the point of discontinuity will not be open (why?).

Let's consider what continuity amounts to in the space Pit.

F is empiricalÛ "f "x, y  ((F(f))(x) » y Û $ finite q Í f. (F(q))(x) » y).
Proposition 5:  In the space Pit, F is continuousÛ F is empirical .

Proof:  Suppose F is empirical.
Let basis element [q] be given.
Let f be in the preimage of [q], so that F(f) Î [q].
Then for each x Îdom(q), y, q(x) » y Û $ finite dx Í f. (F(d))(x) » y).
Form the finite union df = Èx Îdom(q)dx.
Thus, df is a finite function.
By construction, [df ] ÍF-1([q]) and f Î [df ].
Hence, ÈfÎF-1([q])df = F-1([q]).
So F-1([q]) is open.
To see that the preimage of an arbitrary open set is open, form the open preimage of each basis element included in the set and take the union of these, which is open by axiom 4.

Conversely, suppose F is continuous.
Exercise 4:  Complete the proof.
-|

In Pit, we will focus on two properties of maps:

F is continuous (empirical) Û "f "x, y (F(f))(x) » y Û$ finite q. (F(q))(x) » y.
F is monotoneÛ"f,y, f Í y Þ F(f) Í F(y).
A stronger property than continuity requires that each value of the output function be determined by "past" information about the input function:
F is LipschitzÛ"f "x, y (F(f))(x) »y Û$q. max(dom(q)) £xÙ (F(q))(x) »y.
Exercise 1:  Find an example of an operator that is continuous but not Lipschitz.  Find an example of an operator that is continuous but not monotone.  Find an example of an operator that is monotone but not continuous or Lipschitz.

The Borel Hierarchy on Pit

Topology alone gives rise to a hierarchy analogous to the arithmetical hierarchy of recursion theory.  Here's an extended analogy.
verifiable : open : r.e. ::
refutable : closed : co-r.e.::
decidable : clopen : recursive ::
empirical : continuous : computable
The Borel or "bold-faced" hierarchy on Pit is defined as follows, by transfinite recursion on the ordinals.  The idea is to start out with open sets and to build complexity by countable union and complementation.  Think of the existential quantifiers in the arithmetical hierarchy as countable, "r.e. unions" or unions over r.e. sets of indices.  Thus, the Borel hierarchy allows "ideal" verification in the base case and "ideal" disjunctions at each complexity jump.  In both places, the arithmetical hierarchy insists on an effective concept.
S0(S) Û S is clopen.
Sa(S) Û $ countable G Í Èg <a Sb .  S = ÈP Î G ØP.
Pa(S) Û Sa(ØS).
Da(S) Û Sa(S) Ù Pa(S).
These classes satisfy closure laws analogous to those for the arithmetical hierarchy, except that existentential quantification is replaced with countable union.  Check for yourself.

The initial segment of the hierarchy of height w is called the finite Borel hierarchy.

To establish a finite Borel hierarchy theorem, we follow our earlier approach of setting up an indexing for each class and diagonalizing once for all over each indexing.  The technique goes back at least to Kuratowski.

We can't use natural numbers as indices, of course, since there are uncountably many open sets.  But we can use functions as indices.

Here's the trick:
Recall the ff indexing q[k] of finite the functions in chapter 8.

q[n](x) = mz £ n $w£ n(<x, z> = d(n, w)).
Each open set S is a countable union of fans [q].
We may, therefore, uniquely code S by listing the finite functions that determine its fans.
W1[f](y) Û $x  q[f(x)] Í y.
To deal with the recursive clause, we dovetail one infinite sequence into another to simulate existential quantification over an infinite sequence of variables.

Let d be a function.
Let d[x] denote the restriction of y to the domain {<x, 0>, <x, 1>, ..., <x, n>, ...}.
So given a countable collection of functions f0, ..., fn, ..., we can concoct a single d such that for each x, y,

d[x](<x, y>)  = fx(y).
Now given a countable collection Wn[f0], ..., Wn[fn], ..., we can construct d for f0, ..., fn, ..., as just described and let
Wn + 1[d] = Èn ØWn[f0].
To summarize:
W1[f](y) Û $x q[f(x)] Í y.
Wn + 1[f](y) = $x ØWn[f[x]].
It is easy now to show that we have indices for each finite Borel

Proposition 6:  Sn(S) Û $f. S = Wn[f].
-|

Now the usual Cantor diagonal establishes:
Proposition 7 (finite Borel hierarchy theorem):  Sn Ì Sn + 1.
-|

Continuous m-Reducibility (Wadge Reducibility)

Under construction.

Recursive Operators Defined

The idea is to view recursive operators as ordinary machines that can return a specific position in the function that is the value of the operator after inspecting only a finite amount of information in the given function.  If the function that is the value of the operator is undefined at that point, the machine goes into an infinite loop.

Recall the ff indexing q[k] of finite the functions in chapter 8.

q[n](x) = mz £ n $w£ n(<x, z> = d(n, w)).
Define
(F[z](f))(x) = y Û $k. q[k] Í f Ù f[z](k, x) = y.
Let Y be a mapping from partial functions to partial functions.
Y is a recursive operator Û $z. Y = F[z].
Under construction
 
 
 

A