|
[ Pobierz całość w formacie PDF ]
.I.e., in Conway's terminology [Conway(1986)], \ LISP has no syntax," except for a set of measure zero.For1Self-contained S-expression i.e., the expression is evaluated in an empty envi-ronment, and all needed function de nitions must be made locally within it.2The expressions may evaluate to di erent function de nitions, as long as thesede nitions compute the same function. 5.1.COMPLEXITY VIA LISP EXPRESSIONS 141if one ips 7 coins for each character, eventually the number of rightparentheses will overtake the number of left parentheses, with probabil-ity one.This is similar to the fact that heads versus tails will cross theorigin in nitely often, with probability one.I.e., a symmetrical randomwalk on a line will return to the origin with probability one.For a moredetailed explanation, see Appendix B.Now let's select from the set of all syntactically correct programs,which has measure 1, those that give a particular result.I.e., let'sconsiderPLISP(x) de ned to be the probability that an S-expressionchosenx.In other words, if one tosses 7 coinsat random evaluates toper character, what is the chance that the LISP S-expression that onegetsx?evaluates toFinally, we de ne to be the probability that an S-expressionLISP\halts", i.e., the probability that it has a value.If one tosses 7 coinsper character, what is the chance that the LISP S-expression that onegets halts? That is the value of.LISPNow for an upper bound on LISP complexity.Consider the S-expression ('x) which evaluates to x.This shows thatH(x)xj:j +3The complexity of an S-expression is bounded from above by its size +3.Now we introduce the important notion of a minimal program.Aminimal program is a LISP S-expression having the property that nosmaller S-expression has the same value.It is obvious that there isat least one minimal program for any given LISP S-expression, i.e., atleastpwithpjHLISP(x)x.Consider the S-one j = which evaluates toexpressionqisp,pis a minimal(! q) where a minimal program for andprogramx.x, and thusfor This expression evaluates tojpjH(x)qjH(p)= 3 + j =3 +whichpis a minimal program, thenshows that ifH(p)pj:j ; 3Itp, and there are in nitely manyfollows that all minimal programsof them, have the property thatjH(p)pj:;j j 3 142 CHAPTER 5.CONCEPTUAL DEVELOPMENTI.e., LISP minimal programs are algorithmically incompressible, at leastif one is programming in LISP.Minimal programs have three other fascinating properties:(1) Large minimal programs are \normal", that is to say, each of the128 characters in the LISP character set appears in it with a rel-ative frequency close to 1/128.The longer the minimal programis, the closer the relative frequencies are to 1/128.(2) There are few minimal programs for a given object minimal pro-grams are essentially unique.(3) In any formal axiomatic theory, it is possible to exhibit at mosta nite number of minimal programs.In other words, there is aversion of G incompleteness theorem for minimal programs:odel'sto prove that a program is minimal is extremely hard.Let's start by showing how to prove (3).We derive a contradictionfrom the assumption that a formal theory enables one to prove thatin nitely many programs are minimal.For if this were the case, wecouldfas follows: given the positive integerde ne a LISP functionkask1's, look for the rst proof in the formalargument as a list oftheorypis a minimal program of size greater thanthat an S-expression2k,pbef(k).Then it is easy to see thatand let the value of2k;2n\ :is recursivelytone can eventually dis-enumerable.Similarly, givencoverPC(s=t) that is a power of two.In otherevery lower bound onwords,tone can recursively enumerate the set of all true propo-givensitionsn o; ;Tt PC(s=t)>2n"PC(s=t)>2n:\ :This will enable us to use Theorem I2 to show that there is a computerDwith these properties:(HD(s)PC(s)= ; lg +1(6.1)CPD(s)P(s)2ng:f( : 170 CHAPTER 6.PROGRAM SIZEThuss n)n PC(s=t) + 1.( is taken as a requirement i ; lgHencepofnsuchD(p t)sthe number of programs length that =isn PC(s=t) + 1 and is 0 otherwise, which immediately1 if ; lgyields (6.2).However, we must checkDsatisfythat the requirements (6.4) onthe Kraft inequality and are consistent.X;jC2pjP(s=t)1k>2k>31 1 1=:+ + + =12 4 8On the other hand (see the next section), if we arenallowed to try 2timesnguesses, one of them will always get it right, if wea series oftryndi nguesses.all 2 erent possible series ofTheorem XAnyTcan yield only nitely many (scattered)given formal theorybits of (the base-two expansion of).When we say that a theory yieldsa bit of , we mean that it enables us to determine its position and its0/1 value.ProofConsiderT, an r.e.set of true assertions of the forma theory\Thenth bit of is 0."\Thenth bit of is 1." 202 CHAPTER 8.INCOMPLETENESSHerendenotes speci c positive integers.IfTprovideskdi erent (scattered) bits of , then that gives usaAkofkwhichTuntilcovering measure 2; includes : Enumeratekbits of are determined, then the covering is all bit strings up tothe last determined bit withnis the lastall determined bits okay.Ifdetermined bit,n-bitthis coveringn;kstrings, and willwill consist of 2haven;k=2n=2;k.measure 2ItTyields in nitely many di erent bits of , thenfollows that ifforkwe can produce by runningTaany through all possible proofs incoveringAkofkwhich includes.But this contradicts themeasure 2;fact thatTyields only nitely manyis Martin-L random.Henceofbits of.Q.E.D.Corollary XSince by Theorem R8 can be encoded into an exponential dio-phantine equationL(n x1 ::: xm)R(n x1 ::: xm) (8.2)=it follows that any given formal theory can permit one to determinewhether (8.2) has nitelyx1 ::: xm, foror in nitely many solutionsonly nitely manyn.speci c values of the parameter8.3 Incompleteness Theorems for Ran-dom Reals: j AxiomsjTheorem AIfX2;f(n) 1andfis computable,cfwith the property thatthen there is a constantnon-bitn+f(n)cfbits of.theory ever yields more than +ProofLetAkbe thensuch that there isevent that there is at least oneann-bitn+f(n)kor more bits of.theory that yields +2 0 1 0 132n2;[n+f(n)+k]X6 B C B C(Ak)n-bit @ probability that yields A74 @ A 5ntheoriesn+f(n)kbits of+ 8.3.RANDOM REALS: j AXIOMSj 203X=2;k2;f(n)k2;nsinceX:2;f(n) 1PHence (Ak)k, (Ak) also converges.Thus only nitely2; andmanyAkoccur (Borel{Cantelli lemma [Feller (1970)]).I.e.,of the[ Xlim (Ak) (Ak)N! 0:2;N!1k>Nk>NMore detailed proofAssume the opposite of what we want to prove, namely that foreveryktheren-bitn+f(n)kbitsis at least one theory that yields +of.From this we shall deduce that cannot be Martin-L random,ofwhich is impossible.ToAkof withk,nget a covering measure 2; consider a speci candn-bit theories [ Pobierz całość w formacie PDF ] |
Archiwum
|