Topology of Data Types

Length: 60 minutes

There is a surprising correspondence between computability theory and classical topology. Computability is continuity, open sets are recursively enumerable, spaces are Hausdorff if they admit a definable ≠ operation, and a set over which one can universally quantify is compact. The natural numbers, being non-compact, can't be exhaustively searched: given a predicate p you can't guarantee to find a number n for which p(n) is true—there might not be one, and so your search might continue forever. But the naturals can be embedded in a compact set that can be exhaustively searched. Since this larger type can be modeled on the computer, I will present a simple computer program which, given any predicate p, either locates an n for which p(n) is true, or correctly asserts that no such n exists.

1. Start Here
2. Decidability
3. Closure properties of semidecidable sets
4. Topology is reflected in computability
5. Real numbers
6. Equality
7. Compactness
8. ℕ and its compactification
9. (Demonstration)
10. The Cantor Space
11. References

The last part of the talk was a demonstration of the so-called "impossible functional" forall which takes an arbitrary predicate p and correctly semidecides whether p is true of all elements of the extended natural numbers ℕ*. This is the code I used.

Return to: Universe of Discourse main page | Perl Paraphernalia | Other Classes and Talks