Effective properties of sets and functions in metric spaces with computability structure

We consider an abstract metric space with a computability structure and an effective separating set. In this article, we also introduce an effectively σ-compact space. The computability of real-valued functions on such a space is defined. It is shown that some of typical propositions in a metric spa...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 1999-05, Vol.219 (1), p.467-486
Main Authors: Yasugi, Mariko, Mori, Takakazu, Tsujii, Yoshiki
Format: Article
Language:English
Subjects:
Computability structure
Computable function
Effective Tietze's extension theorem
Effective σ-compactness
Metric space
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider an abstract metric space with a computability structure and an effective separating set. In this article, we also introduce an effectively σ-compact space. The computability of real-valued functions on such a space is defined. It is shown that some of typical propositions in a metric space, namely Baire category theorem, Tietze's extension theorem and decomposition of unity, can be effectivized. It is also proved that computable functions are dense in continuous functions.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(98)00301-6