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.
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 Talksmjdemail@example.com