Page - 451 - in Differential Geometrical Theory of Statistics

Entropy2016,18, 110 3.4. KolmogorovComplexityand theAsymptoticBound Werecallherebrieflytheresultof [16] linkingtheasymptoticboundoferrorcorrectingcodes to Kolmogorovcomplexity. Aswediscussedabove, only theasymptoticboundmarksa significant changeofbehaviorof codesacross thecurve (isolatedcodepointswithfinitemultiplicityversusaccumulationpointswith infinitemultiplicity). In thissense thiscurve isverydifferent fromall theotherbounds in thespace of codeparameters.However, there isnoexplicit expression for thecurveR= αq(δ) thatgives the asymptoticbound. Indeed,eventhequestionof thecomputabilityof the functionR=αq(δ) isapriori unclear. Thisquestionwasformulatedexplicitly in [25]. It isproved in [16] that theasymptoticboundR= αq(δ)becomescomputablegivenanoracle thatcan list codesbyincreasingKolmogorovcomplexity.Givensuchanoracle,onecanprovidean explicit iterative (algorithmic)procedure forconstructing theasymptoticbound. This implies that the asymptoticboundis“atworstasnon-computableasKolmogorovcomplexity”. Consider thesetX=Cqof (unstructured)q-arycodesandthesetY⊂ [0,1]2 ofcodepointsand thecomputable function f :X→Y thatassigns toacodeC∈X its codeparameters (R(C),δ(C))∈Y. LetYfin andY∞be, respectively, thesubsetsof thespaceofcodepoints thatcorrespondtocodepoints realizedwithfinite andwith infinitemultiplicity. Thealgorithm iterativelyproduces twosets Am andBm thatapproximate, respectively,Y∞ andYfinbyYfin=∪m≥1Bm andY∞=∪m≥1(∩n≥0Am+n). The inductive construction starts by choosing an increasing sequenceof positive integersNm and settingB1=∅andtakingA1 tobe thesetofcodepointsywithν−1Y (y)≤N1,whereνY :N→Y isa fixedenumerationof thesetof rationalpoints [0,1]2∩Q2wherecodepointsbelong. General estimates on the behavior of (exponential) Kolmogorov complexity under composition of total recursive functions (see [30], Section VI.9 of [32]) show that, for a composition F= f0(f1(t1, . . . ,tm), · · · , fn(t1, . . . ,tm),tm+1, . . . ,t ) of recursive functions the Kolmogorovcomplexitysatisfies K(F)≤ c · n ∏ i=1 K(fi) · ( log n ∏ i=1 K(fi) )n−1 , forafixed f0 andvarying fi, i≥1. Consider the total recursive functionF(x)=(f(x),n(x))with n(x)=#{x′ |ν−1X (x′)≤ ν−1X (x), f(x′)= f(x)} where νX :N→X is an enumerationof the spaceof codes. Consider the enumerable setsXm := {x ∈ X |n(x) = m} and Ym := f(Xm) ⊂ Y, with Y∞ = ∩mf(Xm) and Yfin = f(X) Y∞. For ϕ : f(X)→ X1, defined as f−1 on f(X1) = f(X), applying the composition rule for exponential Kolmogorovcomplexity, it is showninProposition3.1of [16] that, forx∈X1 andy= f(x), onehas K(x)=K(ϕ(y))≤ cϕ ·K(y)≤ cν−1Y (y), hence KTU(x)≤ c ·ν−1Y (y). UsingthesametypeofestimateofKolmogorovcomplexityforcompositionofrecursivefunctions, it is thenshown inProposition3.2 [16] that, fory∈Y∞ andm≥ 1, and foraunique xm ∈X,with y= f(xm),n(xm)=mand c= c(f,u,v,νX,νY)>0,onefinds KTU(xm)≤ c ·ν−1Y (y)m log(ν−1Y (y)m). 451