K-triviality in computable metric spaces

Abstract

A point x in a computable metric space is called K-trivial if for each positive rational , there is an approximation p at distance at most from x such that the pair p; is highly compressible in the sense that K(p; ) K( ) + O(1). We show that this local de nition is equivalent to the point having a rapid Cauchy name that is K-trivial when viewed as a function from N to N. We use this to transfer known results on K-triviality for functions to the more general setting of metric spaces. For instance, we show that each computable Polish space without isolated points contains an incomputable K-trivial point.