How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non-computable
Authors:
Open Access
- 22 June 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 297, 1066-1072
Abstract
We consider the simplest non-linear discrete dynamical systems, given by the logistic maps f a (x)=ax(1−x) of the interval [0,1]. We show that there exist real parameters a∈ (0,4) for which almost every orbit of f a has the same statistical distribution in [0,1], but this limiting distribution is not Turing computable. In particular, the Monte Carlo method cannot be applied to study these dynamical systems.Keywords
All Related Versions
Funding Information
- Horizon 2020 (731143)
- Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada
- Fondo Nacional de Desarrollo Científico y Tecnológico (1190493)
This publication has 13 references indexed in Scilit:
- Space-Bounded Church-Turing Thesis and Computational Tractability of Closed SystemsPhysical Review Letters, 2015
- A Rigorous ODE Solver and Smale’s 14th ProblemFoundations of Computational Mathematics, 2002
- On topological dynamics of Turing machinesTheoretical Computer Science, 1997
- Computability with low-dimensional dynamical systemsTheoretical Computer Science, 1994
- One-Dimensional Dynamics1993
- Generalized shifts: unpredictability and undecidability in dynamical systemsNonlinearity, 1991
- Quadratic maps without asymptotic measureCommunications in Mathematical Physics, 1990
- Singular measures without restrictive intervalsCommunications in Mathematical Physics, 1987
- Diffeomorphisms with infinitely many sinksTopology, 1974
- The Monte Carlo MethodJournal of the American Statistical Association, 1949