Readers of this blog are familiar with notions of computability – basically, the question is, what can machines do without human assistance? And you are familiar with machines. Electronic ones of course, but I always like to think of machines as composed of gears, levers and pulleys.

Topology? That’s another story. Rubber doughnuts being continuously stretched but always preserving that hole. Or calculus and differential equations.

So what’s the connection? You’d be surprised

Topology

The formal definition of topology doesn’t shed much light. A topology is a nonempty space (set) X together with a collection of ‘open’ sets that includes X and ∅ and is closed under finite intersection and arbitrary union. A set its closed iff its complement is open. A function from X to X is continuous iff the inverse image of an open set is open. Clear? Hardly. (But remember these concepts.)

What topology is really about is the idea of closeness. A set is open iff all points sufficiently close to a member of the set are also in the set. A set is closed iff any point that has members of the set arbitrarily close to it, is also in the set. A function is continuous iff f(x) is arbitrarily close to f(x’) as long as x’ is sufficiently close to x.

So what has topology to do with computability? A lot, as it turns out. (Besides network topologies, which is not what we’re talking about.) (This is based on lecture given by my PhD supervisor J. W. Addison jr way way back in 1967 (!) in the graduate logic course at UC Berkeley. I remember it vividly.)

The Baire Space

The study of the topological notions of open, closed, and continuous began in analysis with the study of the real numbers and functions over the real numbers. As the discipline progressed, mathematicians realized that the the reals were somewhat inconvenient. For example, the product of the reals with itself (the set of pairs of reals) is not isomorphic to the reals.

These minor difficulties could be cleared up by taking the irrationals as the space studied. Every irrational has a unique decimal expansion but not all expansions (e.g. those that repeat after a certain point) denote irrationals. However every positive irrational has a unique infinite continued fraction expansion

a0+1/(a1+1/(a2+1/(a3+…

Soon topologists dealt directly with the sequence

a0, a1, a2, a3, …

and thus was born the Baire space of infinite sequences of natural numbers (isomorphic to the irrationals). 

What is the topology of the Baire space? If you trace back the definitions it turns out that a set G of infinite sequences is open iff whenever a (= <a0,a1,a2,…>) is in G then there is an n such that every sequence with initial segment <a0,a1,a2,…,a(n)> is also in G.

Open sets in the Baire topology

In other words, if a is in G then there is a finite amount of information about a that implies that a is in G. And this is where computability comes in.

Suppose that we have a Turing machine M with a two-way infinite  tape. We can write a on one half of the tape and start the machine. Let’s say that M accepts a iff it eventually halts and prints “1”. Then the set accepted by M is open.

For example the sets {a: a0 = 5}, {a: a(a0) = 8}, and {a: a(i) = 7 for some i} are all open. Whereas {a: a is increasing} is not.

The converse is not true for computability-over-the-naturals reasons. Let S be any non-re set, e.g. codes for true statements (with quantifiers) of arithmetic. Then {a: a0 is in S} is open but is not the set accepted by any M. We can restore the symmetry by allowing M to have an infinite data base in the form of an element d of the Baire space written on a second tape. The tape d could enumerate all the initial segments that guarantee membership in G.

Now it is true that a set is open iff it is the set accepted by a machine augmented as described.

We know from computability theory that a set defined by being those numbers accepted by a machine is recursively enumerable (re), and vice versa. So in a sense the open subsets of the Baire space are the re subsets. This is the basis for the analogy between computability over the naturals and topology over the Baire space (which is really the irrational numbers).

Closed sets

For the closed sets, let us say that an (augmented) machine rejects a iff at some point it halts and prints “0”. A set F is closed iff there is a machine that rejects exactly the non elements of F. The first two example sets given above are (also) closed, as is the set of increasing sequences. Notice that (unlike over the reals) a set can be clopen – both closed and open.

If a set D is both open (witnessed by augmented machine M1) and closed (witnessed by augmented machine M2) then we can run M1 and M2 in parallel until one of them halts, as eventually must  happen. It’s easy to combine M1 and M2 and their augments into an augmented machine M which accepts elements of D and rejects elements of -D. In this way we get a machine that decides membership in D.

In computability theory a set whose membership is decidable by Turing machine is recursive (decidable, effective). Thus the clopen subsets correspond to decidable subsets of the naturals.

Functions

What about functions? What functions from the Baire space to itself deserve to  be called computable (by augmented Turing machines)? No prize for guessing the continuous functions, and here’s why.

If you trace through the topology definitions it turns out that  b = f(a)  is continuous iff every initial segment of b is determined by at least one initial segment of a. In other words,  b begins 

<b0, b1, b2, … b(m)>

if a begins with some

<a0, a1, a2, …, a(n)>

Thus, any finite amount of information about f(a) is determined by a finite amount of information about a.

Continuous functions as filters

We can code up the (countable) set {(s,t): a has s as an initial segment implies b has t as an initial segment} in an element d of the Baire space. It is then easy to define a machine M augmented with d that computes f incrementally. M starts with a on its main tape then starts reading in a0, a1, a2, … in turn and eventually prints b0 on the other half tape, then eventually b1, then eventually b2, etc.

(Latex images by John Plaice)

Modern computer scientists will recognize M as a filter that transforms the stream a into the stream b:

Dataflow was practically an unknown concept back in 1967 but Addison anticipated it by decades!

Of course that is not the end of the analogy. The G-delta sets (countable intersection of open sets)  correspond to the ∀∃ level of the arithmetic hierarchy. The Borel sets are those closed under complement and intersection and correspond to the hyperarithmetic sets (more precisely, the hyperarithmetic-in-some-d sets).

For me personally, the analogy lead me directly to the game characterization of the ‘Wadge’ reducibility, which formed the basis of my PhD research.

Not only that, my next major research project was dataflow and Lucid – once again, infinite sequences and filters.

Addison’s 1967 lecture was for me the most important of my whole educational career !