Nuprl Theory sci_inv13

(only non hidden objects are presented)

COMsci_inv_lemma13---- Lemma 13 --------------------------------------------
ABSinv13_assumpinv13_assump{}(s; p; q; r) == status-p_ = Purging status-p_ = Ftod (staying(s;q) (succ-q_ = p)) (purgeQ(q::[]) buf[p]_) (purgeR(q::p::[]) buf[r]_)
THMinv13_assump_wfs:state. p,q,r:PId. inv13_assump{}(s; p; q; r)
ABSinv13_preinv13_pre{}(n; s) == p,q:P. r:P+m. inv13_assump{}(s; p; q; r)
THMinv13_pre_wfn:. s:state. inv13_pre{}(n; s)
ABSinv13a_offinv13a_off{}(s; p) == status-p_ = Off status-p_ = Pending cs-p_ = invalid{}
THMinv13a_off_wfs:state. p:PId. inv13a_off{}(s; p)
ABSinv13a_inlistinv13a_inlist{}(s; p) == status-p_ = Inlist (cs-p_ = invalid{})
THMinv13a_inlist_wfs:state. p:PId. inv13a_inlist{}(s; p)
ABSinv13a_purginginv13a_purging{}(s; p) == status-p_ = Purging cs-p_ = dirty{} succ-p_ = nil
THMinv13a_purging_wfs:state. p:PId. inv13a_purging{}(s; p)
ABSinv13a_ftodinv13a_ftod{}(s; p) == status-p_ = Ftod cs-p_ = fresh{} pred-p_ = m
THMinv13a_ftod_wfs:state. p:PId. inv13a_ftod{}(s; p)
ABSinv13a_inqueueinv13a_inqueue{}(s; p) == status-p_ = Inqueue pred-p_ = m succ-p_ = nil
THMinv13a_inqueue_wfs:state. p:PId. inv13a_inqueue{}(s; p)
ABSinv13a_delrightinv13a_delright{}(s; p; q; r; cs) == delrightQ(q::r::cs::[]) buf[p]_ (r = nil) (cs = invalid{})
THMinv13a_delright_wfs:state. p:PId. q,r,cs:. inv13a_delright{}(s; p; q; r; cs)
ABSinv13a_visiting1inv13a_visiting1{}(s; p; q; r; cs) == visiting(s;p) (status-q_ = Delleft) delrightQ(p::r::cs::[]) buf[q]_ succ-p_ = q
THMinv13a_visiting1_wfs:state. p,q:PId. r,cs:. inv13a_visiting1{}(s; p; q; r; cs)
ABSinv13a_visiting2inv13a_visiting2{}(s; p; q) == visiting(s;p) delrightR(q::ok{}::[]) buf[p]_ succ-p_ = q
THMinv13a_visiting2_wfs:state. p:PId. q:. inv13a_visiting2{}(s; p; q)
ABSinv13ainv13a{}(s; p; q; r; cs) == inv13a_off{}(s; p) inv13a_inlist{}(s; p) inv13a_purging{}(s; p) inv13a_ftod{}(s; p) inv13a_inqueue{}(s; p) inv13a_delright{}(s; p; q; r; cs) inv13a_visiting1{}(s; p; q; r; cs) inv13a_visiting2{}(s; p; q)
THMinv13a_wfs:state. p,q:PId. r,cs:. inv13a{}(s; p; q; r; cs)
ABSinv13a_inv13a_{}(s; p; q; r; cs) == inv13a_off{}(s; p) inv13a_inlist{}(s; p) inv13a_purging{}(s; p) inv13a_ftod{}(s; p) inv13a_inqueue{}(s; p) inv13a_delright{}(s; p; q; r; cs) inv13a_visiting1_{}(s; p; q; r; cs) inv13a_visiting2{}(s; p; q)
THMinv13a__wfs:state. p,q:PId. r,cs:. inv13a_{}(s; p; q; r; cs)
ABSinv13b_1inv13b_1{}(s; p) == (status-p_ = Inqueue) cs-p_ = invalid{} pred-p_ = nil succ-p_ = nil
THMinv13b_1_wfs:state. p:PId. inv13b_1{}(s; p)
ABSinv13b_2inv13b_2{}(s; p) == (cs-p_ = invalid{}) (pred-p_ = nil)
THMinv13b_2_wfs:state. p:PId. inv13b_2{}(s; p)
ABSinv13binv13b{}(s; p) == inv13b_1{}(s; p) inv13b_2{}(s; p)
THMinv13b_wfs:state. p:PId. inv13b{}(s; p)
ABSinv13cinv13c{}(n; s) == head-m_ = nil (p:P. idle(s;p) leaving(s;p))
THMinv13c_wfn:. s:state. inv13c{}(n; s)
ABSinv13dinv13d{}(n; s; p) == head-m_ = p (p = nil) maxrank(n;s;p)
THMinv13d_wfn:. s:state. p:PId. inv13d{}(n; s; p)
ABSinv13einv13e{}(n; s; p; q; r) == idle(s;p) entering(s;p) leaving(s;p) maxrank_visiting(n;s;p) (staying(s;q) (succ-q_ = p)) (purgeQ(q::[]) buf[p]_) (purgeR(q::p::[]) buf[r]_)
THMinv13e_wfn:. s:state. p,q,r:PId. inv13e{}(n; s; p; q; r)
ABSinv13finv13f{}(n; s; p; q; cv; arg) == read_cache_freshR(m::q::cv::arg) buf[p]_ read_cache_goneR(m::q::cv::arg) buf[p]_ ((q = nil rank(s;p) = 0 (r:P. visiting(s;r))) (isP(q) ((isP(q) entering(s;q)) maxrank_visiting(n;s;q)) hasrank(s;q) hasrank(s;p) rank(s;p) = rank(s;q) + 1)) cv-m_ = cv
THMinv13f_wfn:. s:state. p,q,cv:. arg: List. inv13f{}(n; s; p; q; cv; arg)
ABSinv13ginv13g{}(s; p) == visiting(s;p) (status-p_ = Purging) succ-p_ = nil rank(s;p) = 0
THMinv13g_wfs:state. p:PId. inv13g{}(s; p)
ABSinv13hinv13h{}(n; s; p; q) == visiting(s;p) succ-p_ = q (q = nil) (isP(q) visiting(s;q)) hasrank(s;q) hasrank(s;p) rank(s;p) = rank(s;q) + 1
THMinv13h_wfn:. s:state. p:PId. q:. inv13h{}(n; s; p; q)
ABSinv13iinv13i{}(n; s; p; q) == prependQ(q::[]) buf[p]_ hasrank(s;p) hasrank(s;q) rank(s;q) = rank(s;p) + 1 ((isP(p) entering(s;p)) maxrank_visiting(n;s;p))
THMinv13i_wfn:. s:state. p:PId. q:. inv13i{}(n; s; p; q)
ABSinv13jinv13j{}(s; p; q; r; cv) == delleftQ(q::r::cv::[]) buf[p]_ visiting(s;q) succ-q_ = r pred-q_ = p
THMinv13j_wfs:state. p,q:PId. r,cv:. inv13j{}(s; p; q; r; cv)
ABSinv13kinv13k{}(n; s; p; q; r; cv; cs) == prependR(q::q::ok{}::cv::cs::[]) buf[p]_ maxrank_visiting(n;s;q) hasrank(s;p) (cs = invalid{}) pred-q_ = p rank(s;p) = rank(s;q) + 1 (staying(s;r) (pred-r_ = m))
THMinv13k_wfn:. s:state. p,q,r:PId. cv,cs:. inv13k{}(n; s; p; q; r; cv; cs)
ABSinv13linv13l{}(n; s; p; q; cv; cs) == prependR(q::nil::ok{}::cv::cs::[]) buf[p]_ (r:P. visiting(s;r)) rank(s;p) = 0 (cs = invalid{})
THMinv13l_wfn:. s:state. p:PId. q,cv,cs:. inv13l{}(n; s; p; q; cv; cs)
ABSinv13minv13m{}(n; s; p; q; r; cv; cs) == prependR(q::r::retry{}::cv::cs::[]) buf[p]_ isP(r) (entering(s;r) maxrank_visiting(n;s;r)) hasrank(s;r) hasrank(s;p) rank(s;p) = rank(s;r) + 1 ((visiting(s;r) (q = r)) q = r)
THMinv13m_wfn:. s:state. p:PId. q,r,cv,cs:. inv13m{}(n; s; p; q; r; cv; cs)
ABSinv13ninv13n{}(s; p; q) == purgeQ(q::[]) buf[p]_ visiting(s;p) hasrank(s;p) hasrank(s;q) rank(s;q) = rank(s;p) + 1
THMinv13n_wfs:state. p:PId. q:. inv13n{}(s; p; q)
ABSinv13oinv13o{}(n; s; p; q; r) == purgeR(q::r::[]) buf[p]_ visiting(s;q) ((r = nil rank(s;p) = 0) (isP(r) hasrank(s;p) hasrank(s;r) rank(s;p) = rank(s;r) + 1 (isP(r) visiting(s;r))))
THMinv13o_wfn:. s:state. p:. q:PId. r:. inv13o{}(n; s; p; q; r)
ABSinv13pinv13p{}(n; s; p; q; cv; cs) == (pred-p_ = m staying(s;p) maxrank_staying(n;s;p)) (maxrank_staying(n;s;p) ((pred-p_ = m) (r:P. prependR(p::p::ok{}::cv::cs::[]) buf[r]_))) (prependR(q::m::cs::[]) buf[p]_ maxrank_staying(n;s;q))
THMinv13p_wfn:. s:state. p,q:PId. cv,cs:. inv13p{}(n; s; p; q; cv; cs)
ABSinv13qinv13q{}(n; s; p; q; r; cs) == ((cs-p_ = invalid{}) pred-p_ = m (r':P pred-p_ = r' ((cs-r'_ = invalid{}) smallrank(n;s;r';p)))) (visiting(s;q) delrightQ(q::r::cs::[]) buf[p]_ r = m (isP(r) (isP(r) cs-r_ = invalid{})) (isP(r) (isP(r) (cs-r_ = invalid{}) smallrank(n;s;r;q))))
THMinv13q_wfn:. s:state. p,q:PId. r,cs:. inv13q{}(n; s; p; q; r; cs)
DISPinv13all_dfinv13all(<n:n:*><s:s:*>)== inv13all(<n><s>)
ABSinv13allinv13all(n;s) == (p:P. q:P+m. r,cs:. inv13a{}(s; p; q; r; cs)) (p:P. inv13b{}(s; p)) inv13c{}(n; s) (p:P. inv13d{}(n; s; p)) (p,q:P. r:P+m. inv13e{}(n; s; p; q; r)) (p:P. q,cv:. arg: List. inv13f{}(n; s; p; q; cv; arg)) (p:P. inv13g{}(s; p)) (p:P. q:. inv13h{}(n; s; p; q)) (p:P. q:. inv13i{}(n; s; p; q)) (p:P+m. q:P. r,cv:. inv13j{}(s; p; q; r; cv)) (p,q,r:P. cv,cs:. inv13k{}(n; s; p; q; r; cv; cs)) (p:P. q,cv,cs:. inv13l{}(n; s; p; q; cv; cs)) (p:P. q,r,cv,cs:. inv13m{}(n; s; p; q; r; cv; cs)) (p,q:P. inv13n{}(s; p; q)) (p,q:P. r:. inv13o{}(n; s; p; q; r)) (p,q:P. r,cv:. inv13p{}(n; s; p; q; r; cv)) (p,q:P. r,cs:. inv13q{}(n; s; p; q; r; cs))
THMinv13all_wfn:. s:state. inv13all(n;s)
DISPinv13all_assump_dfinv13all_assump(<n:n:*><s:s:*>)== inv13all_assump(<n><s>)
ABSinv13all_assumpinv13all_assump(n;s) == (p,q:P. r:P+m. inv13_assump{}(s; p; q; r)) (p:P. q:P+m. r,cs:. inv13a{}(s; p; q; r; cs)) (p:P. inv13b{}(s; p)) inv13c{}(n; s) (p:P. inv13d{}(n; s; p)) (p,q:P. r:P+m. inv13e{}(n; s; p; q; r)) (p:P. q,cv:. arg: List. inv13f{}(n; s; p; q; cv; arg)) (p:P. inv13g{}(s; p)) (p:P. q:. inv13h{}(n; s; p; q)) (p:P. q:. inv13i{}(n; s; p; q)) (p:P+m. q:P. r,cv:. inv13j{}(s; p; q; r; cv)) (p,q,r:P. cv,cs:. inv13k{}(n; s; p; q; r; cv; cs)) (p:P. q,cv,cs:. inv13l{}(n; s; p; q; cv; cs)) (p:P. q,r,cv,cs:. inv13m{}(n; s; p; q; r; cv; cs)) (p,q:P. inv13n{}(s; p; q)) (p,q:P. r:. inv13o{}(n; s; p; q; r)) (p,q:P. r,cv:. inv13p{}(n; s; p; q; r; cv)) (p,q:P. r,cs:. inv13q{}(n; s; p; q; r; cs))
THMinv13all_assump_wfn:. s:state. inv13all_assump(n;s)
ABSinv13inv13{}(n; s) == (p:P. q:P+m. r,cs:. inv13a{}(s; p; q; r; cs)) (p:P. inv13b{}(s; p)) inv13c{}(n; s) (p:P. inv13d{}(n; s; p)) (p,q:P. r:P+m. inv13e{}(n; s; p; q; r)) (p:P. q,cv:. arg: List. inv13f{}(n; s; p; q; cv; arg)) (p:P. inv13g{}(s; p)) (p:P. q:. inv13h{}(n; s; p; q)) (p:P. q:. inv13i{}(n; s; p; q)) (p:P+m. q:P. r,cv:. inv13j{}(s; p; q; r; cv)) (p,q,r:P. cv,cs:. inv13k{}(n; s; p; q; r; cv; cs)) (p:P. q,cv,cs:. inv13l{}(n; s; p; q; cv; cs)) (p:P. q,r,cv,cs:. inv13m{}(n; s; p; q; r; cv; cs)) (p,q:P. inv13n{}(s; p; q)) (p,q:P. r:. inv13o{}(n; s; p; q; r)) (p,q:P. r,cv:. inv13p{}(n; s; p; q; r; cv))
THMinv13_wfn:. s:state. inv13{}(n; s)
THMdecidable__inbufs:state. M:mesg. p:. Dec(M buf[p]_)
THMdecidable__all_vprocn:. P:P . (x:P. Dec(P[x])) Dec(x:P. P[x])
THMdecidable__exists_vprocn:. P:P . (x:P. Dec(P[x])) Dec(x:P. P[x])
THMdecidable__hasranks:state. p:. Dec(hasrank(s;p))
THMdecidable__maxrankn:. s:state. p:. Dec(maxrank(n;s;p))
THMdecidable__stayings:state. p:PId. Dec(staying(s;p))
THMdecidable__maxrank_visitingn:. s:state. p:PId. Dec(maxrank_visiting(n;s;p))
THMdecidable__implies2P,Q:. Dec(P) (P Dec(Q)) Dec(implies2{}(P; Q))
THMdecidable__is_procp:. N:. Dec(isP(N,p))
THMdecidable__maxrank_stayingn:. s:state. p:PId. Dec(maxrank_staying(n;s;p))
THMdecidable__xorp,q:. Dec(p) Dec(q) Dec(p q)
THMdecidable__inv13as:state. p,q:PId. r,cs:. Dec(inv13a{}(s; p; q; r; cs))
THMdecidable__inv13bs:state. p:PId. Dec(inv13b{}(s; p))
THMdecidable__inv13cn:. s:state. Dec(inv13c{}(n; s))
THMdecidable__inv13dn:. s:state. p:PId. Dec(inv13d{}(n; s; p))
THMdecidable__inv13en:. s:state. p,q,r:PId. Dec(inv13e{}(n; s; p; q; r))
THMdecidable__inv13fn:. s:state. p,q,cv:. arg: List. Dec(inv13f{}(n; s; p; q; cv; arg))
THMdecidable__inv13gs:state. p:PId. Dec(inv13g{}(s; p))
THMdecidable__inv13hn:. s:state. p:PId. q:. Dec(inv13h{}(n; s; p; q))
THMdecidable__inv13in:. s:state. p:PId. q:. Dec(inv13i{}(n; s; p; q))
THMdecidable__inv13js:state. p,q:PId. r,cv:. Dec(inv13j{}(s; p; q; r; cv))
THMdecidable__inv13kn:. s:state. p,q,r:PId. cv,cs:. Dec(inv13k{}(n; s; p; q; r; cv; cs))
THMdecidable__inv13ln:. s:state. p:PId. q,cv,cs:. Dec(inv13l{}(n; s; p; q; cv; cs))
THMdecidable__inv13mn:. s:state. p:PId. q,r,cv,cs:. Dec(inv13m{}(n; s; p; q; r; cv; cs))
THMdecidable__inv13ns:state. p:PId. q:. Dec(inv13n{}(s; p; q))
THMdecidable__inv13on:. s:state. p:. q:PId. r:. Dec(inv13o{}(n; s; p; q; r))
THMdecidable__inv13pn:. s:state. p,q:PId. cv,cs:. Dec(inv13p{}(n; s; p; q; cv; cs))
THMdecidable__inv13qn:. s:state. p,q:PId. r,cs:. inv13q{}(n; s; p; q; r; cs)

the other theories