zbMATH — the first resource for mathematics

Demuth randomness and computational complexity. (English) Zbl 1223.03026
Demuth tests are a generalization of Martin-Löf tests $$\{G_m\}_{m\in \omega}$$ so that one can exchange the $$m$$-th component a computably bounded number of times. A set $$Z\subseteq \omega$$ fails a Demuth test if $$Z$$ is in infinitely many final versions of the $$G_m$$. One has weak Demuth randomness if $$G_m\supseteq G_{m+1}$$ for each $$m$$.
It is shown that, different from weak-2-randomness, which is a well-known randomness notion stronger than Martin-Löf randomness, each $$\Pi^0_1$$ class of positive measure contains a weakly Demuth random set which is $$\Delta^0_2$$ and high, but no weakly Demuth random set is superhigh. Moreover, any c.e. set Turing-below a Demuth random set is strongly jump-traceable.
Reviewer: Liang Yu (Nanjing)

MSC:
 03D32 Algorithmic randomness and dimension 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text:
References:
 [1] Arslanov, M.M., Some generalizations of a fixed-point theorem, Izv. vyssh. uchebn. zaved. mat., 5, 9-16, (1981) · Zbl 0523.03029 [2] G. Barmpalias, J. Miller, A. Nies, Randomness notions and partial relativization, 20xx (in press). · Zbl 1279.03065 [3] Demuth, Osvald, Some classes of arithmetical real numbers, Comment. math. univ. carolin., 23, 3, 453-465, (1982), (in Russian) · Zbl 0519.03046 [4] Demuth, Osvald, Remarks on the structure of tt-degrees based on constructive measure theory, Comment. math. univ. carolin., 29, 2, 233-247, (1988) · Zbl 0646.03039 [5] Demuth, Osvald; Kučera, A., Remarks on $$1$$-genericity, semigenericity and related concepts, Comment. math. univ. carolin., 28, 1, 85-94, (1987) · Zbl 0655.03029 [6] S. Figueira, D. Hirschfeldt, J. Miller, Selwyn Ng, A Nies, Counting the changes of random $$\Delta_2^0$$ sets, in: CiE 2010, 2010, pp. 1-10. [7] Figueira, S.; Nies, A.; Stephan, F., Lowness properties and approximations of the jump, Ann. pure appl. logic, 152, 51-66, (2008) · Zbl 1137.03025 [8] Gács, P., Every sequence is reducible to a random one, Inform. control, 70, 186-192, (1986) · Zbl 0628.03024 [9] N. Greenberg, A $$\Delta_2^0$$ random set which only computes strongly jump-traceable c.e. sets., J. Symbolic Logic (in press). · Zbl 1220.03042 [10] N. Greenberg, D. Hirschfeldt, A. Nies, Characterizing the strongly jump traceable sets via randomness (in press). · Zbl 1257.03068 [11] Greenberg, N.; Nies, A., Benign cost functions and lowness properties, J. symbolic logic, 76, 1, 289-312, (2011) · Zbl 1221.03036 [12] Hirschfeldt, D.; Nies, A.; Stephan, F., Using random sets as oracles, J. lond. math. soc. (2), 75, 3, 610-622, (2007) · Zbl 1128.03036 [13] Jockusch, Carl G.; Soare, Robert I., Degrees of members of $$\Pi_1^0$$ classes, Pacific J. math., 40, 605-616, (1972) · Zbl 0209.02201 [14] Jockusch, Carl G.; Soare, Robert I., $$\Pi_1^0$$ classes and degrees of theories, Trans. amer. math. soc., 173, 33-56, (1972) · Zbl 0262.02041 [15] B. Kjos-Hanssen, A. Nies, Superhighness, 20xx (in press). [16] Kučera, A., Measure, $$\Pi_1^0$$-classes and complete extensions of $$\operatorname{PA}$$, (), 245-259 [17] Kučera, A., An alternative, priority-free, solution to post’s problem, (), 493-500 [18] Kučera, A., On the use of diagonally nonrecursive functions, (), 219-239 [19] S. Kurtz, Randomness and genericity in the degrees of unsolvability. Ph.D. Dissertation, University of Illinois, Urbana, 1981. [20] Miller, J.; Nies, A., Randomness and computability: open questions, Bull. symbolic logic, 12, 3, 390-410, (2006) · Zbl 1169.03033 [21] Nies, A., Reals which compute little, (), 260-274 · Zbl 1107.03047 [22] Nies, A., Lowness properties and randomness, Adv. in math., 197, 274-305, (2005) · Zbl 1141.03017 [23] Nies, A., Computability and randomness, () · Zbl 1237.03027 [24] Nies, A.; Stephan, F.; Terwijn, S., Randomness, relativization and Turing degrees, J. symbolic logic, 70, 2, 515-535, (2005) · Zbl 1090.03013 [25] Simpson, S., Mass problems and almost everywhere domination, Math. log. Q., 53, 4-5, 483-492, (2007) · Zbl 1123.03041
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.