Zrjydtj

Theorema Posner–Robinson est theorema theoriae facultatis calculandi de gradibus Turing.

Expositio |

Theorema. Sit Bdisplaystyle B copia numerorum naturalium, quae calculari non potest. (Id est B≰T0displaystyle Bnot leq _Tmathbf 0 .) Tum est copia Gdisplaystyle G ut
G⊕B≡TG′displaystyle Goplus Bequiv _TG^prime .

Demonstratio |

Sit Bdisplaystyle B. Volumus facere series ((Φp,X¯p))p∈ωdisplaystyle ((Phi _p,bar X_p))_pin omega , quorum:

• 
  Φpdisplaystyle Phi _p est copia finita rerum sicut (a,b,X)displaystyle (a,b,X), in qua a,b∈ωdisplaystyle a,bin omega , X∈2<ωdisplaystyle Xin 2^<omega . Φp(X)displaystyle Phi _p(X) est functio ab 2ωdisplaystyle 2^omega in 2ωdisplaystyle 2^omega , ut Φp(X)(a)=bdisplaystyle Phi _p(X)(a)=b si et tantum si (a,b,X)∈Φpdisplaystyle (a,b,X)in Phi _p,


• 
  X¯pdisplaystyle bar X_p est copia finita rerum X∈2ωdisplaystyle Xin 2^omega ,

in qua serie, si q>pdisplaystyle q>p:

• (a) Cuique (xq,yq,η)∈Φq∖Φpdisplaystyle (x_q,y_q,eta )in Phi _qbackslash Phi _p et (xp,yp,σ)∈Φpdisplaystyle (x_p,y_p,sigma )in Phi _p, |η|>|σ|displaystyle vert eta vert >vert sigma vert ,


• (b) Φp⊆Φqdisplaystyle Phi _psubseteq Phi _q et X¯p⊆X¯qdisplaystyle bar X_psubseteq bar X_q,


• (c) Cuique X∈X¯pdisplaystyle Xin bar X_p, Φq(X)=Φp(X)displaystyle Phi _q(X)=Phi _p(X).

ita ut, si Φ:=⋃p∈ωΦpdisplaystyle Phi :=bigcup _pin omega Phi _p, tum Φ(B)=Φ′displaystyle Phi (B)=Phi ^prime . Sit Φ0=X¯0=∅displaystyle Phi _0=bar X_0=varnothing . Si habemus (Φp,X¯p)displaystyle (Phi _p,bar X_p), sic agamus ut (Φp+1,X¯p+1)displaystyle (Phi _p+1,bar X_p+1) faciamus:

1. Sit ∃nθp(n,Z|n)displaystyle exists n,theta _p(n,Zvert n) formula numero pdisplaystyle p. Si nancisci possumus copiam Ψ⊇Φdisplaystyle Psi supseteq Phi quae (a) satisfaciat, ut cuique X∈X¯p∪Bdisplaystyle Xin bar X_pcup B, Ψ(X)=Φ(X)displaystyle Psi (X)=Phi (X), tum sit Φp+1:=Ψ∪(p,1,B)displaystyle Phi _p+1:=Psi cup (p,1,B) et X¯p+1:=X¯pdisplaystyle bar X_p+1:=bar X_p.


2. Sin nancisci non possumus Ψdisplaystyle Psi , tum sciamus cuique copiae Ψ⊆Φdisplaystyle Psi subseteq Phi quae (a) satisfaciat esse X∈X¯p∪Bdisplaystyle Xin bar X_pcup B ut Ψ(X)≠Φ(X)displaystyle Psi (X)neq Phi (X). Sit igitur collectio Zdisplaystyle mathcal Z ut:

Z¯∈Z⟺Sit Ψ⊇Φ quae (a) satisfaciat, tum si ∃n<|Ψ|θp(n,Ψ|n), tum ∃(a,b,X)∈Ψ∖Φ, ut X∈Z¯displaystyle bar Zin mathcal Ziff textSit Psi supseteq Phi text quae (a) satisfaciat, tum si exists n<vert Psi vert ,theta _p(n,Psi vert n)text, tum exists (a,b,X)in Psi backslash Phi text, ut Xin bar Z

Sed scilicet X¯p∪B∈Zdisplaystyle bar X_pcup Bin mathcal Z, ergo Z≠∅displaystyle mathcal Zneq varnothing . Lemma habemus:

Lemma. (de conis vitandis) Sit collectio non vacua Adisplaystyle mathcal A ut X∈A⟺∀nθ(n,X|n)displaystyle Xin mathcal Aiff forall n,theta (n,Xvert n), in quo θ∈Δ0displaystyle theta in Delta _0 (vide pagina de hierarchia arithmetica). Sit D≰T0displaystyle Dnot leq _Tmathbf 0 . Tum est G∈Adisplaystyle Gin mathcal A ut G≱TDdisplaystyle Gnot geq _TD.

Ergo, sit D¯=Bdisplaystyle bar D=B, tum est Z¯∈Zdisplaystyle bar Zin mathcal Z ut Z¯≱TBdisplaystyle bar Znot geq _TB, id est, B∉Z¯displaystyle Bnot in bar Z. Igitur sit Φp+1=Φp∪(p,0,B)displaystyle Phi _p+1=Phi _pcup (p,0,B) et X¯p+1:=X¯p∪Z¯displaystyle bar X_p+1:=bar X_pcup bar Z.

Nunc tota serie facta habemus Φdisplaystyle Phi ut Φ(B)=Φ′displaystyle Phi (B)=Phi ^prime . Ergo Φ⊕B≡TΦ′displaystyle Phi oplus Bequiv _TPhi ^prime , quod erat demonstrandum.

Significatio |

Hoc theorema naturam omnium copiarum quae calculari non possunt patefacit. Si Bdisplaystyle B est copia quae calculari non potest, tum nancisci possumus copia Gdisplaystyle G, ut differentia inter Gdisplaystyle G et G′displaystyle G^prime sit Bdisplaystyle B.