zbMATH — the first resource for mathematics

Diagonally non-computable functions and fireworks. (English) Zbl 1423.03141
Summary: A set \(\mathcal{C}\) of reals is said to be negligible if there is no probabilistic algorithm which generates a member of \(\mathcal{C}\) with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, the class of coherent completions of Peano Arithmetic or the class of reals of minimal Turing degree. One class of particular interest in the study of negligibility is the class of diagonally non-computable (DNC) functions, proven by A. Kučera [Lect. Notes Math. 1141, 245–259 (1985; Zbl 0622.03031)] to be non-negligible in a strong sense: every Martin-Löf random real computes a DNC function. K. Ambos-Spies et al. [J. Symb. Log. 69, No. 4, 1089–1104 (2004; Zbl 1076.03039)] showed that the converse does not hold: there are DNC functions which compute no Martin-Löf random real. In this paper, we show that the set of such DNC functions is in fact non-negligible using a technique we call ‘fireworks argument’. We also use this technique to prove further results on DNC functions.

03D28 Other Turing degree structures
03D32 Algorithmic randomness and dimension
Full Text: DOI arXiv
[1] Ambos-Spies, Klaus; Kjos-Hanssen, Bjørn; Lempp, Steffen; Slaman, Theodore A., Comparing DNR and WWKL, J. Symb. Log., 69, 4, 1089-1104, (2004) · Zbl 1076.03039
[2] Barmpalias, George; Day, Adam; Lewis-Pye, Andy, The typical Turing degree, Proc. Lond. Math. Soc., 109, 1, 1-39, (2013) · Zbl 1332.03009
[3] Bienvenu, Laurent; Porter, Christopher P., Deep \(\operatorname{\Pi}_1^0\) classes, Bull. Symb. Log., 22, 2, 249-286, (2016) · Zbl 1401.03077
[4] Cai, Mingzhong, Elements of classical recursion theory: degree-theoretic properties and combinatorial properties, (2011), Cornell University, PhD thesis
[5] de Leeuw, Karel; Moore, Edward F.; Shannon, Claude; Shapiro, Norman, Computability by probabilistic machines, (Automata Studies, (1956), Princeton University Press)
[6] Demuth, Oswald, Remarks on the structure of tt-degrees based on constructive measure theory, Comment. Math. Univ. Carol., 29, 2, 233-247, (1988) · Zbl 0646.03039
[7] Dobrinen, Natasha; Simpson, Stephen G., Almost everywhere domination, J. Symb. Log., 69, 3, 914-922, (2004) · Zbl 1075.03021
[8] Dorais, François G.; Hirst, Jeffry L.; Shafer, Paul, Comparing the strength of diagonally non-recursive functions in the absence of \(\operatorname{\Sigma}_2^0\) induction, J. Symb. Log., 80, 1211-1235, (2015) · Zbl 1373.03016
[9] Downey, Rodney; Hirschfeldt, Denis, Algorithmic randomness and complexity, Theory and Applications of Computability, (2010), Springer · Zbl 1221.68005
[10] Greenberg, Noam; Miller, Joseph S., Diagonally non-recursive functions and effective Hausdorff dimension, Bull. Lond. Math. Soc., 43, 4, 636-654, (2011) · Zbl 1225.03055
[11] Carl, Jockusch; Soare, Robert, \(\operatorname{\Pi}_1^0\) classes and degrees of theories, Trans. Am. Math. Soc., 173, 33-56, (1972) · Zbl 0262.02041
[12] Khan, Mushfeq, Shift-complex sequences, Bull. Symb. Log., 19, 2, 199-215, (2013) · Zbl 1285.03057
[13] Khan, Mushfeq; Miller, Joseph S., Forcing with bushy trees, (2015), arXiv preprint · Zbl 1421.03021
[14] Kjos-Hanssen, Bjørn; Merkle, Wolfgang; Stephan, Frank, Kolmogorov complexity and the recursion theorem, Trans. Am. Math. Soc., 363, 10, 5465-5480, (2011) · Zbl 1236.03032
[15] Kučera, Antonin, Measure, \(\operatorname{\Pi}_1^0\) classes, and complete extensions of PA, Lect. Notes Math., 1141, 245-259, (1985)
[16] Kumabe, Masahiro; Lewis, Andrew E. M., A fixed-point-free minimal degree, J. Lond. Math. Soc., 80, 3, 785-797, (2009) · Zbl 1183.03030
[17] Kurtz, Stuart, Randomness and genericity in the degrees of unsolvability, (1981), University of Illinois at Urbana, PhD dissertation
[18] Levin, Leonid; V’yugin, Vladimir, Invariant properties of informational bulks, Lect. Notes Comput. Sci., 53, 359-364, (1977) · Zbl 0409.94019
[19] Martin Donald, Measure, category, and degrees of unsolvability, 1967, Unpublished manuscript.
[20] Paris, Jeffrey, Measure and minimal degrees, Ann. Math. Log., 11, 203-216, (1977) · Zbl 0359.02037
[21] Rumyantsev, Andrei; Shen, Alexander, Probabilistic constructions of computable objects and a computable version of lovász local lemma, (2013), arXiv preprint · Zbl 1317.68131
[22] Rumyantsev, Andrey Yu., Everywhere complex sequences and the probabilistic method, (STACS, LIPIcs, vol. 9, (2011)), 464-471 · Zbl 1230.68119
[23] Simpson, Stephen G., Mass problems associated with effectively closed sets, Tohoku Math. J., 63, 489-517, (2011) · Zbl 1246.03064
[24] V’yugin, Vladimir V., On Turing invariant sets, Sov. Math. Dokl., 17, 1090-1094, (1976) · Zbl 0359.02041
[25] V’yugin, Vladimir V., Algebra of invariant properties of binary sequences, Probl. Pereda. Inf., 18, 2, 83-100, (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.