-triviality in computable metric spaces

Authors:
Alexander Melnikov and André Nies

Journal:
Proc. Amer. Math. Soc. **141** (2013), 2885-2899

MSC (2010):
Primary 03D32, 03F60

Published electronically:
April 4, 2013

MathSciNet review:
3056579

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A point in a computable metric space is called -trivial if

for each positive rational there is an approximation at distance at most from such that the pair is highly compressible in the sense that . We show that this local definition is equivalent to the point having a Cauchy name that is -trivial when viewed as a function from to . We use this to transfer known results on -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

-trivial point.

**1.**George Barmpalias, Douglas Cenzer, Jeffrey B. Remmel, and Rebecca Weber,*𝐾-triviality of closed sets and continuous functions*, J. Logic Comput.**19**(2009), no. 1, 3–16. MR**2475639**, 10.1093/logcom/exn021**2.**L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. S. Miller, A. Nies, and D. Turetsky.

Computing -trivial sets by incomplete random sets.

Preprint, 2012.**3.**Laurent Bienvenu and Rod Downey,*Kolmogorov complexity and Solovay functions*, STACS 2009: 26th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 3, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2009, pp. 147–158. MR**2870648****4.**Vasco Brattka and Guido Gherardi,*Borel complexity of topological operations on computable metric spaces*, J. Logic Comput.**19**(2009), no. 1, 45–76. MR**2475641**, 10.1093/logcom/exn027**5.**Vasco Brattka, Peter Hertling, and Klaus Weihrauch,*A tutorial on computable analysis*, New computational paradigms, Springer, New York, 2008, pp. 425–491. MR**2762094**, 10.1007/978-0-387-68546-5_18**6.**Gregory J. Chaitin,*Information-theoretic characterizations of recursive infinite strings*, Theoret. Comput. Sci.**2**(1976), no. 1, 45–48. MR**0413595****7.**Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan,*Trivial reals*, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore Univ. Press, Singapore, 2003, pp. 103–131. MR**2051976**, 10.1142/9789812705815_0005**8.**D. W. Loveland,*A variant of the Kolmogorov concept of complexity*, Information and Control**15**(1969), 510–526. MR**0274200****9.**A. Melnikov.*Computability and Structure*.

Ph.D. thesis, University of Auckland, 2012.**10.**Joseph S. Miller and André Nies,*Randomness and computability: open questions*, Bull. Symbolic Logic**12**(2006), no. 3, 390–410. MR**2248590****11.**André Nies,*Lowness properties and randomness*, Adv. Math.**197**(2005), no. 1, 274–305. MR**2166184**, 10.1016/j.aim.2004.10.006**12.**André Nies,*Computability and randomness*, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR**2548883****13.**R. Solovay.

Handwritten manuscript related to Chaitin's work.

IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975.**14.**Klaus Weihrauch,*Computable analysis*, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR**1795407**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
03D32,
03F60

Retrieve articles in all journals with MSC (2010): 03D32, 03F60

Additional Information

**Alexander Melnikov**

Affiliation:
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand

Address at time of publication:
Department of Mathematics, Nanyang Technological University, 50 Nanyang Avenue, Singapore 639798

**André Nies**

Affiliation:
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand

Email:
andre@cs.auckland.ac.nz

DOI:
https://doi.org/10.1090/S0002-9939-2013-11528-5

Keywords:
Computable analysis,
metric spaces,
$K$-triviality

Received by editor(s):
October 18, 2011

Received by editor(s) in revised form:
October 28, 2011

Published electronically:
April 4, 2013

Additional Notes:
Both authors were partially supported by the Marsden Fund of New Zealand, grant No. 08-UOA-187.

Communicated by:
Julia Knight

Article copyright:
© Copyright 2013
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.