Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Ulam meets Turing: constructing quadratic maps with non-computable SRB measures

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read There are computable numbers a in (2,4) for which the logistic map has a unique physical measure that is not Turing computable; computing it is equivalent to solving the Halting Problem.

desk verdict A genuinely stronger result than RY20, but the proof has a real convergence gap and a too-sketchy Lemma 3.3. read the letter →

arxiv 2501.00006 v1 pith:S6QDVMDU submitted 2024-11-26 math.DS

Cristóbal Rojas , Michael Yampolsky This is my paper · ORCID
classification math.DS MSC 68Q1737E05
keywords non-computabilityunimodalmapsphysicalmeasuresSRBMonteCarlomethodlogisticmapHaltingProblemcomputableanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that a completely ordinary-looking logistic map $f_a(x)=a x(1-x)$ with a computable parameter $a\in(2,4)$ can have a unique statistical equilibrium (a physical or SRB measure) that is not Turing computable. This undercuts the usual justification of the Monte Carlo method: the limiting distribution exists, has a full-measure basin, and yet no algorithm can approximate its values. The construction proves something sharper: the measure's mass on a countable family of periodic orbits encodes the halting behavior of every Turing machine, so computing the measure is exactly as hard as solving the Halting Problem. The argument works by tuning the parameter through a nested sequence of parabolic parameters, reprogramming the measure's weights at each stage as machines halt, and the exponential shrink makes the final parameter computable while the measure remains non-computable.

What carries the argument

The engine is Lemma 3.3, a computable refinement of Johnson's construction: given an 'admissible' parabolic parameter (a parabolic periodic point with an interval diffeomorphically mapped over the whole dynamical interval) and any uniformly computable positive sequence of weights summing to 1, one can algorithmically find an arbitrarily close admissible parameter such that, for all initial points in a set of measure at least $1-2^{-k}$, the finite-time empirical averages over the first $N$ periodic orbits match the prescribed weights to within $2^{-k}$. This lemma converts a small move in the parameter space into a controlled reallocation of the physical measure's statistical weight. The second piece is the nested-induction scheme: at stage $k$, the parameter interval is halved and the weight of one pair of periodic orbits is switched from the 'non-halting' to the 'halting' member whenever a new machine halts. The intersection of the intervals is a computable number because the intervals shrink exponentially, and the measure it defines is exactly the halting-encoded measure, whose non-computability follows from the undecidability of the Halting Problem.

What would settle it

Try to compute the parameter promised by Lemma 3.3 for the weight sequence $l_n=2^{-n}$ starting from a fixed admissible parabolic parameter, implementing the greedy search exactly as described in the proof. If the search does not halt for some $k$, or returns no parameter within $\delta$, the claimed effectivity of the construction, and hence the computability of the final parameter $a$, fails.

Watch

Extended reading notes

Core claim

The paper's central claim is constructive: it produces computable numbers $a$ for which the logistic map $f_a$ has a unique physical measure $\mu_a$ whose basin has full Lebesgue measure in $[0,1]$, yet $\mu_a$ is not Turing computable. In the proof, the measure $\mu_a$ is supported on a countable collection of periodic orbits $\mathrm{Per}(n)$ (a fixed enumeration), and its mass on the pair $\mathrm{Per}(2n)\cup\mathrm{Per}(2n-1)$ is $2^{-n}$, split between the two orbits according to whether the $n$-th Turing machine halts. If $\mu_a$ were computable, one could compute upper bounds for these masses from below and compare them with $2^{-n}$, thereby solving the Halting Problem; hence the measure is non-computable. The parameter $a$ itself is the intersection of a nested sequence of intervals produced by a computable version of Johnson's construction (Lemma 3.3), so $a$ is a computable real even though the associated statistical law is not.

Load-bearing premise

The load-bearing premise is that the greedy search in Lemma 3.3 is fully effective: given an admissible parabolic parameter and a computable weight sequence, a terminating algorithm can find the nearby admissible parameter and error bounds; if this search is not algorithmic, the constructed limit parameter $a$ may not be computable.

Editorial extensions

If this is right

  • There is no general algorithm that, given a computable logistic map, outputs its physical measure to arbitrary precision, even when that measure exists, is unique, and attracts Lebesgue-almost every orbit.
  • The Monte Carlo method, applied to the constructed maps as black boxes, cannot converge to the true limiting distribution in any computable sense, because the distribution itself is not computable.
  • For the quadratic family, statistical prediction can be computationally harder than topological prediction: the paper cites its earlier result that every quadratic map has a computable topological attractor, while here the physical measure can be non-computable.
  • The construction yields, for any effective enumeration of Turing machines, a computable parameter whose physical measure's masses on the periodic-orbit family encode the Halting Problem; thus the measure's computational complexity is exactly that of the Halting Problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The parameter-tuning coding is likely flexible enough to realize measures whose weights on the periodic-orbit family have arbitrary prescribed Turing degrees, so one could build logistic maps whose statistics sit at any level of the arithmetical hierarchy.
  • The same technique should transfer to other one-parameter families that contain a full-shift horseshoe (e.g., higher-dimensional quadratic or Hénon-type maps); if so, non-computable physical measures could become generic rather than isolated examples, a question the paper leaves open.
  • A practical corollary the paper does not spell out: for these maps, any finite Monte Carlo run carries no reliable error estimate, since the rate of convergence to the limiting measure is effectively unknowable when the limit is non-computable.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper claims to construct computable parameters a in (0,4) for which the logistic map f_a(x)=ax(1-x) has a unique physical (SRB) measure that is not Turing computable. The construction uses a nested interval argument based on an effective version of Johnson's construction, as developed by Hofbauer and Keller, to arrange that the empirical statistics of almost every orbit approximate a measure encoding the Halting Problem. The authors also argue that the limiting measure is non-computable because its values on certain periodic orbits would decide the Halting Problem.

Significance. If correct, the result is significant: it shows that Monte Carlo simulation, or any numerical scheme, can provably fail to approximate the asymptotic statistical behavior of a very simple computable dynamical system, even when a unique physical measure exists. The construction is also an improvement over the authors' previous non-constructive work, since the parameter a is claimed to be computable. The paper connects computable analysis with one-dimensional dynamics in a novel way. However, the proof as written contains a load-bearing gap in the passage from convergence along a subsequence of times to convergence for all large times, as well as an insufficiently justified effectivity claim in Lemma 3.3.

major comments (3)
  1. [§3.2.2, Theorem 3.4] The convergence step is not justified. Lemma 3.3 provides the bound (3.1) only at a single time m (and at each stage k only at m_k). The proof of Theorem 3.4 then asserts that for every ε>0, |ν^m_a(x)(Per_a(i)) − μ(Per_a(i))| < ε for all m > m_l on a set of measure at least 1−ε. This does not follow from the lemma, because the empirical averages at times between m_k and m_{k+1} could in principle deviate arbitrarily from the target measure. To establish that μ is the physical measure, one needs either a strengthened version of Lemma 3.3 giving a bound for all m' ≥ m, or an additional argument controlling the drift of the empirical averages between the chosen times. Without this, the construction only proves convergence along the subsequence m_k on a full-measure set, which does not imply that μ is the limiting statistical distribution of almost every orbit.
  2. [§3.2.1, Lemma 3.3 proof] The effectivity of Lemma 3.3 is asserted rather than proved. The sentence 'Note that such a parameter can be found by a greedy search' relies on the claim that parabolic parameters and the endpoints of the interval J are specified by algebraic conditions, but the endpoints of J are not shown to be algebraic, and the search is not explicitly defined. The subsequent 'standard exercise on estimating the condition number' that produces m and ε is also not carried out. Since the computability of the final parameter a in Theorem 3.4 depends on being able to effectively compute these objects with the required precision, this gap is load-bearing. A rigorous proof must specify algorithms with explicit termination criteria and error bounds.
  3. [§3.2.1, Lemma 3.3 statement] The lemma states a bound (3.1) for all n ∈ N, but the proof only discusses n ≤ N, where N is chosen so that the total weight of the tail is small. For n > N, the target weight l_n is small, but the empirical measure ν^m_r(x)(Per_r(n)) is not automatically small; the orbit at time m could have spent a significant fraction of time near the corresponding periodic orbit. The proof gives no argument controlling the tail of the empirical measure. A complete proof must either show that the tail mass is uniformly small or modify the statement to only require the bound for n ≤ N, and then handle the tail separately in the application.
minor comments (4)
  1. [§1, Abstract and Introduction] There are several typographical issues, including 'asymptotical' for 'asymptotic' and 'ga(0, 5)' for 'ga(0.5)'. The notation for the empirical measure is inconsistent: the text sometimes uses ν^n_a(x) and sometimes ν^m_r(x) without a clear distinction. Please standardize.
  2. [§3, Definition 3.1] In Definition 3.1, the phrase 'a is parabolic, that is, there exists p ... Df^j_a(p) = 1' should clarify whether j is the period of p and whether the derivative condition is meant to be exactly +1 (as written) or possibly |Df^j_a(p)| = 1. The current wording is ambiguous.
  3. [§3.2.2, Theorem 3.4 proof] The definition of n_l is confusing: the sentence 'Let M_{n_l} be the last machine that halts among the first n machines' uses n both as the index bound and in the subscript; later the text switches to 'for all k > l' without clearly relating l to n_l. Please define l explicitly and distinguish the fixed n from the stage index.
  4. [§3.2.2, Non-computability argument] The argument that a computable measure would allow deciding the Halting Problem is correct in spirit, but it should spell out that the functions φ_l are uniformly computable from the periodic orbit data and that the comparison with 2^{−n} uses the dichotomy μ(Per(2n)) ∈ {0, 2^{−n}}. As written, the step 'by comparing them against 2^{−n}' is terse.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the construction is driven by external results from Johnson and Hofbauer–Keller, and the authors' self-citations are contextual only.

full rationale

The paper's central claim is a construction: given a target measure µ defined from the Halting Problem, it builds a computable parameter a and shows that fa has µ as its unique physical measure. The measure is not defined in terms of the map, nor is the map's behavior fitted to a subset of data and then renamed a prediction; Lemma 3.3 is an explicit construction lemma whose proof cites the independent external works [Joh87] and [HK90]. The only self-citations ([RY20], [RY19], and [BBRY11] in the introduction) are historical or motivational and are not load-bearing: the main proof does not rely on a uniqueness theorem or ansatz imported from the authors' prior work. The uniqueness of the physical measure in Proposition 3.1 is cited to the external textbook [dMvS93], not to the authors. The reader-flagged concern about the final convergence step is a potential mathematical gap (the lemma gives approximation at selected times m_k while the theorem asserts control for all sufficiently large m), but a gap in the proof is not circularity: no equation is equivalent to its own input by construction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new entities; it constructs a probability measure encoding the halting problem and uses an existing dynamical construction. The central claim rests on prior theorems in one-dimensional dynamics and on the effectiveness of a search over parabolic parameters.

assumptions (4)
  • domain assumption Johnson/Hofbauer-Keller existence: for any admissible parabolic parameter and any finite set of weights, there exists a nearby admissible parameter whose finite-time empirical averages approximate those weights.
    Invoked in Lemma 3.3 via [Joh87, HK90]; the paper does not reprove this deep one-dimensional dynamics result.
  • domain assumption Parabolic parameters are effectively searchable because they are specified by algebraic conditions and their periodic orbits are algebraic functions of the parameter.
    Used in the greedy search argument in Lemma 3.3 to claim termination and verifiability.
  • standard math Standard theorems of one-dimensional dynamics: unique physical measure when a non-repelling periodic orbit exists (Proposition 3.1) and symbolic dynamics of the quadratic family from de Melo-van Strien.
    Background facts used throughout the proof.
  • standard math Borel-Cantelli lemma and classical undecidability of the Halting Problem.
    Used to pass from stage-wise approximations to almost everywhere convergence and to prove non-computability.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ulam meets Turing: constructing quadratic maps with non-computable SRB measures." pith.science (2026). https://pith.science/paper/S6QDVMDU

@misc{pith2026250100006,
  author       = {Pith},
  title        = {Pith review of: Ulam meets Turing: constructing quadratic maps with non-computable SRB measures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S6QDVMDU}},
  note         = {Machine review of arXiv:2501.00006}
}
abstract

In 1946, S. Ulam invented Monte Carlo method, which has since become the standard numerical technique for making statistical predictions for long-term behaviour of dynamical systems. We show that this, or in fact any other numerical approach can fail for the simplest non-linear discrete dynamical systems given by the logistic maps $f_{a}(x)=ax(1-x)$ of the unit interval. We show that there exist computable real parameters $a\in (0,4)$ for which almost every orbit of $f_a$ has the same asymptotical statistical distribution in $[0,1]$, but this limiting distribution is not Turing computable.

Figures

Figures reproduced from arXiv: 2501.00006 by the authors.

Figure 1
Figure 1. Some iterates of f ≡ fa for a ∈ (c, 4] restricted to the appropriate intervals (we drop the subscript a for simplicity in all notations in the figure). In particular, every periodic sequence of 0’s and 1’s corresponds to a unique periodic orbit in Ca with this symbolic dynamics. These orbits clearly move con￾tinuously with a, and can be easily computed given a and the symbolic sequence as the unique fixed points of … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Computable Ergodic Optimisation

    math.DS 2026-07 accept novelty 6.5 of 10

    Under computable compactness and overtness of invariant measures, the max ergodic average of a computable potential is computable and maximising measures form a Π1 set; for finite-range SFT potentials an explicit max-...

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · cited by 1 Pith paper

  1. [1]

    On Emergence and Complexity of Ergodic Decompositions

    P. Berger and J. Bochi. On emergence and complexity of ergodic decompositions. ar X iv preprint math/1901.03300 , 2019

    work page Pith review arXiv 1901

  2. [2]

    Binder, M

    I. Binder, M. Braverman, C. Rojas, and M. Yampolsky. Computability of B rolin- L yubich measure. Commun. Math. Phys. , 308:743--771, 2011

    work page 2011

  3. [3]

    L. Blum, F. Cucker, M. Shub, and S. Smale. The condition number for nonlinear problems. In Complexity and Real Computation , pages 217--236. Springer New York, New York, NY, 1998

    work page 1998

  4. [4]

    P. Berger. Unpredictability of dynamical systems and non-typicality of the finiteness of the number of attractors in various topologies. Tr. Mat. Inst. Steklova , 297:7--37, 2017. English version published in Proc. Steklov Inst. Math. 297 (2017), no. 1, 1--27

    work page 2017

  5. [5]

    Braverman, A

    M. Braverman, A. Grigo, and C. Rojas. Noise vs computational intractability in dynamics. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference , ITCS '12, pages 128--141, New York, NY, USA, 2012. ACM

    work page 2012

  6. [6]

    Banach and S

    S. Banach and S. Mazur. Sur les fonctions caluclables. Ann. Polon. Math. , 16, 1937

    work page 1937

  7. [7]

    Braverman, C

    M. Braverman, C. Rojas, and J. Schneider. Space-bounded C hurch- T uring thesis and computational tractability of closed systems. Physical Review Letters , 115(9), August 2015

    work page 2015

  8. [8]

    Burr, M.; Schmoll and C

    M. Burr, M.; Schmoll and C. Wolf. On the computability of rotation sets and their entropies. Ergodic Theory and Dynamical Systems , pages 1--35, 2018

    work page 2018

Show all 33 references
  1. [9]

    Braverman and M

    M. Braverman and M. Yampolsky. Computability of J ulia sets , volume 23 of Algorithms and C omputation in M athematics . Springer, 2008

    2008

  2. [10]

    de M elo and S

    W. de M elo and S. van Strien . One-dimensional dynamics . Springer- V erlag, 1993

    1993

  3. [11]

    Galatolo, M

    S. Galatolo, M. Hoyrup, and C. Rojas. Dynamics and abstract computability: computing invariant measures. Discr. Cont. Dyn. Sys. Ser A , 2010

    2010

  4. [12]

    G \'a cs, P.; Hoyrup and C

    M. G \'a cs, P.; Hoyrup and C. Rojas. Randomness on computable probability spaces -- a dynamical point of view. Theory Comput. Syst. , 48(465), 2011

    2011

  5. [13]

    Characterisation of sets of limit measures after iteration of a cellular automaton on an initial measure

    Benjamin Hellouin de Menibus and Mathieu Sablik. Characterisation of sets of limit measures after iteration of a cellular automaton on an initial measure. Ergodic Theory and Dynamical Systems , 38(2):601--650, 2016

    2016

  6. [14]

    Hofbauer and G

    F. Hofbauer and G. Keller. Quadratic maps without asymptotic measure. Comm. M ath. P hys. , 127:319--337, 1990

    1990

  7. [15]

    Hochman and T

    M. Hochman and T. Meyerovitch. Characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics , 171(3):2011--2038, 2010

    2011

  8. [16]

    E. Jeandel. Computability of the entropy of one-tape T uring machines. In 31st I nternational S ymposium on T heoretical A spects of C omputer S cience (STACS) , volume 25 of LIPIcs. Leibniz Int. Proc. Inform. , pages 421--432. 2014

    2014

  9. [17]

    S. Johnson. Singular measures without restrictive intervals. Commun. M ath. P hys. , 110:185--190, 1987

    1987

  10. [18]

    Koiran, M

    P. Koiran, M. Cosnard, and M. Garzon. Computability with low-dimensional dynamical systems. Theoret. Comput. Sci. , 132(1-2):113--128, 1994

    1994

  11. [19]

    Average-case polynomial-time computability of H amiltonian dynamics

    Akitoshi Kawamura, Holger Thies, and Martin Ziegler. Average-case polynomial-time computability of H amiltonian dynamics. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK , pages 30:1--30:17, 2018

    2018

  12. [20]

    On topological dynamics of T uring machines

    Petr Kurka. On topological dynamics of T uring machines. Theoret. Comput. Sci. , 174:203--2016, 1997

    2016

  13. [21]

    E. N. Lorenz. Deterministic nonperiodic flow. J. Atmos. Sci. , 20:130--141, 1963

    1963

  14. [22]

    S. Mazur. Computable A nalysis , volume 33. Rosprawy Matematyczne, Warsaw, 1963

    1963

  15. [23]

    Metropolis

    N. Metropolis. The beginning of the M onte C arlo method. Los A lamos S cience S pecial I ssue , pages 125--130, 1987

    1987

  16. [24]

    Moore and P

    C. Moore and P. Koiran. Closed-form analytic maps in one and two dimensions can simulate universal T uring machines. Theoret. Comput. Sci. , 210(1):2217--223, 1999

    1999

  17. [25]

    C. Moore. Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity , 4(2):199--230, 1991

    1991

  18. [26]

    Metropolis and Ulam

    N. Metropolis and Ulam. S. The M onte C arlo method. Journal of the A merican S tatistical A ssociation , 44:335--341, 1949

    1949

  19. [27]

    Newhouse

    S. Newhouse. Diffeomorphisms with infinitely many sinks. Topology , 13:9--18, 1974

    1974

  20. [28]

    C. Rojas. Randomness and ergodic theory: an algorithmic point of view . PhD thesis, Ecole Polytechnique, 2008

    2008

  21. [29]

    Computational intractability of attractors in the real quadratic family

    Cristobal Rojas and Michael Yampolsky. Computational intractability of attractors in the real quadratic family. Advances in Mathematics , 349:941 -- 958, 2019

    2019

  22. [30]

    Rojas and M

    C. Rojas and M. Yampolsky. How to lose at M onte C arlo: a simple dynamical system whose typical statistical behavior is non-computable. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , 2020

    2020

  23. [31]

    W. Tucker. A rigorous O D E solver and S male's 14th problem. Found. Comp. Math. , 2:53--117, 2002

    2002

  24. [32]

    A. M. Turing. On computable numbers, with an application to the E ntscheidungsproblem. Proceedings, London Mathematical Society , pages 230--265, 1936

    1936

  25. [33]

    Ulam, R.D

    S. Ulam, R.D. Richtmyer, and J. von Neumann. Statistical methods in neutron diffusion. Los A lamos S cientific L aboratory report L A M S 551 , 1947

    1947

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.