Computability in Locally Compact Spaces
If you have a question about this talk, please contact Paul Levy.
Stephen Kleene showed that any recursive enumerable predicate φ(n) could be put in the form ∃ h.T(p,n,h) where T is decidable.; Using the notion of an effective basis (An,βn) of compact and open subspaces, I will show that this Kleene’s theorem can be adapted to computation of continuous functions between locally compact topological spaces.
The normal form is developed in a similar way to Peter Landin’s SECD machine, but we observe some connections between programming and topology. The stack consists of values like n that correspond to inputs, and has a contravariance property like the compact part An of the basis. Intermediate and output values reside in the heap h, which, like the open part βn of the basis, is covariant, and indeed preserves meets.
The formal meets of the basis elements lead to a generalisation of unification, which is Cleary’s “Logical Arithmetic” in the case of the reals. Roundedness with respect to the way-below or cover relation indicates how to improve the precision of a value and how to perform universal quantification over a compact subspace.
Although this investigation clearly offers a plan for a compiler for the ASD language, I was prompted to do it by theoretical questions. In particular, I can show that any overt subspace of Cantor space or the reals is the image of an RE subset of ℕ.
This talk is part of the Theoretical computer science seminar series.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsBiosciences seminars Condensed Matter Group Meetings School of Mathematics Events
Other talksRSLC PhD/Postdoc Seminar (Chemistry) Long-Term Autonomy in Everyday Environments: A New Challenge for AI and Robotics Growth of homology torsion TBA RSLC PhD/Postdoc Seminar (Chemistry) Solution of an old problem in vector optimisation: Support function of the generalised Jacobian