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