{"id":"60d56742-c013-4ba9-a576-25f50f0ce0e9","arxiv_id":"2501.00006","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"There exist computable parameters a for which the logistic map fa(x)=ax(1-x) has a unique physical (SRB) measure that is not Turing computable.","lead":"This paper constructs explicit choices of the logistic map parameter where the unique long-run statistical distribution of almost every orbit exists but cannot be computed by any algorithm. It shows that Monte Carlo style prediction can fail in principle even for the simplest non-linear dynamical systems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.3 only gives approximation at one time m_k; Theorem 3.4's convergence step claims the bound holds for all later times, which does not follow from the stated lemma.","rationale":"The paper's central claim is that there are computable parameters a for which the SRB measure exists and is non-computable. The proof constructs a as a nested intersection of intervals via Lemma 3.3, then argues that the empirical measures converge to the non-computable measure μ. The reader's weakest assumption focused on the effectiveness of the greedy search in Lemma 3.3, which is indeed a legitimate concern about the computability of a. However, I find a more direct and load-bearing gap in the final step: even granting Lemma 3.3 in full, the theorem's proof does not derive the needed uniformity in time. Lemma 3.3 only bounds the empirical measure at a single time m_k, not for all later times. The sentence in the proof of Theorem 3.4 stating that the bound holds for all m > m_l is unsupported. This is not a mere technicality; without an argument for full convergence of the empirical measures, the proof does not establish that μ is the physical measure, which is the core of the theorem. The gap is likely repairable by standard techniques (e.g., threshold times or fast-growing m_k), which is why I recommend CONDITIONAL rather than REJECT, but it must be addressed before the result can be considered rigorous. My concern is distinct from but related to the reader's, so agreement is partial.","tokens_in":10365,"tokens_out":21762,"duration_ms":202684,"concrete_test":"Verify whether Lemma 3.3 can be strengthened so that (3.1) holds for all m' ≥ m (a threshold statement), by checking whether the Johnson/Hofbauer–Keller construction from [Joh87, HK90] yields such a uniform-in-time bound. If the construction only gives a single-time estimate, then the proof of Theorem 3.4 must instead choose the inductive times m_k with m_k/m_{k+1}→0 and bound the contribution of intermediate blocks; check whether that argument is supplied anywhere in the paper.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The final step of Theorem 3.4 asserts that for every ε>0, |ν^m_a(x)(Pera(i)) − μ(Pera(i))| < ε holds for all m > m_l on a set of measure ≥1−ε. This is not a consequence of Lemma 3.3, whose conclusion (3.1) provides the bound only at the single time m (and similarly at each stage k only at m_k). From the lemma one obtains convergence of the empirical measures along the subsequence m_k, on a full-measure set; it does not control the full sequence, since the averages at intermediate times could deviate. A standard fix would require strengthening Lemma 3.3 to a threshold statement (3.1) for all m' ≥ m, or choosing the times m_k with m_k/m_{k+1}→0 and bounding the drift—neither of which is stated or proved. Without this, the construction does not establish that μ is the limiting statistical distribution of almost every orbit, and hence the central claim that μ is the (unique) physical/SRB measure is unsupported. This gap is independent of the effectivity of the greedy search flagged by the reader; it is a logical gap in the use of Lemma 3.3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10612,"tokens_out":5544,"duration_ms":54045,"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":[{"comment":"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.","section":"§3.2.2, Theorem 3.4"},{"comment":"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.","section":"§3.2.1, Lemma 3.3 proof"},{"comment":"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.","section":"§3.2.1, Lemma 3.3 statement"}],"minor_comments":[{"comment":"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.","section":"§1, Abstract and Introduction"},{"comment":"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.","section":"§3, Definition 3.1"},{"comment":"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.","section":"§3.2.2, Theorem 3.4 proof"},{"comment":"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.","section":"§3.2.2, Non-computability argument"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a topic of clear interest to the dynamical-systems and computable-analysis communities, and the overall strategy is plausible. However, the proof of the main theorem currently contains a logical gap in the convergence argument that is not merely cosmetic. The authors will need to either strengthen Lemma 3.3 to a tail-uniform statement or provide a separate argument controlling the empirical averages at intermediate times. The effectivity of the construction also needs to be made fully rigorous. Given that the central claim is likely salvageable with additional work, I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you my read on arXiv:2501.00006. The headline: the main theorem is a genuine strengthening of RY20 — computable parameter, non-computable SRB measure — and I think the result is probably true. But the proof as written has a real gap in the final convergence step and a computational lemma that is too sketched to verify.\n\nWhat's new and good: RY20 gave an uncountable set of parameters with non-computable physical measures, but not a single computable one. Here they produce a computable a by a nested interval construction that switches weights between periodic orbits as Turing machines halt. The encoding of the halting problem into the measure is clean, and the non-computability argument is standard. The use of Johnson's and Hofbauer-Keller's construction to realize those weights as the physical measure is the right tool.\n\nThe soft spots are in the execution. Lemma 3.3 is the load-bearing piece. The 'greedy search' for an admissible parabolic parameter is described in a few sentences: the parameter is found by enumerating algebraic conditions and verifying inequality (3.2). That's plausible, but the verification requires computing μ_ā(Per_r(n)) for parabolic maps, and it's not shown that this is uniformly computable in the needed precision. The 'standard exercise' for m and ε is also a black box. More seriously, the lemma only gives the estimate (3.1) at one time m. In Theorem 3.4, the proof asserts that for all m > m_l the bound holds on a large-measure set. That does not follow. You only have convergence along the subsequence m_k. Without an extra argument — e.g., strengthening the lemma to all times beyond m, or choosing m_k with m_k/m_{k+1}->0 and controlling the drift — the claim that μ is the limiting distribution for almost every orbit is unsupported. This is a genuine logical gap, independent of the effectivity questions.\n\nThat said, I don't think the gaps are fatal. The construction is concrete enough that a skilled reader could fill them. The result, if fixed, is significant: it shows Monte Carlo fails for a computable logistic map. The paper cites prior work honestly, including its own STOC paper as context; no circularity.\n\nWho should read it: people in computational dynamics and computable analysis. It deserves peer review, but the referee should demand a rewritten Lemma 3.3 and a resolution of the subsequence-to-full-sequence issue. I wouldn't cite it in its current form.\n\nRecommendation: send it out for review, but expect major revision.","headline":"A genuinely stronger result than RY20, but the proof has a real convergence gap and a too-sketchy Lemma 3.3.","tokens_in":11109,"tokens_out":4111,"would_cite":false,"duration_ms":39370,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","37E05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["non-computability","unimodal maps","physical measures","SRB measures","Monte Carlo method","logistic map","Halting Problem","computable analysis"],"falsifier":"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.","tokens_in":10174,"feed_emoji":"🎲","tokens_out":12789,"duration_ms":112702,"temperature":0.7,"pith_summary":"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.","feed_headline":"Computable logistic-map parameters can hide non-computable statistics","feed_subtitle":"The paper constructs such a parameter, making the map's unique physical measure exactly as hard to compute as the Halting Problem.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the refined Johnson-type construction (Theorem 1 therein) that Lemma 3.3 makes computable; without it the parameter-tuning step has no basis.","marker":"[HK90]"},{"why":"Original construction of quadratic maps whose asymptotic measures are prescribed on periodic orbits; the starting point of the method.","marker":"[Joh87]"},{"why":"Earlier non-constructive proof that non-computable physical measures exist in the quadratic family; the present paper strengthens it to computable parameters.","marker":"[RY20]"},{"why":"Defines computable real numbers and the Halting Problem; the non-computability argument measures the physical measure against this standard.","marker":"[Tur36]"},{"why":"Provides the one-dimensional dynamics facts (Proposition 3.1 on physical measures and 3.2 on the full-shift coding) used throughout.","marker":"[dMvS93]"},{"why":"Cited for the condition-number estimate used in Lemma 3.3 to produce the integer m and error bound epsilon.","marker":"[BCSS98]"}],"fun_headline_variants":["Computable parameters, non-computable SRB measures in logistic maps","Even computable logistic maps can hide non-computable statistics","Halting Problem embedded in a logistic map's physical measure","Constructive proof: computable parameter gives non-computable statistical law"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Computable parameters, non-computable SRB measures in logistic maps","Even computable logistic maps can hide non-computable statistics","Halting Problem embedded in a logistic map's physical measure","Constructive proof: computable parameter gives non-computable statistical law"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1498,"prompt_tokens":882,"completion_tokens":616,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":542}},"tokens_in":498,"tokens_out":616,"duration_ms":6175,"temperature":1.0,"reasoning_tokens":542,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:37:42.829436+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}