Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-22T08:09:56.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Kolmogorov complexity and the geometry of Brownian motion

Published online by Cambridge University Press:  10 November 2014

WILLEM L. FOUCHÉ
WILLEM L. FOUCHÉ*
Affiliation:
Department of Decision Sciences, School of Economic Sciences, University of South Africa, PO Box 392, 0003 Pretoria, South Africa Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we continue the study of the geometry of Brownian motions which are encoded by Kolmogorov–Chaitin random reals (complex oscillations). We unfold Kolmogorov–Chaitin complexity in the context of Brownian motion and specifically to phenomena emerging from the random geometric patterns generated by a Brownian motion.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 25 , Special Issue 7: Computing with Infinite Data: Topological and Logical Foundations Part 1 , October 2015 , pp. 1590 - 1606
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Asarin, E. A. (1988) Individual random signals: An approach based on complexity, doctoral dissertation, Moscow State University.Google Scholar
Asarin, E. A. and Prokovskii, A. V. (1986) Use of the Kolmogorov complexity in analysing control system dynamics. Automation Remote Control 47 21–28. (Translated from: Primeenenie kolmogorovskoi slozhnosti k anlizu dinamiki upravlemykh sistem. Automatika i Telemekhanika (Automation Remote Control) 1 (1986) 25–33.)Google Scholar
Camia, F., Fontes, L. R. G. and Newman, C. M. (2005) The scaling limit geometry of near-critical 2D percolation, available at arXiv:cond-mat/0510740v1.Google Scholar
Chaitin, G. A. (1987) Algorithmic Information Theory, Cambridge University Press.Google Scholar
Davie, G. and Fouché, W. L. (2013) On the computability of a construction of Brownian motion. Mathematical Structures in Computer Science 23 1257–1265. doi:10.1017/S0960129513000157.Google Scholar
Fontes, L. R. G., Isopi, M., Newman, C. M. and Ravishankar, K. (2003) The Brownian web: Characterisation and convergence, available at arXiv:math.PR/0304119v1.Google Scholar
Fouché, W. L. (2000a) Arithmetical representations of Brownian motion I. Journal of Symbolic Logic 65 421–442.CrossRefGoogle Scholar
Fouché, W. L. (2000b) The descriptive complexity of Brownian motion. Advances in Mathematics 155 317–343.Google Scholar
Fouché, W. L. (2008) Dynamics of a generic Brownian motion: Recursive aspects. In: From Gödel to Einstein: Computability between Logic and Physics, Theoretical Computer Science 394 175–186.Google Scholar
Fouché, W. L. (2009) Fractals generated by algorithmically random Brownian motion. In: Ambos-Spies, K., Löwe, B. and Merkle, W. (eds.) CiE 2009, Lecture Notes in Computer Science 5635 208–217.Google Scholar
Gács, P. (2005) Uniform test of algorithmic randomness over a general space. Theoretical Computer Science 341 91–137.Google Scholar
Hinman, P. G. (1978) Recursion-Theoretic Hierarchies, Springer-Verlag, New York.Google Scholar
Hoyrup, M. and Rojas, C. (2009) Computability of probability measures and Martin-Löf randomness over metric spaces. Information and Computation 207 830–847.CrossRefGoogle Scholar
Kechris, A. S. (1999) New directions in descriptive set theory. Bulletin of Symbolic Logic 5 161–174.Google Scholar
Kjos-Hanssen, B. and Nerode, A. (2009) Effective dimension of points visited by Brownian motion. Theoretical Computer Science 410 347–354.Google Scholar
Kjos-Hanssen, B. and Szabados, T. (2011) Kolmogorov complexity and strong approximation of Brownian motion. Proceedings of the American Mathematical Society 139 3307–3316.Google Scholar
Manin, Y. I. (2010) A Course in Mathematical Logic for Mathematicians, Springer-Verlag.Google Scholar
Martin-Löf, P. (1966) The definition of random sequences. Information and Control 9 602–619.Google Scholar
Nies, A. (2008) Computability and Randomness, Oxford Logic Guides volume 51 Clarendon Press, Oxford.Google Scholar
Peres, Y. (2001) An Invitation to Sample Paths of Brownian Motion, available at www.stat.berkeley.edu/peres/bmall.pdf Google Scholar
Potgieter, P. (2012) The rapid points of a complex oscillation. Logical Methods in Computer Science 1 1–11.Google Scholar
Rudin, W. (1960) Fourier Analysis on Groups, Interscience Publishers, New York - London.Google Scholar
Tsirelson, B. (2004) Nonclassical stochastic flows and continuous products. Probability Surveys 1 173–298.CrossRefGoogle Scholar
Tsirelson, B. (2006) Brownian local minima, random dense countable sets and random equivalence classes. Electronic Journal of Probability 11 162–198.Google Scholar
Weihrauch, K (1999) Computability on the probability measures on the Borel sets of the unit interval. Theoretical Computer Science 219 421–437.Google Scholar
Weihrauch, K (2000) Computable Analysis, Springer, Berlin.Google Scholar