Asymptotic Density and the Theory of Computability: A Partial Survey

1. Andrews, U., Cai, M., Diamondstone, D., Jockusch, C., Lempp, S.: Asymptotic density, computable traceability, and \(1\)-randomness. Fundam. Math. 234, 41–53 (2016)

   MathSciNet  MATH  Google Scholar 

2. Astor, E., Hirschfeldt, D., Jockusch, C.: Dense computability, upper cones and minimal pairs. In preparation

   Google Scholar 

3. Barzdin, J.: On a frequency solution to the problem of occurrence in a recursively enumerable set. Proc. Steklov Inst. Math. 133, 49–56 (1973)

   MATH  Google Scholar 

4. Bienvenu, L., Day, A., Hölzl, R.: From bi-immunity to absolute undecidability. J. Symb. Log. 78(4), 1218–1228 (2013)

   Article  MathSciNet  MATH  Google Scholar 

5. Cholak, P., Igusa, G.: Bounding a density-\(1\) and quasiminimality in the generic degrees. Preprint

   Google Scholar 

6. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill (2001). Section 29.3: The simplex algorithm, pp. 790–804

   Google Scholar 

7. Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, Springer, New York (2010)

   Book  MATH  Google Scholar 

8. Downey, R.G., Jockusch Jr., C.G., Schupp, P.E.: Asymptotic density and computably enumerable sets. J. Math. Log. 13 (2013). 1350005, 43 pp.

   Google Scholar 

9. Downey, R.G., Jockusch Jr., C.G., McNicholl, T.H., Schupp, P.E.: Asymptotic density and the Ershov Hierarchy. Math. Log. Q. 61, 189–195 (2015)

   Article  MathSciNet  MATH  Google Scholar 

10. Dzhafarov, D.D., Igusa, G.: Notions of robust information coding, computability. To appear

    Google Scholar 

11. Figueira, S., Miller, J.S., Nies, A.: Indifferent sets. J. Log. Comput. 19, 425–443 (2009)

    Article  MathSciNet  MATH  Google Scholar 

12. Gurevich, Y.: Average case completeness. J. Comput. Syst. Sci. 42, 346–398 (1991)

    Article  MathSciNet  MATH  Google Scholar 

13. Harrison-Trainor, M.: The Gamma questions for many-one degrees. Preprint. arXiv: 1606.05701

14. Hirschfeldt, D., Jockusch, C., Kuyper, R., Schupp, P.: Coarse reducibility and algorithmic randomness. J. Symb. Log. 81, 1028–1046 (2016)

    Article  MathSciNet  Google Scholar 

15. Hirschfeldt, D.R., Jockusch, C.G., McNicholl, T., Schupp, P.E.: Asymptotic density and the coarse computability bound. Computability 5, 13–27 (2016)

    Article  MathSciNet  MATH  Google Scholar 

16. Igusa, G.: Nonexistence of minimal pairs for generic computability. J. Symb. Log. 78, 51–522 (2012)

    MathSciNet  Google Scholar 

17. Igusa, G.: The generic degrees of density-\(1\) sets and a characterization of the hyperarithmetic reals. J. Symb. Log. 80, 1290–1314 (2015)

    Article  MathSciNet  MATH  Google Scholar 

18. Jockusch, C.: The degrees of bi-immune sets. Zeitschr. f. math. Logik und Grundlagen d. Math. 15, 135–140 (1969)

    Article  MathSciNet  MATH  Google Scholar 

19. Jockusch, C.G., Schupp, P.E.: Generic computability, Turing degrees, and asymptotic density. J. Lond. Math. Soc. 85, 472–490 (2012)

    Article  MathSciNet  MATH  Google Scholar 

20. Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Generic-case complexity, decision problems in group theory and random walks. J. Algebra 264, 665–694 (2003)

    Article  MathSciNet  MATH  Google Scholar 

21. Klee, V., Minty, G.: How good is the simplex algorithm? Inequalities, III (Proceedings of Third Symposium, University of California, Los Angeles, 1969; dedicated to the memory of Theodore S. Motzkin), pp. 159–175. Academic Press, New York (1972)

    Google Scholar 

22. Kurtz, S.A.: Notions of weak genericity. J. Symb. Log. 48, 764–770 (1983)

    Article  MathSciNet  MATH  Google Scholar 

23. Levin, L.: Average case complete problems. SIAM J. Comput. 15, 285–286 (1986)

    Article  MathSciNet  MATH  Google Scholar 

24. Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Classics in Mathematics. Springer, Heidelberg (2000)

    MATH  Google Scholar 

25. Monin, B.: Asymptotic density, error-correcting codes. https://www.lacl.fr/ benoit.monin/ressources/papers/resolution_gamma.pdf

26. Monin, B., Nies, A.: A unifying approach to the Gamma question. In: 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, pp. 585–596, 6–10 July 2015

    Google Scholar 

27. Myasnikov, A., Osin, D.: Algorithmically finite groups. J. Pure Appl. Algebra 215, 2789–2796 (2011)

    Article  MathSciNet  MATH  Google Scholar 

28. Myasnikov, A., Rybalov, A.: Generic complexity of undecidable problems. J. Symb. Log. 73, 656–673 (2008)

    Article  MathSciNet  MATH  Google Scholar 

29. Myasnikov, A., Shpilrain, V., Ushakov, A.: Non-commutative Cryptography and Complexity of Group-Theoretic Problems. Mathematical Surveys and Monographs, vol. 177. American Mathematical Society (2011)

    Google Scholar 

30. Nies, A.: Computability and Randomness. Oxford University Press, Oxford (2009)

    Book  MATH  Google Scholar 

31. Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trudy Math. Inst. Steklov 44, 3–143 (1955)

    Google Scholar 

32. Post, E.: A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52, 264–268 (1946)

    Article  MathSciNet  MATH  Google Scholar 

33. Rotman, J.: An Introduction to the Theory of Groups. Graduate Texts in Mathematics, 4th edn. Springer, New York (1995)

    Book  MATH  Google Scholar 

34. Terwijn, S.A., Zambella, D.: Algorithmic randomness and lowness. J. Symb. Log. 66, 1199–1205 (2001)

    Article  MATH  Google Scholar 

35. Woess, W.: Cogrowth of groups and simple random walks. Arch. Math. 41, 363–370 (1983)

    Article  MathSciNet  MATH  Google Scholar 

Download references