[ Pobierz całość w formacie PDF ]
.The measure of the set of possibilities for coveredbyn-bit theories is thusthe2n2;n;f(n);k=2;f(n);k:The (Ak) of the union of the set of possibilities for coveredmeasurebyn-bitnis thustheories with anyX XP2;f(n);k=2;k2;f(n)k(sincef(n):2; 2; 1)nnThusAkand (Ak)kforkif there is alwaysis covered by 2; everyann-bitn+f(n)kbits of , which is impossible.theory that yields +Q.E.D.Corollary AIfX2;f(n)convergesfis computable,cfwith theand then there is a constantpropertyn-bitn+f(n)cfbitsthat no theory ever yields more than +of. 204 CHAPTER 8.INCOMPLETENESSProofChoosecso thatX:2;f(n)c2ThenX2;[f(n)+c] 1andf0(n)f(n)c.Q.E.D.we can apply Theorem A to = +Corollary A2LetX2;f(n)convergefbeg(n) is computable, thenand computable as before.Iftherecf gwithg(n)-bit theory everis a constant the property that noyieldsg(n)f(n)cf gbitsNof themore than + + of.E.g., considerformn22:ForN,N-bitN+f(logN)+cf gsuch no theory ever yields more than logbits of.NoteThusnof special form, i.e., which have concise descriptions, weforget better upper bounds on the number of bits of which are yieldedbyn-bit theories.This is a foretaste of the way algorithmic informationtheory will be used in Theorem C and Corollary C2 (Section 8.4).Lemma for Second Borel{Cantelli Lemma!Forxkg of non-negative real numbers,any nite set fY(1x):;k P1xkProofIfxis a real number, then11x :;1x+ThusY(1x)1;k Q(1x)xP1+kk 8.3.RANDOM REALS: j AXIOMSj 205sincexkare non-negativeif all theY(1x)x:X+k kQ.E.D.Second Borel{Cantelli Lemma [Feller (1970)]SupposeAnhave the property that it is possible tothat the eventsdetermineAnoccurs by examining the rstwhether or not the eventf(n)fis a function.nbits of , where If the eventsPcomputableAaremutually (An) diverges, then has the propertyindependent andthatAnmust occur.in nitely many of theProofSuppose on the contrary that has the property that only nitelymanyAnoccur.Nsuch that the eventof the events Then there is anAndoesn N.The probability that none of the eventsnot occur ifAN AN+1 ::: AN+koccurAnare mutually independent,is, since thepreciselykY (A))1h(1N+i;P (A)iki=0 N+ii=0whichkgoes to in nity.This would give us arbitrarilygoes to zero assmall covers for , which contradicts the fact that is Martin-Lofrandom.Q.E.D.Theorem BIfX2n;f(n)divergesfis computable, thenf(n)and in nitely often there is a run ofzerosnandn+1n [ Pobierz całość w formacie PDF ]