Computable measure theory and algorithmic randomness. (English) Zbl 07464645
Brattka, Vasco (ed.) et al., Handbook of computability and complexity in analysis. Cham: Springer. Theory Appl. Comput., 227-270 (2021).
Summary: We provide a survey of recent results in computable measure and probability theory, from the perspectives of both computable analysis and algorithmic randomness, and discuss the relations between them.
For the entire collection see [Zbl 1472.03001].
For the entire collection see [Zbl 1472.03001].
MSC:
| 03D78 | Computation over the reals, computable analysis |
References:
| [1] | Ackerman, N.L., Freer, C.E., Roy, D.M.: On computability and disintegration. Mathematical Structures in Computer Science27(8), 1287-1314 (2017) · Zbl 1423.03251 |
| [2] | Allen, K., Bienvenu, L., Slaman, T.A.: On zeros of Martin-L¨of random Brownian motion. Journal of Logic and Analysis6, Paper 9, 34 (2014) · Zbl 1346.03044 |
| [3] | Archibald, M., Brattka, V., Heuberger, C.: Randomness with respect to the signed-digit representation. Fundamenta Informaticae83(1-2), 1-19 (2008) · Zbl 1147.68029 |
| [4] | Asarin, E., Pokrovskii, A.: Use of the Kolmogorov complexity in analyzing control system dynamics. Avtomatika i Telemekhanika1(1986) · Zbl 0605.93048 |
| [5] | Avigad, J.: Uncomputably noisy ergodic limits. Notre Dame Journal of Formal Logic53(3), 347-350 (2012) · Zbl 1258.03084 |
| [6] | Avigad, J., Dean, E.T., Rute, J.: Algorithmic randomness, reverse mathematics, and the dominated convergence theorem. Annals of Pure and Applied Logic163(12), 1854-1864 (2012) · Zbl 1259.03021 |
| [7] | Avigad, J., Gerhardy, P., Towsner, H.: Local stability of ergodic averages. Transactions of the American Mathematical Society362, 261-288 (2010) · Zbl 1187.37010 |
| [8] | Axon, L.M.: Algorithmically random closed sets and probability. Ph.D. thesis. Department of Mathematics, University of Notre Dame (2010) |
| [9] | Axon, L.M.: Martin-L¨of randomness in spaces of closed sets. The Journal of Symbolic Logic 80(2), 359-383 (2015) · Zbl 1375.03048 |
| [10] | Barmpalias, G., Brodhead, P., Cenzer, D., Dashti, S., Weber, R.: Algorithmic randomness of closed sets. Journal of Logic and Computation17(6), 1041-1062 (2007) · Zbl 1155.03031 |
| [11] | Bauwens, B.: Conditional measure and the violation of van Lambalgen’s theorem for MartinL¨of randomness. Theory of Computing Systems60(2), 1-10 (2017) · Zbl 1420.03098 |
| [12] | Becher, V., Figueira, S.: An example of a computable absolutely normal number. Theoretical Computer Science270, 947-958 (2002) · Zbl 1002.11064 |
| [13] | Bienvenu, L., Day, A., Mezhirov, I., Shen, A.: Ergodic-type characterizations of algorithmic randomness. In: F. Ferreira, B. L¨owe, E. Mayordomo, L.M. Gomes (eds.) CiE 2010,Lecture Notes in Computer Science, vol. 6158, pp. 49-58. Springer, Berlin (2010) · Zbl 1286.03138 |
| [14] | Bienvenu, L., Day, A.R., Hoyrup, M., Mezhirov, I., Shen, A.: A constructive version of Birkhoff’s ergodic theorem for Martin-L¨of random points. Information and Computation 210, 21-30 (2012) · Zbl 1257.03067 |
| [15] | Bienvenu, L., G´acs, P., Hoyrup, M., Rojas, C., Shen, A.: Algorithmic tests and randomness with respect to a class of measures. Proceedings of the Steklov Institute of Mathematics 274(1), 34-89 (2011) · Zbl 1294.03032 |
| [16] | Bienvenu, L., Merkle, W.: Effective randomness for computable probability measures. In: D. Cenzer, R. Dillhage, T. Grubba, K. Weihrauch (eds.) Proceedings of the Third International Conference on Computability and Complexity in Analysis,Electronic Notes in Theoretical Computer Science, vol. 167, pp. 117-130. Elsevier, Amsterdam (2007), CCA 2006, Gainesville, Florida, USA, November 1-5, 2006 · Zbl 1262.03064 |
| [17] | Bienvenu, L., Monin, B.: Von Neumann’s biased coin revisited. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012, pp. 145-154. IEEE Computer Society (2012) · Zbl 1364.03059 |
| [18] | Bishop, E.: Foundations of Constructive Analysis. McGraw-Hill, New York (1967) · Zbl 0183.01503 |
| [19] | Bosserhoff, V.: Are unbounded linear operators computable on the average for Gaussian measures? Journal of Complexity24(4), 477-491 (2008) · Zbl 1155.65115 |
| [20] | Bosserhoff, V.: Notions of probabilistic computability on represented spaces. Journal of Universal Computer Science14(6), 956-995 (2008) · Zbl 1227.03058 |
| [21] | Brattka, V., Gherardi, G., H¨olzl, R.: Las Vegas computability and algorithmic randomness. In: E.W. Mayr, N. Ollinger (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015),Leibniz International Proceedings in Informatics (LIPIcs), vol. 30, pp. 130-142. Schloss Dagstuhl-Leibniz-Zentrum f¨ur Informatik, Dagstuhl, Germany (2015) · Zbl 1355.68132 |
| [22] | Brattka, V., Gherardi, G., H¨olzl, R.: Probabilistic computability and choice. Information and Computation242, 249-286 (2015) · Zbl 1320.03071 |
| [23] | Brattka, V., Miller, J.S., Nies, A.: Randomness and differentiability. Transactions of the American Mathematical Society368(1), 581-605 (2016) · Zbl 1402.03062 |
| [24] | Brin, M., Stuck, G.: Introduction to Dynamical Systems. Cambridge University Press (2002) · Zbl 1314.37002 |
| [25] | Brodhead, P., Cenzer, D., Remmel, J.B.: Random continuous functions.In: D. Cenzer, R. Dillhage, T. Grubba, K. Weihrauch (eds.) Proceedings of the Third International Conference on Computability and Complexity in Analysis,Electronic Notes in Theoretical Computer Science, vol. 167. Elsevier, Amsterdam (2007), CCA 2006, Gainesville, Florida, USA, November 1-5, 2006 · Zbl 1262.03065 |
| [26] | Davie, G.: The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity. Annals of Probability29(4), 1426-1434 (2001) · Zbl 1017.60002 |
| [27] | Davie, G., Fouch´e, W.L.: On the computability of a construction of Brownian motion. Mathematical Structures in Computer Science23, 1257-1265 (2013) · Zbl 1286.68249 |
| [28] | Demuth, O.: The differentiability of constructive functions of weakly bounded variation on pseudo numbers (Russian). Comment. Math. Univ. Carolinae16(3), 583-599 (1975) · Zbl 0325.02023 |
| [29] | Diamondstone, D., Kjos-Hanssen, B.: Members of random closed sets. In: K. Ambos-Spies, B. L¨owe, W. Merkle (eds.) Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings,Lecture Notes in Computer Science, vol. 5635, pp. 144-153. Springer (2009) · Zbl 1233.03049 |
| [30] | Doob, J.: Measure Theory.Graduate Texts in Mathematics. Springer-Verlag (1994) · Zbl 0791.28001 |
| [31] | Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity.Theory and Applications of Computability. Springer, New York (2010) · Zbl 1221.68005 |
| [32] | Edalat, A.: The Scott topology induces the weak topology. In: LICS ’96: Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p. 372. IEEE Computer Society, Washington, DC, USA (1996) |
| [33] | Edalat, A.: A computable approach to measure and integration theory. Information and Computation207(5), 642-659 (2009) · Zbl 1169.03032 |
| [34] | F´er´ee, H., Ziegler, M.: On the computational complexity of positive linear functionals on C[0; 1]. In: I.S. Kotsireas, S.M. Rump, C.K. Yap (eds.) Mathematical Aspects of Com |
| [35] | Springer, Cham (2016), 6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers |
| [36] | Fouch´e, W.: Arithmetical representation of Brownian motion I. The Journal of Symbolic Logic65, 421-442 (2000) · Zbl 0944.60087 |
| [37] | Fouch´e, W.: The descriptive complexity of Brownian motion. Advances in Mathematics155, 317-343 (2000) · Zbl 0971.68077 |
| [38] | Fouch´e, W.: Dynamics of a generic Brownian motion: Recursive aspects. Theoretical Computer Science394, 175-186 (2008) · Zbl 1146.68038 |
| [39] | Fouch´e, W.L.: Fractals generated by algorithmically random Brownian motion.In: K. Ambos-Spies, B. L¨owe, W. Merkle (eds.) Mathematical Theory and Computational Practice,Lecture Notes in Computer Science, vol. 5635, pp. 208-217. Springer, Berlin (2009), 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, · Zbl 1268.03054 |
| [40] | Proceedings |
| [41] | Fouch´e, W.L.: Diophantine properties of Brownian motion: recursive aspects. In: V. Brattka, H. Diener, D. Spreen (eds.) Logic, Computation, Hierarchies,Ontos Mathematical Logic, vol. 4, pp. 139-156. De Gruyter, Boston (2014) · Zbl 1315.68160 |
| [42] | Fouch´e, W.L.: Kolmogorov complexity and the geometry of Brownian motion. Mathematical Structures in Computer Science25(7), 1590-1606 (2015) · Zbl 1361.68110 |
| [43] | Fouch´e, W.L., Mukeru, S., Davie, G.: Fourier spectra of measures associated with algorithmically random Brownian motion. Logical Methods in Computer Science10(3), 3:20, 24 (2014) · Zbl 1448.68251 |
| [44] | Franklin, J.N.Y., Greenberg, N., Miller, J.S., Ng, K.M.: Martin-L¨of random points satisfy Birkhoff’s ergodic theorem for effectively closed sets. Proceedings of the American Mathematical Society140(10), 3623-3628 (2012) · Zbl 1298.03103 |
| [45] | Franklin, J.N.Y., Towsner, H.: Randomness and non-ergodic systems. Moscow Mathematical Journal14(4), 711-744, 827 (2014) · Zbl 1335.03039 |
| [46] | Freer, C., Kjos-Hanssen, B., Nies, A., Stephan, F.: Algorithmic aspects of Lipschitz functions. Computability3(1), 45-61 (2014) · Zbl 1408.03031 |
| [47] | Freer, C.E., Roy, D.M.: Computable exchangeable sequences have computable de Finetti measures. In: K. Ambos-Spies, B. L¨owe, W. Merkle (eds.) Mathematical Theory and Computational Practice,Lecture Notes in Computer Science, vol. 5635, pp. 218-231. Springer, Berlin (2009) · Zbl 1233.03051 |
| [48] | Freer, C.E., Roy, D.M.: Computable de Finetti measures. Annals of Pure and Applied Logic 163(5), 530-546 (2012) · Zbl 1247.03098 |
| [49] | Friedman, H.: The computational complexity of maximization and integration. Advances in Mathematics53, 80-98 (1984) · Zbl 0563.03023 |
| [50] | G´acs, P.: Uniform test of algorithmic randomness over a general space. Theoretical Computer Science341, 91-137 (2005) · Zbl 1077.68038 |
| [51] | G´acs, P., Hoyrup, M., Rojas, C.: Randomness on computable probability spaces—a dynamical point of view. In: S. Albers, J.Y. Marion (eds.) STACS 2009: 26th International Symposium on Theoretical Aspects of Computer Science,LIPIcs. Leibniz Int. Proc. Inform., vol. 3, pp. 469-480. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2009) · Zbl 1236.68110 |
| [52] | G´acs, P., Hoyrup, M., Rojas, C.: Randomness on computable probability spaces—a dynamical point of view. Theory of Computing Systems48(3), 465-485 (2011) · Zbl 1238.68069 |
| [53] | Galatolo, S., Hoyrup, M., Rojas, C.: A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties. Theoretical Computer Science410, 2207-2222 (2009) · Zbl 1171.60002 |
| [54] | Galatolo, S., Hoyrup, M., Rojas, C.: Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems. In: X. Zheng, N. Zhong (eds.) Proceedings Seventh International Conference on Computability and Complexity in Analysis 2010,Electronic Proceedings in Theoretical Computer Science, vol. 24, pp. 7-18. Open Publishing Association (2010), Zhenjiang, China, 21-25th June 2010 · Zbl 1456.37004 |
| [55] | Galatolo, S., Hoyrup, M., Rojas, C.: Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Information and Computation208(1), 23-41 (2010) · Zbl 1185.68368 |
| [56] | Galatolo, S., Hoyrup, M., Rojas, C.: Dynamics and abstract computability: computing invariant measures. Discrete and Continuous Dynamical Systems. Series A29(1), 193-212 (2011) · Zbl 1217.37076 |
| [57] | Galatolo, S., Hoyrup, M., Rojas, C.: Statistical properties of dynamical systems—simulation and abstract computation. Chaos, Solitons and Fractals45(1), 1-14 (2012) · Zbl 1293.37001 |
| [58] | Hertling, P., Wang, Y.: Invariance properties of random sequences. Journal of Universal Computer Science3(11), 1241-1249 (1997) · Zbl 0969.60002 |
| [59] | Hertling, P., Weihrauch, K.: Randomness spaces. In: K.G. Larsen, S. Skyum, G. Winskel (eds.) Automata, Languages and Programming,Lecture Notes in Computer Science, vol. 1443, pp. 796-807. Springer, Berlin (1998), 25th International Colloquium, ICALP’98, Aalborg, Denmark, July 1998 · Zbl 0914.03054 |
| [60] | Hertling, P., Weihrauch, K.: Random elements in effective topological spaces with measure. Information and Computation181(1), 32-56 (2003) · Zbl 1055.68059 |
| [61] | Hochman, M.: Upcrossing inequalities for stationary sequences and applications. The Annals of Probability37(6), 2135-2149 (2009) · Zbl 1196.37014 |
| [62] | H¨olzl, R., Shafer, P.: Universality, optimality, and randomness deficiency. Annals of Pure and Applied Logic166(10), 1049-1069 (2015) · Zbl 1386.03047 |
| [63] | Hoyrup, M.: Randomness and the ergodic decomposition. In: B. L¨owe, D. Normann, I.N. Soskov, A.A. Soskova (eds.) Models of Computation in Context,Lecture Notes in Computer Science, vol. 6735, pp. 122-131. Springer, Heidelberg (2011) · Zbl 1259.03057 |
| [64] | Hoyrup, M.: The dimension of ergodic random sequences. In: C. D¨urr, T. Wilke (eds.) 29th International Symposium on Theoretical Aspects of Computer Science,LIPIcs. Leibniz Int. Proc. Inform., vol. 14, pp. 567-576. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2012) · Zbl 1254.03082 |
| [65] | Hoyrup, M.: Computability of the ergodic decomposition. Annals of Pure and Applied Logic 164(5), 542-549 (2013) · Zbl 1271.03063 |
| [66] | Hoyrup, M.: Irreversible computable functions. In: E.W. Mayr, N. Portier (eds.) 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014),Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 362-373. Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2014) · Zbl 1359.68072 |
| [67] | Hoyrup, M., Rojas, C.: An application of Martin-L¨of randomness to effective probability theory. In: K. Ambos-Spies, B. L¨owe, W. Merkle (eds.) Mathematical Theory and Computational Practice,Lecture Notes in Computer Science, vol. 5635, pp. 260-269. Springer, Berlin (2009) · Zbl 1268.03055 |
| [68] | Hoyrup, M., Rojas, C.: Applications of effective probability theory to Martin-L¨of randomness. In: S. Albers, A. Marchetti-Spaccamela, Y. Matias, S.E. Nikoletseas, W. Thomas (eds.) Automata, Languages and Programming. Part I,Lecture Notes in Comput. Sci., vol. 5555, pp. 549-561. Springer, Berlin (2009) · Zbl 1248.03066 |
| [69] | Hoyrup, M., Rojas, C.: Computability of probability measures and Martin-L¨of randomness over metric spaces. Information and Computation207(7), 830-847 (2009) · Zbl 1167.68023 |
| [70] | Hoyrup, M., Rojas, C., Weihrauch, K.: Computability of the Radon-Nikodym derivative. In: B. L¨owe, D. Normann, I. Soskov, A. Soskova (eds.) Models of Computation in Context, Lecture Notes in Computer Science, vol. 6735, pp. 132-141. Springer, Heidelberg (2011) · Zbl 1345.03084 |
| [71] | Hoyrup, M., Rojas, C., Weihrauch, K.: Computability of the Radon-Nikodym derivative. Computability1(1), 3-13 (2012) · Zbl 1277.03043 |
| [72] | Jafarikhah, T., Weihrauch, K.: The Riesz representation operator on the dual ofC[0; 1]is computable. Journal of Universal Computer Science19(6), 750-770 (2013) · Zbl 1412.03024 |
| [73] | Kakutani, S., Petersen, K.: The speed of convergence in the ergodic theorem. Monatshefte f¨ur Mathematik91(1), 11-18 (1981) · Zbl 0446.28015 |
| [74] | Kawamura, A.: Computational complexity in analysis and geometry. Ph.D. thesis. Department of Computer Science, University of Toronto (2011) |
| [75] | Kawamura, A., Cook, S.A.: Complexity theory for operators in analysis. ACM Transactions on Computation Theory4(2), 5:1-5:24 (2012) · Zbl 1322.68083 |
| [76] | Kjos-Hanssen, B.: Infinite subsets of random sets of integers. Mathematical Research Letters 16(1), 103-110 (2009) · Zbl 1179.03061 |
| [77] | Kjos-Hanssen, B.: The probability distribution as a computational resource for randomness testing. Journal of Logic and Analysis2, Paper 10, 13 (2010) · Zbl 1286.68251 |
| [78] | Kjos-Hanssen, B., Nerode, A.: The law of the iterated logarithm for algorithmically random Brownian motion. In: S.N. Artemov, A. Nerode (eds.) Logical Foundations of Computer Science,Lecture Notes in Computer Science, vol. 4514, pp. 310-317. Springer, Berlin (2007), Proceedings of the International Symposium (LFCS 2007) held at the City University of New York, New York, June 4-7, 2007 · Zbl 1133.68029 |
| [79] | Kjos-Hanssen, B., Nguyen, P.K.L.V., Rute, J.: Algorithmic randomness for Doob’s martingale convergence theorem in continuous time. Logical Methods in Computer Science 10(4:12), 1-35 (2014) · Zbl 1325.03051 |
| [80] | Ko, K.I.: Complexity Theory of Real Functions.Progress in Theoretical Computer Science. Birkh¨auser, Boston (1991) · Zbl 0791.03019 |
| [81] | van Lambalgen, M.: Random sequences. Ph.D. thesis. Department of Mathematics, University of Amsterdam (1987) · Zbl 0628.60001 |
| [82] | Levin, L.A.: Uniform tests of randomness. Soviet Math. Dokl.17(2), 337-340 (1976) · Zbl 0341.94013 |
| [83] | Li, M., Vit´anyi, P.: An Introduction to Kolmogorov Complexity and its Applications, 4th edn. Texts in Computer Science. Springer, Cham (2019) · Zbl 1423.68005 |
| [84] | Lu, H., Weihrauch, K.: Computable Riesz representation for the dual ofC[0; 1]. Mathematical Logic Quarterly53(4-5), 415-430 (2007) · Zbl 1128.03050 |
| [85] | Lu, H., Weihrauch, K.: Computable Riesz representation for locally compact Hausdorff spaces. Journal of Universal Computer Science14(6), 845-860 (2008) · Zbl 1227.03059 |
| [86] | Martin-L¨of, P.: The definition of random sequences. Information and Control9, 602-619 (1966) · Zbl 0244.62008 |
| [87] | Miyabe, K.: The difference between optimality and universality. Logic Journal of IGPL20, 222-234 (2011) · Zbl 1258.03052 |
| [88] | Miyabe, K.:L1-computability, layerwise computability and Solovay reducibility.Computability2(1), 15-29 (2013) · Zbl 1315.03073 |
| [89] | Miyabe, K.: Algorithmic randomness over general spaces. Mathematical Logic Quarterly 60(3), 184-204 (2014) · Zbl 1338.03084 |
| [90] | Miyabe, K., Nies, A., Zhang, J.: Using almost-everywhere theorems from analysis to study randomness. The Bulletin of Symbolic Logic22(3), 305-331 (2016) · Zbl 1401.03079 |
| [91] | Miyabe, K., Rute, J.: Van Lambalgen’s theorem for uniformly relative Schnorr and computable randomness. In: R. Downey, J. Brendle, R. Goldblatt, B. Kim (eds.) Proceedings of the 12th Asian Logic Conference, pp. 251-270. World Scientifc Publishing, Hackensack, NJ (2013), held in Wellington, December 15-20, 2011 · Zbl 1364.03062 |
| [92] | Moser, P.: On the convergence of Fourier series of computable Lebesgue integrable functions. In: R. Dillhage, T. Grubba, A. Sorbi, K. Weihrauch, N. Zhong (eds.) Proceedings of the Fourth International Conference on Computability and Complexity in Analysis (CCA 2007), Electronic Notes in Theoretical Computer Science, vol. 202, pp. 13-18. Elsevier (2008), CCA 2007, Siena, Italy, June 16-18, 2007 · Zbl 1262.42002 |
| [93] | M¨uller, N.T.: Computability on random variables. Theoretical Computer Science219(1-2), 287-299 (1999) · Zbl 0916.68041 |
| [94] | Nakamura, M.: Ergodic theorems for algorithmically random sequences. In: M.J. Dinneen, U. Speidel, D.P. Taylor (eds.) Proceedings of the IEEE ITSOC Information Theory Workshop 2005 on Coding and Complexity ITW 2005, pp. 147-150 (2005) |
| [95] | Nandakumar, S.: An effective ergodic theorem and some applications. In: STOC’08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 39-44. ACM, New York (2008) · Zbl 1231.37064 |
| [96] | Nies, A.: Computability and Randomness,Oxford Logic Guides, vol. 51. Oxford University Press, New York (2009) · Zbl 1169.03034 |
| [97] | Nies, A.: Differentiability of polynomial time computable functions.In: E.W. Mayr, N. Portier (eds.) 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014),Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 602-613. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2014) · Zbl 1359.03032 |
| [98] | Pathak, N., Rojas, C., Simpson, S.G.: Schnorr randomness and the Lebesgue differentiation theorem. Proceedings of the American Mathematical Society142(1), 335-349 (2014) · Zbl 1307.03027 |
| [99] | Phelps, R.R.: Lectures on Choquet’s Theorem, 2nd edn. Springer, Berlin, London (2001), previous ed.: Princeton, N.J. : Van Nostrand, 1966 · Zbl 0135.36203 |
| [100] | Pour-El, M.B., Richards, J.I.:Lp-computability in recursive analysis. Proceedings of the American Mathematical Society92, 93-97 (1984) · Zbl 0558.03030 |
| [101] | Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics.Perspectives in Mathematical Logic. Springer, Berlin (1989) · Zbl 0678.03027 |
| [102] | Rumyantsev, A., Shen, A.: Probabilistic constructions of computable objects and a computable version of Lov´asz Local Lemma. Fundamenta Informaticae132(1), 1-14 (2014) · Zbl 1317.68131 |
| [103] | Rute, J.: Computable randomness and betting for computable probability spaces. Mathematical Logic Quarterly62(4-5), 335-366 (2016) · Zbl 1364.03064 |
| [104] | Rute, J.: When does randomness come from randomness? Theoretical Computer Science 635, 35-50 (2016) · Zbl 1339.68127 |
| [105] | Rute, J.: Schnorr randomness for noncomputable measures. Information and Computation 258, 50-78 (2018) · Zbl 1453.03044 |
| [106] | ˇSanin, N.: Constructive Real Numbers and Constructive Function Spaces,Translations of Mathematical Monographs, vol. 21. American Mathematical Society, Providence (1968) · Zbl 0169.31101 |
| [107] | Schnorr, C.P.: Zuf¨alligkeit und Wahrscheinlichkeit,Lecture Notes in Mathematics, vol. 218. Springer, Berlin (1971) · Zbl 0232.60001 |
| [108] | Schr¨oder, M.: Admissible representations for probability measures. Mathematical Logic Quarterly53(4-5), 431-445 (2007) · Zbl 1124.03019 |
| [109] | Spitters, B.: A constructive view on ergodic theorems. The Journal of Symbolic Logic71(2), 611-623 (2006) · Zbl 1106.03052 |
| [110] | Takahashi, H.: On a definition of random sequences with respect to conditional probability. Information and Computation206, 1375-1382 (2008) · Zbl 1208.03046 |
| [111] | Takahashi, H.: Algorithmic randomness and monotone complexity on product space. Information and Computation209(2), 183-197 (2011) · Zbl 1215.68115 |
| [112] | Vovk, V.G.: The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences. Theory of Probability and Applications32, 413-425 (1987) · Zbl 0645.60006 |
| [113] | V’yugin, V.V.: Effective convergence in probability and an ergodic theorem for individual random sequences. SIAM Theory of Probability and Its Applications42(1), 39-50 (1997) · Zbl 0917.60039 |
| [114] | V’yugin, V.V.: Ergodic theorems for individual random sequences. Theoretical Computer Science207(4), 343-361 (1998) · Zbl 0915.68092 |
| [115] | V’yugin, V.V.: Non-robustness property of the individual ergodic theorem. Problems of Information Transmission37(2), 27-39 (2001) · Zbl 1012.37003 |
| [116] | Weihrauch, K.: Computability on the probability measures on the Borel sets of the unit interval. Theoretical Computer Science219, 421-437 (1999) · Zbl 0916.68043 |
| [117] | Weihrauch, K.: Computable Analysis. Springer, Berlin (2000) · Zbl 0956.68056 |
| [118] | Weihrauch, K.: On computable metric spaces Tietze-Urysohn extension is computable. In: J. Blanck, V. Brattka, P. Hertling (eds.) Computability and Complexity in Analysis,Lecture Notes in Computer Science, vol. 2064, pp. 357-368. Springer, Berlin (2001), 4th International Workshop, CCA 2000, Swansea, UK, September 2000 · Zbl 0985.03033 |
| [119] | Weihrauch, K.: Computability on measurable functions. Computability6(1), 79-104 (2017) · Zbl 1420.03115 |
| [120] | Weihrauch, K., Tavana-Roshandel, N.: Representations of measurable sets in computable measure theory. Logical Methods in Computer Science10, 3:7,21 (2014) · Zbl 1337.03068 |
| [121] | Wu, Y., Ding, D.: Computability of measurable sets via effective topologies. Archive for Mathematical Logic45(3), 365-379 (2006) · Zbl 1094.03049 |
| [122] | Wu, Y., Weihrauch, K.: A computable version of the Daniell-Stone theorem on integration and linear functionals. Theoretical Computer Science359(1-3), 28-42 (2006) · Zbl 1106.03042 |
| [123] | Zhong, N., Zhang, B.Y.:Lp-computability. Mathematical Logic Quarterly45(4), 449-456 (1999) · Zbl 0938.03091 |
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.
