You are an expert at summarizing long articles. Proceed to summarize the following text: 
the _ effective dimension _ and _ strong effective dimension _ of an infinite binary sequence @xmath4 are defined as @xmath6 where @xmath7 is the kolmogorov complexity of @xmath8 . they can be characterized as effective versions of hausdorff and packing dimensions respectively , or by divergence of @xmath9-gales ( see @xcite for the original results and @xcite for a survey ) . let @xmath10 $ ] be a computable real number and @xmath11 the bernoulli measure over cantor space given by @xmath12=p^{|w|_1}(1-p)^{|w|_0}$ ] . it is well - known that if an infinite binary sequence @xmath4 is martin - lf random w.r.t . @xmath11 then @xmath13 , where @xmath14 is the entropy of @xmath11 defined by @xmath15    this result is not difficult to prove and reduces to the strong law of large numbers for martin - lf random sequences , as on the one hand is the prefix version of kolmogorov complexity ] @xmath16+o(1)\ ] ] for @xmath11-random sequences by levin - schnorr theorem , and on the other hand @xmath17=-\frac{|x{\ensuremath{{\mathbin\upharpoonright}\raise-.2ex\hbox{\scriptsize $ n$}}}|_1}{n}\log(p)-\frac{|x{\ensuremath{{\mathbin\upharpoonright}\raise-.2ex\hbox{\scriptsize $ n$}}}|_0}{n}\log(1-p)\ ] ] which converge to @xmath14 for @xmath11-random sequences , by the strong law of large numbers for martin - lf random sequences . this result highlights the relationship between shannon s information theory , kolmogorov algorithmic information theory and effective randomness . ergodic theory provides a natural extension of information theory in which many results can be transferred , with more involved proofs , from the case of independent identically distributed random variables to the ergodic case , where independence is only required _ asymptotically , in the average _ ( see section [ sec_back ] for a precise definition ) . first , the strong law of large numbers extends to birkhoff s ergodic theorem . second , the coincidence between local information and entropy extends through the shannon - mcmillan - breiman theorem . whether martin - lf randomness fits with these theorems has been an open problem for a while . the first results were proved by vyugin @xcite , based on non - classical , constructive proofs of the theorems . he proved , in particular :    [ thm_birkhoff_vyugin ] let @xmath0 be a computable shift - invariant ergodic measure over @xmath1 and @xmath18 be computable . for every martin - lf @xmath0-random sequence @xmath4 , @xmath19    the entropy of an ergodic measure is defined as @xmath20\log \mu[w].\ ] ] observe that ( [ entropy_bernoulli ] ) and ( [ eq_entropy2 ] ) are consistent as they give the same quantity when @xmath0 is a bernoulli measure . [ thm_sh1 ] let @xmath0 be a computable shift - invariant ergodic measure over @xmath1 . for every martin - lf @xmath0-random sequence @xmath4 , @xmath21=h(\mu).\ ] ]    the question whether @xmath22 coincides with @xmath23 for every martin - lf @xmath0-random was left open by vyugin . an alternative proof of theorem [ thm_sh1 ] approximating ergodic measures by markovian measures was later developed by nakamura @xcite , but also left the question open . in this paper we provide a positive answer to this question . a classical proof of the shannon - mcmillan - breiman theorem uses birkhoff s ergodic theorem , applied to some particular functions . the problem in making it effective is that these functions are not computable in general . recent works have been achieved to push the effective ergodic theorem to the largest possible class of functions . here we extend it enough to get the full effective shannon - mcmillan - breiman theorem . in section [ sec_back ] we recall basic notions of computability , randomness and ergodic theory . in section [ sec_erg ] we develop effective versions of birkhoff s ergodic theorem . in section [ sec_sh ] we present our main result . we work on the cantor space @xmath24 of infinite binary sequences . a finite word @xmath25 determines the cylinder @xmath26\subseteq{\{0,1\}^{\mathbb{n}}}$ ] of infinite sequences starting with @xmath8 . if @xmath27 and @xmath28 , @xmath29 is the prefix of @xmath4 of length @xmath30 , and is also denoted @xmath31 . the cylinders form a base of the product topology . [ [ effective - topology . ] ] effective topology . + + + + + + + + + + + + + + + + + + +    an open set @xmath32 is _ * effective * _ if it is a recursively enumerable union of cylinders . a closed set is effective it its complement is an effective open set . a function @xmath33 is _ * computable * _ if there is a turing machine that on oracle @xmath4 and input @xmath30 computes a rational number @xmath34 such that @xmath35 . equivalently , @xmath36 is computable if for every rational numbers @xmath37 , @xmath38 is effectively open , uniformly in @xmath39 . a function @xmath40 $ ] is _ * lower * _ ( resp . _ * upper * _ ) _ * semi - computable * _ if there is a turing machine that on oracle @xmath4 and input @xmath30 computes a rational number @xmath41 such that @xmath42 ( resp . @xmath43 ) . equivalently , @xmath36 is lower ( resp . upper ) semi - computable if for every rational number @xmath44 , @xmath45 $ ] ( resp . @xmath46 ) is effectively open , uniformly in @xmath44 . [ [ kolmogorov - complexity - and - martin - lf - randomness . ] ] kolmogorov complexity and martin - lf randomness . + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +    for @xmath25 , @xmath7 is the prefix version of kolmogorov complexity , defined by levin and chaitin independently . it is defined as the length of a shortest input of a universal turing machine with prefix - free domain computing @xmath8 on that input . a probability measure @xmath0 over @xmath24 is determined by its value on cylinders @xmath47 $ ] , for @xmath25 . @xmath0 is computable if @xmath47 $ ] is a computable real number , uniformly in @xmath8 . given a computable probability measure @xmath0 , a sequence @xmath27 is _ * martin - lf @xmath48-random * _ , denoted @xmath49 , if there is @xmath50 such that for all @xmath30 , @xmath51-c.\ ] ] martin - lf s original definition @xcite was expressed in terms of tests rather than complexity , but the one given here , due to levin and chaitin @xcite independentely , was proved to be equivalent by levin @xcite and schnorr @xcite . the function @xmath52-k(x{\ensuremath{{\mathbin\upharpoonright}\raise-.2ex\hbox{\scriptsize $ n$}}})\}\ ] ] is lower semi - computable and @xmath53 . moreover , it was proved in @xcite that @xmath54 is maximal in the sense that for every integrable lower semi - computable function @xmath40 $ ] , there exists @xmath55 such that @xmath56 . we call such an @xmath36 a _ * @xmath48-test*_. it tests martin - lf randomness in the sense that @xmath49 iff @xmath57 for each @xmath0-test @xmath36 iff @xmath58 . more can be found on this subject in @xcite . [ [ ergodic - theory . ] ] ergodic theory . + + + + + + + + + + + + + + +    we recall some basic notions of ergodic theory , more details can be found in @xcite . we denote by @xmath59 the _ * shift map * _ defined by @xmath60 . a measure @xmath0 over @xmath24 is _ * shift - invariant * _ if for all borel sets @xmath61 , @xmath62 , equivalently if @xmath63+\mu[1w]=\mu[w]$ ] for all @xmath25 . @xmath0 is _ * ergodic * _ if for all borel sets @xmath61 such that @xmath64 up to a null sets , @xmath65 or @xmath66 . equivalently , @xmath0 is ergodic if for all @xmath67 , @xmath68\cap t^{-k}[v])=\mu[u]\cdot \mu[v].\ ] ] the following theorem , taken from @xcite , extends a result of ku@xmath69era  from the uniform measure to any ergodic shift - invariant measure :    [ thm_poincare ] let @xmath0 be a computable ergodic shift - invariant measure and @xmath70 an effective closed set such that @xmath71 . every martin - lf @xmath0-random sequence has a tail in @xmath72 , i.e. for every @xmath49 there exists @xmath73 such that @xmath74 .    in @xcite and @xcite independently this result was used to prove that not only the orbit of @xmath4 eventually falls into @xmath72 , but it does so with frequency @xmath75 . [ thm_brk_lsc ] let @xmath0 be a computable ergodic shift - invariant measure and @xmath70 an effective closed set such that @xmath71 . for every martin - lf @xmath0-random sequence @xmath4 , @xmath76    we first generalize the result from sets to functions :    [ thm_erg_semi ] let @xmath0 be a computable ergodic shift - invariant measure . assume @xmath77 $ ] is :    * either lower semi - computable , * or upper semi - computable and bounded by a @xmath0-test .    for each @xmath49 , @xmath78    let us introduce the notation @xmath79 . if @xmath36 is lower semi - computable , then there is a sequence of uniformly computable nonnegative functions @xmath80 . applying theorem [ thm_birkhoff_vyugin ] to @xmath81 and @xmath49 gives @xmath82 . by the monotone convergence theorem , @xmath83 , so @xmath84 . if @xmath85 we are done . otherwise , let @xmath86 be a rational number . the set @xmath87 is effectively closed and by the classical ergodic theorem , there exists @xmath88 such that @xmath89 . theorem [ thm_poincare ] tells us that if @xmath49 then there is @xmath30 such that @xmath90 . as a result , @xmath91 . as this is true of every @xmath86 , we get the result .    now , if @xmath36 is upper semi - computable and @xmath92 where @xmath93 is a @xmath0-test , then for @xmath49 , applying the preceding result to @xmath93 and @xmath94 , @xmath95    we then extend this result further :    [ cor_delta2_bounded ] let @xmath40 $ ] be @xmath96 on @xmath97 , i.e. there is a sequence @xmath81 of uniformly computable functions such that @xmath98 for each @xmath49 . assume that @xmath36 is dominated by a @xmath0-test . for every @xmath49 , @xmath99    let @xmath100 and @xmath101 . on @xmath97 , @xmath102 and @xmath103 . by the monotone and dominated convergence theorem , the convergences hold in @xmath104 . applying theorem [ thm_brk_lsc ] to @xmath105 and @xmath106 gives the result . more precisely , for every @xmath49 and every @xmath107 , @xmath108 so @xmath109 we now present our main result .      a proof of the classical result , stating the result for a.e . @xmath4 , can be found in @xcite . it makes use of martingale convergence theorems and ergodic theorems . the main difficulty in adapting the proof is to make sure that the effective versions of the ergodic theorem can be applied . the rest of this section is devoted to the proof of theorem [ thm_main ] . an easy calculation shows that @xmath111 = \sum_{k=0}^{n-1}f_{n-1-k}\circ t^{k}(x)\ ] ] where @xmath112=-\log\frac{\mu[x_0\ldots x_k]}{\mu[x_1\ldots x_k]}&\quad & \text{for } k\geq 1,\\ f_0(x ) & : =   -\log \mu[x_0].\end{aligned}\ ] ]      define the computable martingale @xmath114 } \\ d(x_0\ldots x_k ) & = \frac{\mu[x_1\ldots x_k]}{\mu[x_0\ldots x_k]}\quad\text{for $ k\geq 1$.}\end{aligned}\ ] ] by the effective doob s convergence theorem ( see theorem 7.1.3 on page 270 in @xcite ) , for each @xmath49 , @xmath115 converges , and so does @xmath116 . let @xmath117 be the limit . we write @xmath118=\frac{1}{n}\sum_{k=0}^{n-1}(f_{n-1-k}\circ t^k(x)-f\circ t^k(x))+\frac{1}{n}\sum_{k=0}^{n-1}f\circ t^k(x)\ ] ] and prove that the first term tends to @xmath119 while the second term converges to @xmath120 . @xmath128 is lower semi - computable and by lemma [ lem_sup ] it is a @xmath0-test . by construction , @xmath36 is @xmath96 on @xmath97 and it is dominated by @xmath128 so it satisfies the conditions of corollary [ cor_delta2_bounded ] , from which the result follows directly . let @xmath130 for @xmath131 , @xmath132 so @xmath133 . as @xmath122 a.e . , @xmath134 a.e . as @xmath135 , @xmath134 in @xmath124 by the dominated convergence theorem . on @xmath97 , @xmath136 fix @xmath107 and let @xmath137 . as @xmath138 is lower semi - computable , the first term converges to @xmath139 by the effective ergodic theorem [ thm_erg_semi ] . as @xmath140 is @xmath96 on @xmath97 and is dominated by the @xmath0-test @xmath141 , the second and the third terms converge to @xmath142 by corollary [ cor_delta2_bounded ] so their limits cancel each other . laurent bienvenu , adam day , ilya mezhirov , and alexander shen . ergodic - type characterizations of algorithmic randomness . in _ computability in europe ( cie 2010 ) _ , volume 6158 of _ lecture notes in computer science _ , pages 4958 . springer , 2010 . johanna  n.y . franklin , noam greenberg , joseph  s. miller , and keng meng ng . artin - lf random points satisfy birkhoff s ergodic theorem for effectively closed sets . to appear in the _ proceedings of the american mathematical society _ , 2010 .
let @xmath0 be a computable ergodic shift - invariant measure over @xmath1 . providing a constructive proof of shannon - mcmillan - breiman theorem 
 , vyugin proved that if @xmath2 is martin - lf random w.r.t . 
 @xmath0 then the strong effective dimension @xmath3 of @xmath4 equals the entropy of @xmath0 . 
 whether its effective dimension @xmath5 also equals the entropy was left as an problem question . in this paper 
 we settle this problem , providing a positive answer . a key step in the proof 
 consists in extending recent results on birkhoff s ergodic theorem for martin - lf random sequences . 
 + _ keywords : shannon - mcmillan - breiman theorem ; martin - lf random sequence ; effective hausdorff dimension ; compression rate ; entropy .