\({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets. (English) Zbl 1402.03063
Summary: G. Hjorth and A. Nies [J. Lond. Math. Soc., II. Ser. 75, No. 2, 495–508 (2007; Zbl 1118.03034)] proposed notions of randomness corresponding to the higher recursion setting. In particular, they defined the notion of \(\Pi_1^1\)-Martin-Löf randomness. In this article we present examples of \(\Pi_1^1\)-Martin-Löf random reals which are obtained as measures of \(\Pi_1^1\) open sets.
Citations:
Zbl 1118.03034References:
| [1] | Becher, V.; Chaitin, G., Another example of higher order randomness, Fund. Inform., 51, 4, 325-338 (2002) · Zbl 1011.68042 |
| [2] | Becher, V.; Daicz, S.; Chaitin, G., A highly random number, (Combinatorics, Computability and Logic, Proceedings of the 3rd International Conference. Combinatorics, Computability and Logic, Proceedings of the 3rd International Conference, DMTCS ’01 (2001), Springer: Springer London), 55-68 · Zbl 0982.68080 |
| [3] | Becher, V.; Grigorieff, S., Random reals and possibly infinite computations, I, J. Symbolic Logic, 70, 3, 891-913 (2005) · Zbl 1089.03037 |
| [4] | Becher, V.; Grigorieff, S., From index sets to randomness in \(\varnothing^n\), II, J. Symbolic Logic, 74, 1, 124-156 (2009) · Zbl 1163.03023 |
| [5] | Chong, C. T.; Yu, L., Recursion Theory, A Generalized Point of View (2015), De Gruyter |
| [6] | Downey, R.; Hirschfeldt, D., Algorithmic Randomness and Complexity (2010), Springer-Verlag · Zbl 1221.68005 |
| [7] | Hjorth, G.; Nies, A., Randomness via effective descriptive set theory, J. Lond. Math. Soc., II Ser., 75, 2, 495-508 (2007) · Zbl 1118.03034 |
| [8] | Jech, T., Set Theory (2003), Springer: Springer Berlin · Zbl 1007.03002 |
| [9] | Martin-Löf, Per, On the notion of randomness, (Intuitionism and Proof Theory, Proc. Conf.. Intuitionism and Proof Theory, Proc. Conf., Buffalo, N.Y., 1968 (1970), North-Holland: North-Holland Amsterdam), 73-78 · Zbl 0203.29903 |
| [10] | Moschovakis, Y., Descriptive Set Theory (2009), Amer. Math. Soc. · Zbl 1172.03026 |
| [11] | Nies, A., Computability and Randomness (2009), Oxford University Press · Zbl 1169.03034 |
| [12] | Sacks, G., Higher Recursion Theory (1990), Springer-Verlag: Springer-Verlag Berlin · Zbl 0716.03043 |
| [13] | Sureson, C., Random reals as measures of natural open sets, Theoret. Comput. Sci., 589, 1-23 (2015) · Zbl 1327.03035 |
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.
