Abstract
Cost functions provide a framework for constructions of sets Turing below the halting problem that are close to computable. We carry out a systematic study of cost functions. We relate their algebraic properties to their expressive strength. We show that the class of additive cost functions describes the K-trivial sets. We prove a cost function basis theorem, and give a general construction for building computably enumerable sets that are close to being Turing complete.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
L. Bienvenu, N. Greenberg, A. Kučera, A. Nies, D. Turetsky, Coherent randomness tests and computing the K-trivial sets. J. Eur. Math. Soc. 18, 773–812 (2016)
L. Bienvenu, A. Day, N. Greenberg, A. Kučera, J. Miller, A. Nies, D. Turetsky, Computing K-trivial sets by incomplete random sets. Bull. Symb. Log. 20, 80–90 (2014)
L. Bienvenu, R. Downey, N. Greenberg, W. Merkle, A. Nies, Kolmogorov complexity and Solovay functions. J. Comput. Syst. Sci. 81 (8), 1575–1591 (2015)
C. Calude, A. Grozea, The Kraft-Chaitin theorem revisited. J. Univ. Comput. Sci. 2, 306–310 (1996)
A.R. Day, J.S. Miller, Density, forcing and the covering problem. Math. Res. Lett. 22 (3), (2015). http://arxiv.org/abs/1304.2789
D. Diamondstone, N. Greenberg, D. Turetsky, Inherent enumerability of strong jump-traceability. http://arxiv.org/abs/1110.1435 (2012)
R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity (Springer, Berlin, 2010)
R. Downey, D. Hirschfeldt, A. Nies, F. Stephan, Trivial reals, in Proceedings of the 7th and 8th Asian Logic Conferences (Singapore University Press, Singapore, 2003), pp. 103–131
S. Figueira, A. Nies, F. Stephan, Lowness properties and approximations of the jump. Ann. Pure Appl. Log. 152, 51–66 (2008)
N. Greenberg, A. Nies, Benign cost functions and lowness properties. J. Symb. Log. 76, 289–312 (2011)
N. Greenberg, D. Turetsky, Strong jump-traceability and Demuth randomness. Proc. Lond. Math. Soc. 108, 738–779 (2014)
N. Greenberg, J. Miller, A. Nies, Computing from projections of random sets (submitted)
N. Greenberg, D. Hirschfeldt, A. Nies, Characterizing the strongly jump-traceable sets via randomness. Adv. Math. 231 (3–4), 2252–2293 (2012)
D. Hirschfeldt, A. Nies, F. Stephan, Using random sets as oracles. J. Lond. Math. Soc. (2) 75 (3), 610–622 (2007)
B. Kjos-Hanssen, W. Merkle, F. Stephan, Kolmogorov complexity and the Recursion Theorem, in STACS 2006. Lecture Notes in Computer Science, vol. 3884 (Springer, Berlin, 2006), pp. 149–161
A. Kučera, An alternative, priority-free, solution to Post’s problem, in Mathematical Foundations of Computer Science, 1986 (Bratislava, 1986). Lecture Notes in Computer Science, vol. 233 (Springer, Berlin, 1986), pp. 493–500
A. Kučera, A. Nies, Demuth randomness and computational complexity. Ann. Pure Appl. Log. 162, 504–513 (2011)
A. Kučera, T. Slaman, Low upper bounds of ideals. J. Symb. Log. 74, 517–534 (2009)
A. Kučera, S. Terwijn, Lowness for the class of random sets. J. Symb. Log. 64, 1396–1402 (1999)
A. Melnikov, A. Nies, K-triviality in computable metric spaces. Proc. Am. Math. Soc. 141 (8), 2885–2899 (2013)
A. Nies, Reals which compute little, in Logic Colloquium ‘02. Lecture Notes in Logic (Springer, Heidelberg, 2002), pp. 260–274
A. Nies, Lowness properties and randomness. Adv. Math. 197, 274–305 (2005)
A. Nies, Computability and Randomness. Oxford Logic Guides, vol. 51 (Oxford University Press, Oxford, 2009)
A. Nies, Interactions of computability and randomness, in Proceedings of the International Congress of Mathematicians (World Scientific, Singapore, 2010), pp. 30–57
R.I. Soare, Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series (Springer, Heidelberg, 1987)
R. Solovay, Handwritten Manuscript Related to Chaitin’s Work (IBM Thomas J. Watson Research Center, Yorktown Heights, 1975), 215 pp.
Acknowledgements
Research partially supported by the Marsden Fund of New Zealand, grant no. 08-UOA-187, and by the Hausdorff Institute of Mathematics, Bonn.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this chapter
Cite this chapter
Nies, A. (2017). Calculus of Cost Functions. In: Cooper, S., Soskova, M. (eds) The Incomputable. Theory and Applications of Computability. Springer, Cham. https://doi.org/10.1007/978-3-319-43669-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-43669-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-43667-8
Online ISBN: 978-3-319-43669-2
eBook Packages: Computer ScienceComputer Science (R0)