Abstract
Abstract. V'yugin [2, 3] has shown that there are a computable shift-invariant measure on 2 N and a simple function f such that there is no computable bound on the rate of convergence of the ergodic averages Anf . Here it is shown that in fact one can construct an example with the property that there is no computable bound on the complexity of the limit; that is, there is no computable bound on how complex a simple function needs to be to approximate the limit to within a given ε.
Let 2
N denote Cantor space, the space of functions from N to the discrete space {0, 1} under the product topology. Viewing elements of this space as infinite sequences, for any finite sequence σ of 0's and 1's let [σ] denote the set of elements of 2 N that extend σ. The collection B of Borel sets in the standard topology are generated by the set of such [σ] . For each k, let B k denote the finite σ-algebra generated by the partition {[σ] | length(σ) = k}. If a function f from 2 N to Q is measurable with respect to B k , I will call it a simple function with complexity at most k.
Let µ be any probability measure on (2 N , B), and let f be any element of L 1 (µ). Say that a function k from Q + to N is a bound on the complexity of f if, for every ε > 0, there is a simple function g of complexity at most k(ε) such that f − g < ε.
If (f n ) is any convergent sequence of elements of L 1 (µ) with limit f , say that r(ε) is a bound on the rate of convergence of (f n ) if for every n ≥ r(ε), f n − f < ε. (One can also consider rates of convergence in any of the L p norms for 1 < p < ∞, or in measure. Since all the sequences considered below are uniformly bounded, this does not affect the results below.) Now suppose that µ is a computable measure on 2 N in the sense of computable measure theory [1, 4] . Then if f is any computable element of L 1 (µ), there is a computable sequence (f n ) of simple functions that approaches f with a computable rate of convergence r(ε); this is essentially what it means to be a computable element of L 1 (µ). In particular, setting k(ε) equal to the complexity of f r(ε) provides a computable bound on the complexity of f . But the converse need not hold: if r is any noncomputable real number and f is the constant function with value r, then f is not computable even though there is a trivial bound on its complexity.
It is not hard to compute a sequence of simple functions (f n ) that converges to a function f even in the L ∞ norm with the property that there is no computable bound on the complexity of the limit, with respect to the standard coin-flipping measure on 2 N . Notice that this is stronger than saying that there is no computable bound on the rate of convergence of (f n ) to f ; it says that there is no way of 2010 Mathematics Subject Classification. 03F60, 37A25. Work partially supported by NSF grant DMS-1068829. I am grateful to an anonymous referee for comments and suggestions.
computing bounds on the complexity of any sequence of good approximations to f .
To describe such a sequence, for each k, let h k be the B k -measurable Rademacher function defined by
where σ k−1 denotes the last bit of σ and 1 [σ] denotes the characteristic function of the cylinder set [σ] . Intuitively, h k is a "noisy" function of complexity k. Finally, let f n = i≤n 4 −ϕ(i) h i , where ϕ is an injective enumeration of any computably enumerable set, like the halting problem, that is not computable. Given any m, if n is large enough so that ϕ(j) > m whenever j > n, then for every i > n and every x we have
At the same time, it is not hard to verify that if f is the L 1 limit of this sequence and g is a simple function of complexity at at most n such that µ({x | |g(
, then m is in the range of ϕ if and only if ϕ(j) = n for some j < n. Thus one can compute the range of ϕ from any bound on the complexity of f .
The sequence (f n ) just constructed is contrived, and one can ask whether similar sequences arise "in nature." Letting A n f denote the ergodic average 1 n i<n f • T n , the mean ergodic theorem implies that for every measure µ on 2 N and f in L 1 (µ), the sequence (A n f ) converges in the L 1 norm. However, V'yugin [2, 3] has shown that there is a computable shift-invariant measure µ on Cantor space such that there is no computable bound on the rate of convergence of (A n 1 [1] ). In V'yugin's construction, the limit doesn't have the property described in the last paragraph; in fact, it is very easy to bound the complexity of the limit in question, which places a noncomputable mass on the string of 0's and the string of 1's, and is otherwise homogeneous. The next theorem shows, however, that there are computable measures µ such that the limit does have this stronger property.
Theorem. There is a computable shift-invariant measure µ on 2 N such that if f = lim n A n 1 [1] , the halting problem can be computed from any bound on the complexity of f .
Proof. If σ is any finite binary sequence, let σ * denote the element σσσ . . . of Cantor space. For each e, define a measure µ e as follows: if Turing machine e halts in s steps, let µ e put mass uniformly on these 8s elements:
• all 4s shifts of (1 s 0 3s ) *
• all 4s shifts of (1 3s 0 s ) * Otherwise, let µ e divide mass uniformly between 0 * and 1 * . Each measure µ e is shift invariant, by construction. I will show, first, that µ e is computable uniformly in e, which is to say, there is a single algorithm that, given e, σ, and ε > 0, computes µ e ([σ]) to with ε. I will then show that information as to the complexity needed to approximate f in (2 ω , B, µ e ) allows one to determine whether or not Turing machine e halts. The desired conclusion is then obtained by defining µ = e 2 −(e+1) µ e . If Turing machine e does not halt, µ e ([σ]) = 1/2 if σ is a string of 0's or a string of 1's, and µ e ([σ]) = 0 otherwise. Suppose, on the other hand, that Turing machine e halts in s steps, and suppose k < s. Then there are 2(k − 1) additional strings σ with length k such that µ e ([σ]) > 0, each consisting of a string of 1's followed by a string of 0's or vice versa. For each of these σ, µ e ([σ]) = 1/4s, and if σ is a string of 0's or a string of 1's of length k, µ e ([σ]) = 1/2 − (k − 1)/4s. Thus when s is large compared to k, the non-halting case provides a good approximation to µ e ([σ]) when length(σ) ≤ k, even though e eventually halts. Thus, to compute µ e ([σ]) to within ε, it suffices to simulate the eth Turing machine O(k/ε) steps. If it halts before then, that determines µ e exactly; otherwise, the non-halting approximation is close enough. Now consider f = lim n A n 1 [1] in (2 ω , B, µ e ). Note that (A n 1 [1] )(ω) counts the density of 1's among the first n bits of ω. If Turing machine e does not halt, f (ω) = 1 if ω is the sequence of 1's, and f (ω) = 0 if ω is the sequence of 0's. Up to a.e. equivalence, these are all that matters, since the mass concentrates on these two elements of Cantor space. If Turing machine e halts in s steps, then f (ω) = 1/4 on the shifts of (1 s 0 3s ) * , and f (ω) = 3/4 on the shifts of (1 3s 0 s ) * . Suppose g is B k -measurable. If Turing machine e halts in s steps and k is much less than s, then roughly 3/4 of the shifts of ( 
. Turning this around, given the information that µ e ({ω | |f (ω) − g(ω)| > 1/8}) ≤ 1/4 for some g of complexity at most k enables one to determine whether or not Turing machine e halts; namely, one simulates the Turing machine for O(k) steps, and if it hasn't halted by then, it never will. Set µ = e 2 −(e+1) µ e . Since, for any g,
knowing a k e for each e with the property that µ({ω | |f (ω)−g(ω)| > 1/(8·2 e+1 )} < 1/4 for some g of complexity at most k e enables one to solve the halting problem. But such a k e can be obtained from a bound on the complexity of f . Thus µ satisfies the statement of the theorem.
The proof above relativizes, so for any set X there is a measure µ on 2 N , computable from X, such that no bound on the rate of complexity of f can be computed from X. As the following corollary shows, this implies that lim n A n 1 [1] can have arbitrarily high complexity.
Corollary. For any v : Q + → N there is a measure µ on 2 N such that if f = lim n A n 1 [1] and k(ε) is a bound on the complexity of f , then lim sup ε→0 k(ε)/v(ε) = ∞.
Proof. Let µ be such that no bound on the complexity of f can be computed from v. If the conclusion failed for some k, then there would be a rational ε ′ > 0 and N such that for every ε < ε ′ , k(ε) < N · v(ε). But then k ′ (ε) = N · v(min(ε, ε ′ )) would be a bound on the complexity of f that is computable from v, contrary to our choice of µ.
[4] Klaus Weihrauch. Computability on the probability measures on the Borel sets of the unit interval. Theoret. Comput. Sci., 219(1-2):421-437, 1999.
Departments of Philosophy and Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213

{'paper_id': '41705322', 'title': 'Uncomputably noisy ergodic limits', 's2_url': 'https://api.semanticscholar.org/CorpusID:41705322', 'source': 'S2ORC'}