$K$-triviality in computable metric spaces
HTML articles powered by AMS MathViewer
- by Alexander Melnikov and André Nies PDF
- Proc. Amer. Math. Soc. 141 (2013), 2885-2899 Request permission
Abstract:
A point $x$ in a computable metric space is called $K$-trivial if for each positive rational $\delta$ there is an approximation $p$ at distance at most $\delta$ from $x$ such that the pair $p, \delta$ is highly compressible in the sense that $K(p, \delta ) \le K(\delta ) + O(1)$. We show that this local definition is equivalent to the point having a Cauchy name that is $K$-trivial when viewed as a function from $\mathbb {N}$ to $\mathbb {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.References
- George Barmpalias, Douglas Cenzer, Jeffrey B. Remmel, and Rebecca Weber, $K$-triviality of closed sets and continuous functions, J. Logic Comput. 19 (2009), no. 1, 3–16. MR 2475639, DOI 10.1093/logcom/exn021
- L. Bienvenu, A. Day, N. Greenberg, A. Kuc̆era, J. S. Miller, A. Nies, and D. Turetsky. Computing $K$-trivial sets by incomplete random sets. Preprint, 2012.
- 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
- 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, DOI 10.1093/logcom/exn027
- Vasco Brattka, Peter Hertling, and Klaus Weihrauch, A tutorial on computable analysis, New computational paradigms, Springer, New York, 2008, pp. 425–491. MR 2762094, DOI 10.1007/978-0-387-68546-5_{1}8
- Gregory J. Chaitin, Information-theoretic characterizations of recursive infinite strings, Theoret. Comput. Sci. 2 (1976), no. 1, 45–48. MR 413595, DOI 10.1016/0304-3975(76)90005-0
- 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, DOI 10.1142/9789812705815_{0}005
- D. W. Loveland, A variant of the Kolmogorov concept of complexity, Information and Control 15 (1969), 510–526. MR 274200
- A. Melnikov. Computability and Structure. Ph.D. thesis, University of Auckland, 2012.
- Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
- André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- R. Solovay. Handwritten manuscript related to Chaitin’s work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975.
- Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9
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
- MR Author ID: 878230
- ORCID: 0000-0001-8781-7432
- André Nies
- Affiliation: Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
- MR Author ID: 328692
- Email: andre@cs.auckland.ac.nz
- 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
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 141 (2013), 2885-2899
- MSC (2010): Primary 03D32, 03F60
- DOI: https://doi.org/10.1090/S0002-9939-2013-11528-5
- MathSciNet review: 3056579