Skip to main content
Springer Nature Link
Log in

Calculus of Cost Functions

  • Chapter
  • First Online:
The Incomputable

Part of the book series: Theory and Applications of Computability ((THEOAPPLCOM))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 109.00
Price excludes VAT (USA)
Softcover Book
USD 139.99
Price excludes VAT (USA)
Hardcover Book
USD 139.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We note that the result (c) has a complicated history. Solovay [26] built a \(\Delta _{2}^{0}\) incomputable set A that is K-trivial. Constructing a c.e. example of such a set was attempted in various sources such as [4], and in unpublished work of Kummer.

References

  1. 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)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    Article  MathSciNet  MATH  Google Scholar 

  3. L. Bienvenu, R. Downey, N. Greenberg, W. Merkle, A. Nies, Kolmogorov complexity and Solovay functions. J. Comput. Syst. Sci. 81 (8), 1575–1591 (2015)

    Article  MATH  Google Scholar 

  4. C. Calude, A. Grozea, The Kraft-Chaitin theorem revisited. J. Univ. Comput. Sci. 2, 306–310 (1996)

    MATH  Google Scholar 

  5. A.R. Day, J.S. Miller, Density, forcing and the covering problem. Math. Res. Lett. 22 (3), (2015). http://arxiv.org/abs/1304.2789

  6. D. Diamondstone, N. Greenberg, D. Turetsky, Inherent enumerability of strong jump-traceability. http://arxiv.org/abs/1110.1435 (2012)

  7. R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity (Springer, Berlin, 2010)

    Book  MATH  Google Scholar 

  8. 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

    MATH  Google Scholar 

  9. S. Figueira, A. Nies, F. Stephan, Lowness properties and approximations of the jump. Ann. Pure Appl. Log. 152, 51–66 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. N. Greenberg, A. Nies, Benign cost functions and lowness properties. J. Symb. Log. 76, 289–312 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  11. N. Greenberg, D. Turetsky, Strong jump-traceability and Demuth randomness. Proc. Lond. Math. Soc. 108, 738–779 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  12. N. Greenberg, J. Miller, A. Nies, Computing from projections of random sets (submitted)

    Google Scholar 

  13. N. Greenberg, D. Hirschfeldt, A. Nies, Characterizing the strongly jump-traceable sets via randomness. Adv. Math. 231 (3–4), 2252–2293 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. D. Hirschfeldt, A. Nies, F. Stephan, Using random sets as oracles. J. Lond. Math. Soc. (2) 75 (3), 610–622 (2007)

    Google Scholar 

  15. 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

    Google Scholar 

  16. 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

    Google Scholar 

  17. A. Kučera, A. Nies, Demuth randomness and computational complexity. Ann. Pure Appl. Log. 162, 504–513 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. A. Kučera, T. Slaman, Low upper bounds of ideals. J. Symb. Log. 74, 517–534 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. A. Kučera, S. Terwijn, Lowness for the class of random sets. J. Symb. Log. 64, 1396–1402 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  20. A. Melnikov, A. Nies, K-triviality in computable metric spaces. Proc. Am. Math. Soc. 141 (8), 2885–2899 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  21. A. Nies, Reals which compute little, in Logic Colloquium ‘02. Lecture Notes in Logic (Springer, Heidelberg, 2002), pp. 260–274

    Google Scholar 

  22. A. Nies, Lowness properties and randomness. Adv. Math. 197, 274–305 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  23. A. Nies, Computability and Randomness. Oxford Logic Guides, vol. 51 (Oxford University Press, Oxford, 2009)

    Google Scholar 

  24. A. Nies, Interactions of computability and randomness, in Proceedings of the International Congress of Mathematicians (World Scientific, Singapore, 2010), pp. 30–57

    Google Scholar 

  25. R.I. Soare, Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series (Springer, Heidelberg, 1987)

    Book  MATH  Google Scholar 

  26. R. Solovay, Handwritten Manuscript Related to Chaitin’s Work (IBM Thomas J. Watson Research Center, Yorktown Heights, 1975), 215 pp.

    Google Scholar 

Download references

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

  1. Department of Computer Science, University of Auckland, Auckland, New Zealand

    André Nies

Authors
  1. André Nies
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to André Nies .

Editor information

Editors and Affiliations

  1. School of Mathematics, University of Leeds, Leeds, United Kingdom

    S. Barry Cooper

  2. Dept. of Mathematical Logic & Applications, Sofia University, Sofia, Bulgaria

    Mariya I. Soskova

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics

Search

Navigation