BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:Computability in Locally Compact Spaces - Paul Tay
lor
DTSTART:20100414T150000Z
DTEND:20100414T160000Z
UID:TALK361AT
URL:/talk/index/361
DESCRIPTION:Stephen Kleene showed that any recursive enumerabl
e predicate\n*&phi\;(n)* could be put in th
e form &exist\;* h.T(p\,n\,h)*\nwhere *T
* is decidable.\;\nUsing the notion of an effe
ctive basis *(A*_{n}\,&beta\;^{n})\nof compact and open subspaces\,\nI will s
how that this Kleene's theorem can be adapted to c
omputation\nof continuous functions between locall
y compact topological spaces.\n\nThe normal form i
s developed in a similar way to Peter Landin's\nSE
CD machine\, but we observe some connections betwe
en programming\nand topology.\nThe stack consists
of values like *n* that correspond to input
s\,\nand has a contravariance property like the co
mpact part *A*_{n} of the basis. I
ntermediate and output values reside in the heap <
em>h\,\nwhich\, like the open part *&beta\
;*^{n} of the basis\, is covariant\,\n
and indeed preserves meets.\n\nThe formal meets of
the basis elements lead to a generalisation\nof u
nification\, which is Cleary's "Logical Arithmetic
" in the case\nof the reals.\nRoundedness with res
pect to the way-below or cover relation\nindicates
how to improve the precision of a value\nand how
to perform universal quantification over a compact
subspace.\n\nAlthough this investigation clearly
offers a plan for a compiler\nfor the ASD language
\, I was prompted to do it by theoretical question
s.\nIn particular\, I can show that any overt subs
pace of Cantor space\nor the reals is the image of
an RE subset of ℕ.\n
LOCATION:UG06 Learning Centre
CONTACT:Paul Levy
END:VEVENT
END:VCALENDAR