On the interplay between effective notions of randomness and genericity.

*(English)*Zbl 1445.03049In the last few decades, the field of algorithmic randomness has developed out of the much older field of computability theory. The primary reason for this new field to develop was interest in the question of what makes objects special (or not) within a large set of objects. The simplest setting in which to study this question, and the setting that was studied most intensely, is that of Cantor space. Here, the core question becomes the question of which infinite binary sequences are “typical” and which ones are “unusual” in some way.

There are two important ways of formalising this idea of “typicality”, essentially corresponding to the two field of measure theory and Baire category theory from classical noneffective mathematics, but incorporating effectivity considerations using the tools of computability theory. The two resulting ideas are effective randomness and effective genericity. A large body of results has been obtained in both areas, and is now the subject of several textbooks.

Naturally, the relationship between both possible formalisations has been studied as well, in analogy to how the relation between measure theory and Baire category theory has been studied in noneffective mathematics. In particular, it has been shown that randomness and genericity are orthogonal to each other in the sense that random sequences are not generic and vice versa.

But, taking advantage of the tools provided by computability theory, we can even formulate a much stronger version of this orthogonality: Sufficiently random sequences do not even compute sufficently generic sequences, and vice versa. Before the present article, the strongest known form of this observation was that every \(2\)-random sequence forms a minimal pair in the Turing degrees with every \(2\)-generic sequence, as proven by A. Nies et al. [J. Symb. Log. 70, No. 2, 515–535 (2005; Zbl 1090.03013)].

However, for insufficient levels of randomness or genericity, this stronger form of the orthogonality does not hold: First, S. Kurtz [Randomness and genericity in the degrees of unsolvability. Champaign, IL: University of Illinois at Urbana (PhD Thesis) (1981)] and S. M. Kautz [Degrees of random sequences. Ithaca, NY: Cornell University (PhD Thesis) (1991)] proved that every \(2\)-random sequence computes a \(1\)-generic sequence. And secondly, by a trivial consequence of the Kučera-Gács theorem [A. Kučera, Lect. Notes Math. 1141, 245–259 (1985; Zbl 0622.03031); P. Gács, Inf. Control 70, 186–192 (1986; Zbl 0628.03024)], for arbitrarily large \(n\), every \(n\)-generic sequence is computed by some \(1\)-random sequence. It is therefore natural to wonder at which randomness level (between \(1\)- and \(2\)-randomness) and genericity level (between \(1\)- and \(2\)-genericity) exactly the limit between the weaker and the stronger kind of orthogonality is situated. In the present article, the authors give a precise answer to this question, at least for the notions of randomness and genericity usually studied in the literature.

First, they give an answer to a question of G. Barmpalias et al. [Proc. Lond. Math. Soc. (3) 109, No. 1, 1–39 (2014; Zbl 1332.03009)] by proving that every Demuth random sequence computes a \(1\)-generic. Demuth randomness is a weaker randomness notion than \(2\)-randomness, so that this is a strengthening of the result by Kurtz [loc. cit.] and Kautz [loc. cit.], above. As Kurtz’ and Kautz’ proof is hard to analyse with the necessary precision with regards to the level of randomness needed for it to work, they instead use the framework of fireworks arguments introduced by A. Rumyantsev and A. Shen [Fundam. Inform. 132, No. 1, 1–14 (2014; Zbl 1317.68131)] to show that the set of \(X\)’s that fail to compute a \(1\)-generic can be covered by a new type of test. They then show that this new type of test characterizes Demuth randomness. The new test notion is a variant of a test notion proposed by J. N. Y. Franklin and K. M. Ng [J. Symb. Log. 79, No. 3, 776–791 (2014; Zbl 1353.03046)] to characterise the strictly weaker notion of weak Demuth randomness.

The characterisation of the sequences passing this new test type can also be applied in other contexts involving fireworks arguments. Namely, if an element of a set \(S\) can be obtained with positive probability using fireworks arguments, then every Demuth random computes such an element. In conjunction with a result of L. Bienvenu and L. Patey [Inf. Comput. 253, Part 1, 64–77 (2017; Zbl 1423.03141)] this implies that every Demuth random computes a diagonally noncomputable function which computes no \(1\)-random.

Next, the authors study whether the level of genericity can be increased in their theorem, that is, whether a Demuth random can compute a sequence that has a higher level of genericity than \(1\)-genericity. They give a negative answer for the known genericity notions, by proving that every Demuth random sequence forms a minimal pair with every pb-generic sequence. Here, pb-genericity is a relatively weak genericity notion between \(1\)- and \(2\)-genericity which in particular is implied by weak \(2\)-genericity. The author’s result strengthens a previously known corollary of two results by S. B. Cooper (ed.) et al. [Computability, enumerability, unsolvability. Directions in recursion theory. Cambridge: Cambridge University Press (1996; Zbl 0830.00006)] and R. Downey and K. M. Ng [Lect. Notes Comput. Sci. 5635, 154–166 (2009; Zbl 1268.03053)], as well as the previously mentioned result of A. Nies et al. [J. Symb. Log. 70, No. 2, 515–535 (2005; Zbl 1090.03013)].

Finally, the authors study the situation for weak \(2\)-randomness, a notion that is incomparable with Demuth randomness. They show that for every comeager subset of Cantor space there is a weakly \(2\)-random sequence computing an element of it. In particular, for any level of genericity, there is a sequence \(X\) of that genericity level and some weakly \(2\)-random sequence that computes \(X\). The proof is a modification of a result of G. Barmpalias et al. [J. Symb. Log. 76, No. 2, 491–518 (2011; Zbl 1248.03065)]. It involves a variant of Kučera-Gács coding which, unlike in the original proof of the Kučera-Gács theorem [A. Kučera, Lect. Notes Math. 1141, 245–259 (1985; Zbl 0622.03031); P. Gács, Inf. Control 70, 186–192 (1986; Zbl 0628.03024)] for \(1\)-random sequences, must be allowed to make errors.

There are two important ways of formalising this idea of “typicality”, essentially corresponding to the two field of measure theory and Baire category theory from classical noneffective mathematics, but incorporating effectivity considerations using the tools of computability theory. The two resulting ideas are effective randomness and effective genericity. A large body of results has been obtained in both areas, and is now the subject of several textbooks.

Naturally, the relationship between both possible formalisations has been studied as well, in analogy to how the relation between measure theory and Baire category theory has been studied in noneffective mathematics. In particular, it has been shown that randomness and genericity are orthogonal to each other in the sense that random sequences are not generic and vice versa.

But, taking advantage of the tools provided by computability theory, we can even formulate a much stronger version of this orthogonality: Sufficiently random sequences do not even compute sufficently generic sequences, and vice versa. Before the present article, the strongest known form of this observation was that every \(2\)-random sequence forms a minimal pair in the Turing degrees with every \(2\)-generic sequence, as proven by A. Nies et al. [J. Symb. Log. 70, No. 2, 515–535 (2005; Zbl 1090.03013)].

However, for insufficient levels of randomness or genericity, this stronger form of the orthogonality does not hold: First, S. Kurtz [Randomness and genericity in the degrees of unsolvability. Champaign, IL: University of Illinois at Urbana (PhD Thesis) (1981)] and S. M. Kautz [Degrees of random sequences. Ithaca, NY: Cornell University (PhD Thesis) (1991)] proved that every \(2\)-random sequence computes a \(1\)-generic sequence. And secondly, by a trivial consequence of the Kučera-Gács theorem [A. Kučera, Lect. Notes Math. 1141, 245–259 (1985; Zbl 0622.03031); P. Gács, Inf. Control 70, 186–192 (1986; Zbl 0628.03024)], for arbitrarily large \(n\), every \(n\)-generic sequence is computed by some \(1\)-random sequence. It is therefore natural to wonder at which randomness level (between \(1\)- and \(2\)-randomness) and genericity level (between \(1\)- and \(2\)-genericity) exactly the limit between the weaker and the stronger kind of orthogonality is situated. In the present article, the authors give a precise answer to this question, at least for the notions of randomness and genericity usually studied in the literature.

First, they give an answer to a question of G. Barmpalias et al. [Proc. Lond. Math. Soc. (3) 109, No. 1, 1–39 (2014; Zbl 1332.03009)] by proving that every Demuth random sequence computes a \(1\)-generic. Demuth randomness is a weaker randomness notion than \(2\)-randomness, so that this is a strengthening of the result by Kurtz [loc. cit.] and Kautz [loc. cit.], above. As Kurtz’ and Kautz’ proof is hard to analyse with the necessary precision with regards to the level of randomness needed for it to work, they instead use the framework of fireworks arguments introduced by A. Rumyantsev and A. Shen [Fundam. Inform. 132, No. 1, 1–14 (2014; Zbl 1317.68131)] to show that the set of \(X\)’s that fail to compute a \(1\)-generic can be covered by a new type of test. They then show that this new type of test characterizes Demuth randomness. The new test notion is a variant of a test notion proposed by J. N. Y. Franklin and K. M. Ng [J. Symb. Log. 79, No. 3, 776–791 (2014; Zbl 1353.03046)] to characterise the strictly weaker notion of weak Demuth randomness.

The characterisation of the sequences passing this new test type can also be applied in other contexts involving fireworks arguments. Namely, if an element of a set \(S\) can be obtained with positive probability using fireworks arguments, then every Demuth random computes such an element. In conjunction with a result of L. Bienvenu and L. Patey [Inf. Comput. 253, Part 1, 64–77 (2017; Zbl 1423.03141)] this implies that every Demuth random computes a diagonally noncomputable function which computes no \(1\)-random.

Next, the authors study whether the level of genericity can be increased in their theorem, that is, whether a Demuth random can compute a sequence that has a higher level of genericity than \(1\)-genericity. They give a negative answer for the known genericity notions, by proving that every Demuth random sequence forms a minimal pair with every pb-generic sequence. Here, pb-genericity is a relatively weak genericity notion between \(1\)- and \(2\)-genericity which in particular is implied by weak \(2\)-genericity. The author’s result strengthens a previously known corollary of two results by S. B. Cooper (ed.) et al. [Computability, enumerability, unsolvability. Directions in recursion theory. Cambridge: Cambridge University Press (1996; Zbl 0830.00006)] and R. Downey and K. M. Ng [Lect. Notes Comput. Sci. 5635, 154–166 (2009; Zbl 1268.03053)], as well as the previously mentioned result of A. Nies et al. [J. Symb. Log. 70, No. 2, 515–535 (2005; Zbl 1090.03013)].

Finally, the authors study the situation for weak \(2\)-randomness, a notion that is incomparable with Demuth randomness. They show that for every comeager subset of Cantor space there is a weakly \(2\)-random sequence computing an element of it. In particular, for any level of genericity, there is a sequence \(X\) of that genericity level and some weakly \(2\)-random sequence that computes \(X\). The proof is a modification of a result of G. Barmpalias et al. [J. Symb. Log. 76, No. 2, 491–518 (2011; Zbl 1248.03065)]. It involves a variant of Kučera-Gács coding which, unlike in the original proof of the Kučera-Gács theorem [A. Kučera, Lect. Notes Math. 1141, 245–259 (1985; Zbl 0622.03031); P. Gács, Inf. Control 70, 186–192 (1986; Zbl 0628.03024)] for \(1\)-random sequences, must be allowed to make errors.

Reviewer: Rupert Hölzl (Neubiberg)

PDF
BibTeX
XML
Cite

\textit{L. Bienvenu} and \textit{C. P. Porter}, J. Symb. Log. 84, No. 1, 393--407 (2019; Zbl 1445.03049)

Full Text:
DOI

##### References:

[1] | Andrews, U.; Gerdes, P.; Miller, J. S., The degrees of bi-hyperhyperimmune sets, Annals of Pure and Applied Logic, 165, 3, 803-811, (2014) · Zbl 1323.03054 |

[2] | Barmpalias, G.; Day, A.; Lewis-Pye, A., The typical Turing degree, Proceedings of the London Mathematical Society, 109, 1, 1-39, (2013) · Zbl 1332.03009 |

[3] | Barmpalias, G.; Downey, R.; Ng, K. M., 76, 2, 491-518, (2011) |

[4] | Bienvenu, L.; Downey, R.; Greenberg, N.; Nies, A.; Turetsky, D., 79, 2, 526-560, (2014) |

[5] | Bienvenu, L.; Patey, L., Diagonally non-computable functions and fireworks, Information and Computation, 253, 64-77, (2017) · Zbl 1423.03141 |

[6] | Demuth, O., On some classes of arithmetical real numbers, Commentationes Mathematicae Universitatis Carolinae, 23, 453-465, (1982) · Zbl 0519.03046 |

[7] | Demuth, O., Remarks on the structure of tt-degrees based on constructive measure theory, Commentationes Mathematicae Universitatis Carolinae, 29, 2, 233-247, (1988) · Zbl 0646.03039 |

[8] | Downey, R.; Hirschfeldt, D., Algorithmic Randomness and Complexity, (2010), Springer-Verlag: Springer-Verlag, New York · Zbl 1221.68005 |

[9] | Downey, R.; Jockusch, C.; Stob, M.; Cooper, S. B.; Slaman, T. A.; Wainer, S. S., Computability, Enumerability, Unsolvability. Directions in Recursion Theory, Array nonrecursive degrees and genericity, 93-104, (1996), Cambridge University Press: Cambridge University Press, Cambridge |

[10] | Downey, R.; Ng, K. M., Conference on Computability in Europe (CiE 2009), 5635, Lowness for Demuth randomness, 154-166, (2009), Springer-Verlag: Springer-Verlag, Berlin · Zbl 1268.03053 |

[11] | Franklin, J. N. Y.; Ng, K. M., Difference randomness, Proceedings of the American Mathematical Society, 139, 345-360, (2011) · Zbl 1214.03029 |

[12] | Franklin, J. N. Y.; Ng, K. M., 79, 3, 776-791, (2014) |

[13] | Greenberg, N.; Turetsky, D., Strong jump-traceability and Demuth randomness, Proceedings of the London Mathematical Society, 108, 738-779, (2014) · Zbl 1303.03074 |

[14] | Kautz, S. M., Degrees of random sequences, (1991), Cornell University |

[15] | Kučera, A., Measure, \({\rm{\Pi }}_1^0\) classes, and complete extensions of PA, Lecture Notes in Mathematics, 1141, 245-259, (1985) |

[16] | Kucera, A.; Nies, A., Demuth randomness and computational complexity, Annals of Pure and Applied Logic, 162, 7, 504-513, (2011) · Zbl 1223.03026 |

[17] | Kurtz, S., Randomness and Genericity in the Degrees of Unsolvability, (1981), University of Illinois at Urbana |

[18] | Nies, A., Computability and Randomness, (2009), Oxford University Press: Oxford University Press, Oxford · Zbl 1169.03034 |

[19] | Nies, A.; Stephan, F.; Terwijn, S., 70, 515-535, (2005) |

[20] | Rumyantsev, A. Y.; Shen, A., Probabilistic constructions of computable objects and a computable version of Lovász local lemma, Fundamenta Informaticae, 132, 1, 1-14, (2014) · Zbl 1317.68131 |

[21] | Yates, C. E. M., 35, 2, 243-266, (1970) |

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.