×

Almost everywhere domination and superhighness. (English) Zbl 1123.03040

Summary: Let \(\omega\) be the set of natural numbers. For functions \(f,g: \omega\to\omega\), we say \(f\) is dominated by \(g\) if \(f(n)<g(n)\) for all but finitely many \(n\in \omega\). We consider the standard “fair coin” probability measure on the space \(2^\omega\) of infinite sequences of 0’s and 1’s. A Turing oracle \(B\) is said to be almost everywhere dominating if, for measure 1 many \(X\in 2^\omega\), each function which is Turing computable from \(X\) is dominated by some function which is Turing computable from \(B\). Dobrinen and Simpson have shown [N. L. Dobrinen and S. G. Simpson, “Almost everywhere domination”, J. Symb. Log. 69, No. 3, 914–922 (2004; Zbl 1075.03021)] that the almost everywhere domination property and some of its variant properties are closely related to the reverse mathematics of measure theory. In this paper we exposit some recent results of B. Kjos-Hanssen [“Low for random reals and positive-measure domination”, Proc. Am. Math. Soc. 135, No. 11, 3703–3709 (2007; Zbl 1128.03031)], B. Kjos-Hanssen, J. S. Miller and D. R. Solomon [“Lowness notions, measure and domination” (to appear)], and others concerning LR-reducibility and almost everywhere domination. We also prove the following new result: If \(B\) is almost everywhere dominating, then \(B\) is superhigh, i.e., \(0''\) is truth-table computable from \(B'\), the Turing jump of \(B\).

MSC:

03D28 Other Turing degree structures
03D30 Other degrees and reducibilities in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , Randomness, lowness and degrees. Preprint, 20 pages, in preparation.
[2] Binns, J. Symbolic Logic 71 pp 119– (2006)
[3] Chaitin, J. ACM 2 pp 329– (1975)
[4] , and (eds.), Logic Colloquium ’02: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Colloquium Logicum, held inMünster, Germany, August 3–11, 2002. Lecture Notes in Logic 27 (ASL, 2006).
[5] Cholak, J. Symbolic Logic 71 pp 1057– (2006)
[6] , , , and (eds.), Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20 – August 15, 2005. Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore (World Scientific Publishing Company, Ltd., 2007). In preparation, to appear.
[7] Dobrinen, J. Symbolic Logic 69 pp 914– (2004)
[8] , , , and (eds.), Proceedings of the 7th and 8th Asian Logic Conferences (World Scientific Publishing Company, Ltd., 2003).
[9] , , and , Trivial reals. In [8], pp. 103–131. · Zbl 1044.03027
[10] , and (eds.), Recursion Theory Week. Lecture Notes in Mathematics 1141 (Springer-Verlag, 1985).
[11] , and , Using random sets as oracles. J. London Math. Soc. (2007). Preprint, 17 pages, 2005, accepted for publication.
[12] Jockusch, Trans. Amer. Math. Soc. 275 pp 599– (1983)
[13] Low for random reals and positive-measure domination. Proc. Amer. Math. Soc. (2007). Preprint, 12 pages, 2005, to appear.
[14] , and , Lowness notions, measure and domination. Preprint, 3 pages, in preparation, to appear.
[15] Measure, 01 classes and complete extensions of PA. In [10], pp. 245–259.
[16] Kučera, J. Symbolic Logic 64 pp 1396– (1999)
[17] Martin-Löf, Information and Control 9 pp 602– (1966)
[18] and . In preparation, 2006, to appear.
[19] and , On initial segment complexity and degrees of randomness. Trans. Amer. Math. Soc. (2005). Preprint, 18 pages, to appear.
[20] Mohrherr, Z. Math. Logik Grundlagen Math. 32 pp 5– (1986)
[21] Nies, Advances in Mathematics 197 pp 274– (2005)
[22] Reals which compute little. In [4], pp. 260–274.
[23] Real Variables (Appleton-Century-Crofts, 1959).
[24] Posner, J. Symbolic Logic 46 pp 714– (1981)
[25] Theory of Recursive Functions and Effective Computability (McGraw-Hill, 1967). · Zbl 0183.01401
[26] Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic (Springer-Verlag, 1999). · Zbl 0909.03048
[27] Some fundamental issues concerning degrees of unsolvability. In [6]. Preprint, 21 pages, to appear. · Zbl 1157.03020
[28] Simpson, Math. Log. Quart. 53 pp 483– (2007)
[29] Terwijn, J. Symbolic Logic 66 pp 1199– (2001)
[30] Random sequences. Ph. D. thesis, University of Amsterdam, 1987.
[31] On sequences with simple initial segments. ILLC prepublication series, University of Amsterdam, 1990.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.