| |
VOLUME 4, ISSUE 3, PAPER 3
|
Exhaustible sets in higher-type computation
|
©Martin Escardo, School of Computer Science, University of Birmingham
|
Abstract
We say that a set is exhaustible if it admits algorithmic universal
quantification for continuous predicates in finite time, and searchable if
there is an algorithm that, given any continuous predicate, either selects an
element for which the predicate holds or else tells there is no example. The
Cantor space of infinite sequences of binary digits is known to be searchable.
Searchable sets are exhaustible, and we show that the converse also holds for
sets of hereditarily total elements in the hierarchy of continuous functionals;
moreover, a selection functional can be constructed uniformly from a
quantification functional. We prove that searchable sets are closed under
intersections with decidable sets, and under the formation of computable images
and of finite and countably infinite products. This is related to the fact,
established here, that exhaustible sets are topologically compact. We obtain a
complete description of exhaustible total sets by developing a computational
version of a topological Arzela--Ascoli type characterization of compact
subsets of function spaces. We also show that, in the non-empty case, they are
precisely the computable images of the Cantor space. The emphasis of this paper
is on the theory of exhaustible and searchable sets, but we also briefly sketch
applications.
|
Publication date: August 27, 2008
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-4(3:3)2008
Hit Counts: 3470 |
 Creative Commons | |
