Abstract
We investigate notions of randomness in the space \({{\mathcal C}(2^{\mathbb N})}\) of continuous functions on \({2^{\mathbb N}}\). A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random \({\Delta^0_2}\) continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any \({y \in 2^{\mathbb N}}\), there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Asarin, E.A., Prokovskiy, V.: Application of Kolmogorov complexity to the dynamics of controllable systems. Automat. Telemekh. 1, 25–53 (1986)
Brodhead, P., Cenzer, D., Dashti, S.: Random closed sets. In: Beckmann, A., Berger, U., Löwe, B., Tucker, J.V. (eds.) Logical Approaches to Computational Barriers. Springer Lecture Notes in Computer Science 3988, pp. 55–64 (2006)
Barmpalias, G., Brodhead, P., Cenzer, D., Dashti, S., Weber, R.: Algorithmic randomness of closed sets. J. Logic Comput. (2007) (to appear)
Cenzer, D.: \({\Pi^0_1}\) Classes, ASL Lecture Notes in Logic (2007) (to appear)
Cenzer, D., Remmel, J.B.: \({\Pi^0_1}\) classes. In: Ersov, Y., Goncharov, S., Marek, V., Nerode, A., Remmel, J. (eds.) Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics. Elsevier Studies in Logic and the Foundations of Mathematics, vol. 139, pp. 623–821 (1998)
Chaitin, G.: Information-theoretical characterizations of recursive infinite strings. Theor. Comp. Sci. 2, 45–48 (1976)
Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity (in preparation). Current draft available at http://www.mcs.vuw.ac.nz/~downey/
Fouche, W.: Arithmetical representations of Brownian motion. J. Symbolic Logic 65, 421–442 (2000)
Gács, P.: On the symmetry of algorithmic information. Soviet Mat. Dokl. 15, 1477–1480 (1974)
Kolmogorov, A.N.: Three approaches to the quantitative defintion of information. Problems Inform. Trans. 1, 1–7 (1965)
Levin, L.: On the notion of a random sequence. Soviet Mat. Dokl. 14, 1413–1416 (1973)
Martin-Löf, P.: The definition of random sequences. Inform. Control 9, 602–619 (1966)
Schnorr, C.P.: A unified approach to the definition of random sequences. Math. Syst. Theory 5, 246–258 (1971)
van Lambalgen, M.: Random Sequences. Ph.D. Dissertation, University of Amsterdam (1987)
Ville, J.: Étude Critique de la Notion de Collectif. Gauthier-Villars, Paris (1939)
von Mises, R.: Grundlagen der Wahrscheinlichkeitsrechnung. Math. Zeitschrift 5, 52–99 (1919)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.
Rights and permissions
About this article
Cite this article
Barmpalias, G., Brodhead, P., Cenzer, D. et al. Algorithmic randomness of continuous functions. Arch. Math. Logic 46, 533–546 (2008). https://doi.org/10.1007/s00153-007-0060-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-007-0060-4