# Topology of Data Types

**Length:** 60 minutes

## Description

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.

## Outline

- Start Here
- Decidability
- Closure properties of semidecidable sets
- Topology is reflected in computability
- Real numbers
- Equality
- Compactness
- ℕ and its compactification
- (Demonstration)
- The Cantor Space
- 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

mjd-perl-yak+@plover.com