Lawson computability

Martín Escardó

School of Computer Science, University of Birmingham, UK

MFPS XIX, Montreal, Canada, 19th March 2003

Part of this talk is based on joint work with De Jaeger and Santini

Overview

We begin with topological algebra and finish with the theory of computability.

Topological semilattice

Semilattice L with topology on L making

\begin{matrix}L × L & → & L \\ (x, y) & ↦ & x ∧ y \end{matrix}

into a continuous map. The subject started in the early 50’s. Compact Hausdorff semilattices were a hot topic in the 60’s.

Two crucial examples

1. The unit interval [0, 1] with Euclidean topology.

2. The Vietoris hyperspace of a compact Hausdorff space under the reverse inclusion order.

NB. The Plotkin powerdomain is a special case of the Vietoris hyperspace.

Lawson semilattice

Theorem (Lawson 1969) TFAE for any compact Hausdorff semilattice:

1. Its continuous homomorphisms into the unit interval separate points.

2. Every point has a neighbourhood base of subsemilattices.

(Cf. Locally convex topological vector spaces.)

Definition A Lawson semilattice is such a compact Hausdorff semilattice.

The Lawson topology

Theorem (Lawson 1973) A semilattice admits at most one topology making it into a compact Hausdorff topological semilattice.

Definition This topology, when it exists, is called the Lawson topology.

Domains

Dana Scott independently introduced continuous domains as models of the lambda calculus. Amazing discovery: Theorem (Seminar on continuous semilattices, mid 70’s) The Lawson semilattices are precisely the continuous Scott domains under the Lawson topology.

But does the Lawson topology have anything to do with semantics and computation?

An early appearence of the Lawson topology in semantics

Plotkin introduced SFP domains in order to be able to model non-deterministic computations.

Theorem (Plotkin 1982)

A domain is SFP if and only if it satisfies certain order-theoretical conditions (1), (2) and (3).

Theorem (Plotkin’s 2/3 SFP theorem)

Two of the conditions are together equivalent to compactness in the Lawson topology.

Another appearence

Smyth’s computational intuition (1992 going back to 1983):

1. Scott topology: positive information.

2. Lawson topology: positive and negative information. One of the objectives of this talk is to make this computational intuition precise.

Continuous domains

“x is an approximant of y”

x ≪ y iff for every directed set D, y ≤ ⋁ D implies x ≤ d for some d ∈ D.

Scott’s computational interpretation: Every computation of y or something more defined than y must eventually output x or something more defined than x.

In other words: x is an unavoidable step in any computation of y.

The continuity axiom: Every element of the domain is the directed join of its unavoidable steps.

Effectively given continuous domains

Among the unavoidable steps, we can select countably many which suffice to generate all other elements by taking joins of ascending sequences. Effective presentation of a domain: An explicit selection of such a countable set. Whose members are often referred to as “finite” elements.

(NB. This choice is sometimes forced upon us — cf. algebraic domains.)

Computability. An element is computable if it is the join of an r.e. ascending sequence of finite elements. Our next aim is to show how this notion is tied to the Scott topology.

The Scott topology

An upper set U is Scott open iff for every directed set D with ⋁ D ∈ U there is d ∈ D such that already d ∈ U.

Scott open sets as tests (Smyth 1992): x passes a test iff any computation of x or something more defined than x eventually outputs an approximation that already passes the test.

The Scott topology of a continuous domain: Has a base of open sets of the form ↑ ↑b = {x | b ≪ x}.

Computability again

x is computable iff the relation b ≪ x is r.e. in b, where b ranges over finite elements. That is: The finite approximants of x form an r.e. set. This brings us back to the Scott topology: We have just seen that the sets ↑ ↑b form a base of the Scott topology. Thus: An element is computable iff its basic Scott open neighbourhoods form an r.e. set.

Making this observation into definitions

De Jaeger, Escardó and Santini 2000 A element is Scott computable iff its basic Scott open neighbourhoods form an r.e. set. A element is dual computable iff its basic dual open neighbourhoods form an r.e. set. A element is Lawson computable iff its basic Lawson open neighbourhoods form an r.e. set.

The dual and Lawson topologies

Dual: Usually not considered as interesting on its own right. Has a subbase of open sets of the form

↑̸ b = {x | b ≰ x}.

(Negative tests.)

Lawson: Has the Scott open and dual open sets as a subbase.

Order-theoretic formulations

An element x is:

1. Scott computable iff the relation b ≪ x is r.e. in b.

2. dual computable iff the relation b ≰ x is r.e. in b.

3. Lawson computable iff both relations are r.e.

We now consider concrete examples.

The guiding example: Pℕ

Has as finite elements the finite sets of natural numbers. Any standard enumeration of the finite sets in the sense of recursion theory is an effective presentation. A member of P(ℕ) is:

1. Scott computable iff it is a recursively enumerable set.

2. dual computable iff it has recursively enumerable complement.

3. Lawson computable iff it is a recursive set.

Example: The reals

x ≪ y iff x < y. Every real is the supremum of its rational approximants. ↑ ↑b = (b, ∞) hence Scott topology = topology of lower semicontinuity. ↑̸ c = (−∞, c) hence dual topology = topology of upper semicontinuity. ↑ ↑b∩ ↑̸ c = (b, c) hence Lawson topology = Euclidean topology.

The reals continued

Scott computable = computable from below. dual computable = computable from above. Lawson computable = computable from both sides.

Lawson computability in this case coincides with the usual notion of computability for reals.

(But this example is slightly misleading.)

Example: The interval domain

Closed and bounded real intervals ordered by reverse inclusion. Think of [x, x] = {x} as a total real number and of [x, y] with x < y as a partial real number.

[b, c] ≪ [x, y] iff b < x and y < c. Then [x, y] is:

Scott computable iff x is computable from below and y from above. dual computable iff x is computable from above and y from below. Lawson computable iff x and y are computable from both sides.

The interval domain continued

For total elements, the three notions of computability coincide. This is a computational manifestation of the fact that the relative Scott, dual and Lawson topologies on the total points coincide. Coincidence of the Scott and Lawson topologies on the total elements is known as the Lawson condition for a domain. However, one must be careful in the effective case.

A counter-example

In the domain ℕ_{⊥}, all elements are computable with respect to the three notions.

However, the three topologies are definitely different.

In fact, in the Lawson topology, ⊥ is a point at infinity.

Although all notions of computability coincide, it is not possible to uniformly obtain effective enumerations of neighbourhoods in the Lawson topology from effective enumerations of neighbourhoods in the Scott topology.

The interval domain concluded

Not only do the three notions of computability coincide for total elements, but also:

Given an effective enumeration of the neighbourhoods of a total element in one topology, one can uniformly find an effective enumeration of its neighbourhoods in any of the other two topologies.

This could be called the effective Lawson condition.

Main example: Effective compactness in Euclidean space

In computable analysis, many effective versions of the topological notion of compactness were proposed for subsets of n-dimensional Euclidean space ℝ^{n}.

Brattka and Weihrauch (2000) showed that they fall in three equivalence classes.

Theorem (De Jeager, Escardó and Santini)

They are Scott, dual and Lawson computability.

This is explained as follows.

The Smyth powerdomain of ℝ^{n}

Topologically compact subsets of ℝ^{n} ordered by reverse inclusion. (This generalizes the interval domain.) The finite elements can be taken as the finite unions of polygons with rational vertices. The three notions identified by Brattka and Weihrauch turn out to coincide with Scott, dual and Lawson for this domain.

How did we discover this result?

Brattka and Weihrauch used the Hausdorff metric to construct representatives of each of the three equivalence classes. It is well-known that the Hausdorff metric induces the Vietoris topology. We mentioned that the Vietoris topology is the same as the Lawson topology. So we suspected and then proved what is discussed above. The proof is non-trivial, however, because it involves an effectivization of the proof of equivalence of the Hausdorff and Vietoris/Lawson topologies.

Computability in function spaces

M.H. Escardó. Function-space compactifications of function spaces, Topology and its applications, 120(3):441–463, 2002.

Although this paper doesn’t address computability issues, there are some computability results implicitly.

If the effective Lawson condition holds for the codomain of a function space, then Scott and Lawson computability coincide for total functions.

An important example is the interval domain.

(And, in fact, all continuous Scott domains, and, more generally, all Lawson compact continuous domains such as SFP and FS domains.)

Computability of lower semicontinuous functions

Brattka, Xizhong and Weihrauch introduced notions of computability for lower semicontinuous real-valued functions.

They again turn out to be the same as Scott, dual and Lawson computability.

Summary

Topological semilattices. Domains. Lawson semilattice = Scott domain. However, two different topologies are considered. Both explain independently introduced notions of computability. And so does a third, auxiliary topology.