•MirceaD85
Strain
Karma: -32
 Deconectat
Mesaje: 38
|
 |
« Răspunde #50 : Martie 14, 2012, 10:49:31 » |
|
Si daca tot nu sunteti convinsi, uite o demonstratie mai scurta, bazata pe computabilitate. Presupunem p>0.
Fie W = {0,1}*. E clar ca W ~ Rron (multimea numerelor reale).
Fie w = a i-lea element al lui w (de la stanga la dreapta).
Pentru w finit, negol:
Fie u(w) = w din care elimin cea mai din dreapta cifra.
Fie w_0(w) = w din care elimin cel mai din dreapta 0, daca exista.
Fie w_1(w) = w din care elimin cel mai din dreapta 1, daca exista.
Fie w_*(w) = w_0(w_*(u(w))) daca ultima cifra a lui w este 1, w_1(w_*(u(w))) altfel.
Fie n0[w] = numarul de 0 din w.
Fie n1[w] = numarul de 1 din w.
Fie r raspunsul problemei. Presupunem prin absurd r>0.
Fie M(w) functia aferenta unei masini Turing care simuleaza furnica pentru un input w din W si se opreste atunci cand furnica cade in prapastie sau cand s-a ajuns la capatul lui w si produce la output M(w). M(w) = 1 daca furnica a cazut si 0 altfel.
Observam ca M(w) = 1 => Furnica pica in prapastie CERT pe orice extensie a lui w (chiar si infinita) (1)
r>0 => Exista v din W, a.i. M(pref(v)) = 0 pentru orice prefix finit pref(v) al lui v. Altfel =>(1) nu exista v (o serie de rezultate ale samplingului randomului) pentru care furnica sa traiasca la infinit => r = 0 contradictie.
Fie v cu proprietatea de mai sus si fie V multimea elementelor cu proprietatea lui v.
Fie seturile Si,Li,Ti de siruri din {0,1}^i, pentru orice i natural. Initial S0=L0=T0 = {0,1}^0 (Empty). Si+1 = U A(s)={s 0| M(s 0) = 0} U B(s)= {s 1)} pentru orice s din Si. Li+1 = {w_*(s)|s din Si+1} Fie Ti+1 = {s din Li+1 | |s| = i+1}
=> Multimea Si este multimea tuturor prefixelor "plauzibile" de lungime i pentru v.
=> Pentru v => pentru orice prefix vk al lui v => (Exista) un i a.i. vk apartine Si => Exista i a.i. w_*(vk) apartine lui Li.
=> Li este multime de prefixe "plauzibile" (pentru orice v, a carui plauzibilitate se limiteaza la prefixul i)
Prin inductie Li inclus in {Empty, 1, 11, 111, ... }. //Observam ca w_*(A(s)) apartine unui Li-k si w_*(B(s)) la fel, mai putin daca s=1111....
Dar prin inductie din nou {1}^i inclus in Li => Li = {Empty, 1, 11, 111, ... }.
Fie x din Si, i>2. v = x ..., cu |x|=i . Fie alpha maximal a.i. x = 1 y alpha, cu w_*(alpha)=l2 din Li.
Daca |alpha| = 0 => x = 1 y => w_*(1 y) este in Li => w_*(y) este in Li => alpha nu e maximal. => |alpha|>0
|alpha| > 0 => Daca |y|>0 => x = 1 y alpha, cu |alpha|>=1 => x = 1 y' 0 alpha' 1 alpha'', cu w_*(alpha'j) din Li => Alpha nu e maximal => |y|=0. => x = 1 alpha, alpha maximal a.i. w_*(alpha)=l2 din Li => x apartine {f} din w_*^-1(w(x)) cu |f|=|x|.
Fie L = U Lj dupa j.
Fie Ri = {f | f apartine w_*^-1(L) si |f|=i}.
Ri = multimea prefixelor lungime i, plauzibile in orice moment.
Fie F(i,x) = {f | f apartine w_*^-1({1}^i) si |f|=x}
Fie Gi(x) = U F(k,x) pentru k<=i.
Observam ca F(i,x) = F(i-1,x-1) 1 U F(i,x-1) 0 => F(i,x) \ (F(i-1,x-1) 1) = F(i,x-1) 0 => F(i,x-1)0 U (F(i,x-1)\F(i-1,x-1))1 = F(i,x-1) 0 => F(i,x-1)=F(i-1,x-1).
=> Gi(x)= F(i,x). //Prin inductie: G(0) = F(0,0); G(i+1,x-1) = F(i+1,x-1) U G(i,x-1) =ind F(i+1,x-1) U F(i,x-1) = U F(i+1,x-1).
i>x => Gi(x) = F(i,x) = 0.
Ri = U Gj(i) dupa j natural = U Gj(i) dupa j<=i = U F(j,i), dupa j<=i = Gi(i) = F(i,i) => Ri = {1}^i.
Cum Prefi(v) apartine Ri pentru orice i => Orice prefix finit al lui v este alcatuit doar din 1.
v real (din W ~ Rron) => = v = lim i->inf din Sum(2^Prefi(v)[j]) => v = lim ( 2^(i+1) - 1). Dar lim(2^(i+1) - 1) nu apartine R (este +infinit) => v nu exista contradictie => Ipoteza r>0 falsa!!!
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena