Uni e sal Ca as ophic Sa e y, Undecidabili y,
and Capabili y–Risk F on ie
in Compu a ional Uni e se
Haobo Ma1Wenlin Zhang2
1Independen Resea che
2Na ional Uni e si y o Singapo e
No embe 24, 2025
Abs ac
In p e ious axioma ic and geome ic se ies wo ks on “compu a ional uni e se”
Ucomp = (X, T,C,I), we ha e cons uc ed disc e e complexi y geome y, disc e e
in o ma ion geome y, con ol mani old (M, G) induced by uni ied ime scale, and
p oposed ime–in o ma ion–complexi y join a ia ional p inciple on join mani old
EQ=M × SQ, while p o ing equi alence be ween physical uni e se ca ego y and
e e sible QCA compu a ional uni e se ca ego y unde uni ied ime scale. Howe e ,
essen ial limi a ions ega ding “ca as ophic sa e y” and “capabili y– isk on ie ”
s ill lack uni ied compu a ional–geome ic–logical amewo k.
This pape p oposes wi hin compu a ional uni e se amewo k a “uni e sal
ca as ophic sa e y” heo y, connec ing i wi h undecidabili y and geome ic s uc-
u e o capabili y– isk on ie . We i s o malize ca as ophic sa e y as pa h p op-
e y: gi en ca as ophe se Cca ⊂X, so-called “uni e sal ca as ophic sa e y”
means uni e se e olu ion pa hs s a ing om all allowed ini ial s a es ne e en-
e Cca . Unde his se ing, we de ine uni e sal ca as ophic sa e y decision
p oblem, and p o e a compu a ional uni e se le el: his decision p oblem is un-
decidable in mos gene al case, i.e., he e exis s no algo i hm ha can gi e co ec
“ o e e sa e/possibly ca as ophic” e dic o all compu a ional uni e ses and
ca as ophe speci ica ions.
Second, we model ca as ophic sa e y and capabili y– isk duali y as wo ypes o
unc ionals on compu a ional uni e se: capabili y unc ional Cap e alua es success
p obabili y o pe o mance o ce ain asks, isk unc ional Risk e alua es p oba-
bili y o expec ed loss o eaching ca as ophe se Cca . We de ine capabili y– isk
on ie as Pa e o bounda y o all ealizable s a egy (Cap,Risk) pai s unde gi en
compu a ional uni e se and ask se , and unde cons ain s o uni ied ime scale
and complexi y geome y, cha ac e ize his on ie as class o “ eachable egion
bounda y” on con ol mani old (M, G) and s a egy space.
We u he p o e se e al key esul s: (1) Uni e sal ca as ophic sa e y e i i-
ca ion p oblem in compu a ional uni e se is a leas as ha d as hal ing p oblem,
hus undecidable; (2) Any algo i hmic sa e y il e a emp ing o be “co ec o
all s a egies”, i equi ed o e mina e and gi e e dic o all s a egies unde
uni ied ime scale, necessa ily p oduces una oidable “ alse nega i e/ alse posi i e
egions” on capabili y– isk plane; (3) Unde uni ied ime scale, geome ic op i-
miza ion p oblem o capabili y enhancemen and isk con ol can be w i en as
1
cons ained a ia ional p oblem on join mani old, whe e sa e y cons ain s na u-
ally o m non- ecu si ely sepa able eachable egion, hus capabili y– isk on ie
canno be algo i hmically comple ely compu ed in gene al case.
Finally, we connec undecidabili y o ca as ophic sa e y wi h p e ious opologi-
cal complexi y and causal diamond s uc u es: wi hin causal diamond, ca as ophe
condi ions can be iewed as local bounda y condi ions, bu when diamond scale
ends o in ini y, “whe he he e exis s some pa h iola ing ca as ophic sa e y”
co esponds o p oblem o whe he ce ain class o closed loops on con igu a ion
complex Xa e con ac ible, he eby inhe i ing p e iously es ablished opological
undecidabili y esul s. This pape p o ides sys ema ic ounda ion o subsequen
cons uc ion o “geome ic shape o capabili y– isk on ie ”, “ca as ophic sa e y
consensus geome y o mul i-agen sys ems”, and “sa e y–capabili y–undecidabili y
iangle ela ionship unde uni ied ime scale”.
Keywo ds: Compu a ional uni e se; Ca as ophic sa e y; Undecidabili y; Capabili y–
isk on ie ; Hal ing p oblem; Con ol mani old; Causal diamond
1 In oduc ion
In design and analysis o la ge complex sys ems (including ad anced a i icial in elli-
gence sys ems, inancial sys ems, nuclea acili ies, e c.), ca as ophic sa e y is one o
co e cons ain s: we hope sys em possesses high capabili y (i.e., excellen pe o mance
on a ge asks), while ca as ophic isk is ex emely low (e.g., no igge ing la ge-scale
i e e sible damage). T adi ional sa e y enginee ing mos ly conduc ed in speci ic models,
such as o mal e i ica ion on bounded s a e spaces, model checking, o s a ic analysis;
while adi ional compu a ion heo y e eals undecidabili y o “p og am p ope y deci-
sion” h ough hal ing p oblem, Rice’s heo em, e c.
In “compu a ional uni e se” amewo k, en i e uni e se abs ac ed as disc e e sys em
Ucomp = (X, T,C,I),
whe e Xis con igu a ion se , Tis local one-s ep upda e, Cis single-s ep cos unde
uni ied ime scale, Icha ac e izes ask in o ma ion quali y. Wi hin his amewo k, any
speci ic enginee ing sys em, agen , o dis ibu ed p o ocol can be iewed as some sub-
p ocess o Ucomp o local e olu ion o causal diamond. P e ious wo ks in his se ies ha e
es ablished:
Complexi y dis ance dcomp, olume g ow h Vx0(T), and disc e e Ricci cu a u e
κ(x, y);
Con ol mani old (M, G) induced by uni ied ime scale and geodesic dis ance dG;
Task in o ma ion mani old (SQ, gQ) and in o ma ion dis ance;
Time–in o ma ion–complexi y join a ia ional p inciple;
Equi alence o physical uni e se and compu a ional uni e se ca ego ies;
Topological cha ac e iza ion o opological complexi y, sel - e e en ial loops, and
undecidabili y.
2
Goal o his pape is o, on his ounda ion, uni y ca as ophic sa e y and capabili y–
isk duali y in o language o “compu a ional uni e se”, and gi e sys ema ic answe s o
ollowing ques ions:
1. How o o malize “uni e sal ca as ophic sa e y” in compu a ional uni e se?
2. Wha a e limi s o i s decision p oblem a logical and compu abili y le els?
3. How does geome ic s uc u e o capabili y enhancemen and isk con ol mani es
in con ol mani old and join a ia ional amewo k?
4. How is “non-algo i hmic sol abili y” o capabili y– isk on ie de i ed om unde-
cidabili y and opological complexi y?
We will see ha ca as ophic sa e y is undecidable in mos gene al case, capabili y–
isk on ie canno be algo i hmically comple ely compu ed unde uni ied ime scale, and
any p ac ical sa e y mechanism mus accep ce ain “incomple eness”: ei he ejec ing
some o iginally sa e and high-capabili y s a egies ( alse nega i es), o unable o p o e
exclusion o all ca as ophic isks (una oidabili y o alse posi i es).
Pape s uc u e as ollows: Sec ion 2 o malizes ca as ophic sa e y and capabili y–
isk duali y in compu a ional uni e se. Sec ion 3 gi es undecidabili y p oo o uni e sal
ca as ophic sa e y decision p oblem. Sec ion 4 cons uc s geome ic cha ac e iza ion
o capabili y– isk on ie , and analyzes limi s o algo i hmic sea ch o his on ie .
Sec ion 5 connec s ca as ophic sa e y wi h causal diamonds and opological complexi y.
Appendices gi e de ailed o maliza ions and p oo s o main heo ems.
2 Ca as ophe, Sa e y, and Capabili y–Risk Duali y
in Compu a ional Uni e se
This sec ion o malizes ca as ophe, sa e y speci ica ion, and capabili y– isk unc ionals
on compu a ional uni e se objec s.
2.1 Re iew o Compu a ional Uni e se and E olu ion Pa hs
Conside compu a ional uni e se objec
Ucomp = (X, T,C,I),
sa is ying p e ious axioms: Xcoun able, T⊂X×Xlocal wi h ini e deg ee, C
single-s ep cos posi i e and pa h-addi i e, I ask- ela ed in o ma ion quali y unc ion.
Fo any ini ial s a e x0∈X, an (in ini e) e olu ion pa h is sequence
Γ=(x0, x1, x2, . . . ),(xk, xk+1)∈T.
I conside ing uni ied ime scale, hen o each s ep (xk, xk+1) accumula e cos
C(Γ|[0,n]) =
n−1
X
k=0
C(xk, xk+1),
iewable as physical ime up o s ep n.
3
2.2 Ca as ophe Se and Ca as ophe Speci ica ion
De ini ion 2.1 (Ca as ophe Se ).Ca as ophe se Cca ⊂Xis subse o con igu a-
ion space, ep esen ing “once uni e se con igu a ion en e s i , iewed as ca as ophe
occu ed” s a es. Speci ic examples include: sys em un eco e able aul s a es, global
i e e sible damage s a es, s a es iola ing ha d cons ain s, e c.
In many cases, ca as ophe se i sel is de ining esul o some p ope y, no di ec ly
gi en explici se . We allow Cca desc ibed by p edica e
Ca :X→ { ue, alse}, Cca ={x∈X:Ca (x) = ue}
This p edica e can be ope a o p ope y (e.g., “some ope a o spec al adius exceeds
h eshold”), in o ma ion p ope y (e.g., “in o ma ion leaked o sensi i e subsys em”), o
combina o ial p ope y.
De ini ion 2.2 (Ca as ophe Speci ica ion).Ca as ophe speci ica ion is pai
Nca = (X0, Cca ),
whe e X0⊂Xis allowed ini ial s a e se (e.g., accep able p e-deploymen s a e space),
Cca ⊂Xis ca as ophe se .
We will conside eachabili y o all e olu ion pa hs s a ing om X0 o ca as ophe
se .
2.3 Uni e sal Ca as ophic Sa e y
De ini ion 2.3 (Uni e sal Ca as ophic Sa e y).Gi en compu a ional uni e se Ucomp and
ca as ophe speci ica ion Nca = (X0, Cca ), call (Ucomp,Nca ) uni e sally ca as ophically
sa e, i o any ini ial s a e x0∈X0and any e olu ion pa h Γ = (x0, x1, . . . ) sa is ying
(xk, xk+1)∈T, we ha e
∀k≥0, xk/∈Cca .
O he wise call he e exis s ca as ophic pa h, i.e., he e exis s some pa h en e ing Cca
in ini e-s ep ime.
This p ope y is pa h-le el “ne e ouch” p ope y, ypical sa e y a ibu e.
2.4 Capabili y and Risk Func ionals
Unde uni ied ime scale and ask in o ma ion geome y, we de ine capabili y and isk as
wo dual unc ionals on e olu ion pa hs.
Le ask Qbe ep esen ed by some goal se GQ⊂Xo goal unc ion UQ:X→R.
De ini ion 2.4 (Capabili y Func ional).Fo gi en s a egy o con ol ule π(abs ac ed
as mechanism selec ing nex -s ep upda e om local in o ma ion a each s ep), le Pπ
x0
ep esen pa h dis ibu ion s a ing om ini ial s a e x0. Capabili y unc ional de ined
as
Cap(π) = in
x0∈X0
EΓ∼Pπ
x0UQ(Γ),
4
whe e UQ(Γ) can be e minal ewa d, cumula i e ewa d, o some unc ion o in o -
ma ion quali y. Fo example, o decision asks, can ake UQ(Γ) as “decision co ec ”
indica o .
De ini ion 2.5 (Risk Func ional).Fo same s a egy π, isk unc ional is
Risk(π) = sup
x0∈X0
PΓ∼Pπ
x0∃k≥0, xk∈Cca .
High capabili y means excellen pe o mance on asks, low isk means ca as ophe se
di icul o ouch. Ex eme uni e sal ca as ophic sa e y co esponds o Risk(π) = 0 and
sys em essen ially sa e.
Unde uni ied ime scale, we can also conside capabili y and isk condi ioned wi hin
ime budge T, e.g.,
RiskT(π) = sup
x0∈X0
P∃k, C(Γ|[0,k])≤T, xk∈Cca .
This pape mainly ocuses on concep ual s uc u e unde in ini e ime pe spec i e.
3 Undecidabili y o Uni e sal Ca as ophic Sa e y De-
cision
This sec ion de ines uni e sal ca as ophic sa e y decision p oblem, and p o es i s unde-
cidabili y a compu a ional uni e se le el.
3.1 Uni e sal Ca as ophic Sa e y Decision P oblem
P oblem 3.1 (Uni e sal Ca as ophic Sa e y Decision). Inpu : (1) Fini e desc ip ion
o compu a ional uni e se Ucomp = (X, T,C,I) (e.g., gi en by ini e s a e ansi ion ules
o QCA ules); (2) Fini e desc ip ion o ca as ophe speci ica ion Nca = (X0, Cca ) (e.g.,
gi en by p edica e o au oma on).
Ou pu : Decide whe he (Ucomp,Nca ) is uni e sally ca as ophically sa e.
We will conside whe he such decision p ocess has global algo i hm: o all inpu s
gi ing co ec Yes/No answe in ini e ime.
3.2 Reduc ion om Hal ing P oblem o Ca as ophic Sa e y
S anda d s a emen o hal ing p oblem is: gi en p og am–inpu pai (P, w), decide
whe he p og am Phal s in ini e s eps on inpu w. We know his p oblem is unde-
cidable.
Wi hin compu a ional uni e se amewo k, we can embed simula ion o uni e sal Tu -
ing machine o uni e sal CA/QCA in o con igu a ion g aph. Below we cons uc educ-
ion om hal ing p oblem o uni e sal ca as ophic sa e y decision.
Cons uc ion Idea
Gi en (P, w), cons uc ollowing compu a ional uni e se and ca as ophe speci ica-
ion:
1. Le basic compu a ional uni e se UTM
comp simula e uni e sal Tu ing machine, whose
con igu a ion space Xcon ains “machine s a e + ape con en ” encoding.
5
2. Fo gi en (P, w), de ine ini ial s a e se X0={xini (P, w)}, i.e., unique ini ial s a e
is machine’s ini ial con igu a ion unde p og am Pand inpu w.
3. De ine ca as ophe se Cca as special ma king s a e se eached a e simula ion
hal ing s a e eached hen passing h ough ixed-leng h upda e. Fo example:
When Tu ing machine hal s, en e hal ing s a e qhal ;
Then h ough ini e-s ep ansi ion en e ma king s a e xbad ∈Cca ;
I Tu ing machine ne e hal s, hen pa h ne e en e s Cca .
Unde his cons uc ion, ha e:
I P(w) hal s, hen he e exis s pa h s a ing om xini (P, w) en e ing Cca in ini e
s eps, hus (UTM
comp,N(P,w)
ca ) no uni e sally ca as ophically sa e;
I P(w) does no hal , hen o all pa hs ne e en e Cca (assuming compu a ional
uni e se has no ex e nal noise pe u ba ion), he e o e (UTM
comp,N(P,w)
ca ) uni e sally
ca as ophically sa e.
Thus hal ing p oblem educible o uni e sal ca as ophic sa e y decision.
3.3 Undecidabili y Theo em
Theo em 3.2 (Undecidabili y o Uni e sal Ca as ophic Sa e y).The e does no ex-
is global algo i hm Sa eDecide, o all compu a ional uni e se ini e desc ip ions Ucomp
and ca as ophe speci ica ions Nca as inpu s, always ou pu ing co ec decision alue
{“uni e sally ca as ophically sa e”,“ca as ophic pa h exis s”}in ini e ime.
P oo (Ou line). Assume he e exis s such algo i hm Sa eDecide. Fo any p og am–inpu
pai (P, w), acco ding o p e ious sec ion cons uc ion cons uc (UTM
comp,N(P,w)
ca ). Run
Sa eDecideUTM
comp,N(P,w)
ca
I ou pu s “uni e sally ca as ophically sa e”, hen P(w) does no hal ; i ou pu s
“ca as ophic pa h exis s”, hen P(w) hal s. Thus ob ain decision algo i hm o hal ing
p oblem, con adic ion.
The e o e assump ion does no hold, uni e sal ca as ophic sa e y decision p oblem is
undecidable.
Q.E.D.
3.4 Hie a chy and S onge Undecidabili y
Abo e p oo shows uni e sal ca as ophic sa e y is a leas equi alen o hal ing p oblem.
I u he conside ing andomness, in e ac ion, and ime-unbounded beha io s, co e-
sponding “ca as ophe possibili y” can be encoded as ce ain ope a o o pa h hype -
p ope ies, whose logical complexi y can ele a e o highe classes in a i hme ic o ana-
ly ical hie a chy. In such cases, uni e sal ca as ophic sa e y decision p oblem can e en
each comple eness o highe hie a chy classes.
This pape does no pu sue p ecise hie a chy, only cha ac e izes “undecidabili y” as
undamen al obs acle o ca as ophic sa e y e i ica ion.
6
4 Geome ic Cha ac e iza ion and Non-Algo i hmic
Sol abili y o Capabili y–Risk F on ie
This sec ion gi es geome ic cha ac e iza ion o capabili y– isk on ie unde uni ied ime
scale and complexi y geome y, and analyzes limi s o i s algo i hmic sol abili y.
4.1 S a egy Space and Con ol Mani old
In p e ious con ol mani old (M, G) cons uc ion, each con ol pa ame e θ∈ M co -
esponds o some physically ealizable con ol con igu a ion o s a egy p o o ype. In
mul i-s ep e olu ion, con ol pa h θ( ) co esponds o some dynamic s a egy amily. Fo
simpli ica ion, we i s abs ac s a egy space a disc e e le el as some se Π, each π∈Π
de ines ule om local obse a ion o nex -s ep upda e, cons ained by uni ied ime scale
and complexi y budge .
Can u he embed Π in o some pa ame e submani old MΠ⊂ M o con ol mani old,
such ha each s a egy πco esponds o one o amily o con ol pa hs. This pape
concep ually does no dis inguish Π om MΠ.
4.2 De ini ion o Capabili y–Risk F on ie
De ini ion 4.1 (Capabili y–Risk Pai ).Fo each s a egy π∈Π, de ine i s capabili y–
isk pai as
(Cap(π),Risk(π)) ∈R×[0,1].
De ini ion 4.2 (Realizable Capabili y–Risk Se ).Realizable capabili y– isk se is
RCR ={(Cap(π),Risk(π)) : π∈Π} ⊂ R×[0,1].
De ini ion 4.3 (Capabili y–Risk F on ie ).Capabili y– isk on ie FCR ⊂ RCR is se o
all Pa e o op imal poin s:
(Cap,Risk) ∈ FCR
i and only i he e does no exis ano he s a egy π′sa is ying
Cap(π′)≥Cap,Risk(π′)≤Risk,
wi h a leas one inequali y s ic .
In ui i ely, poin s on on ie co espond o class o “capabili y– isk adeo ” limi s,
any a emp o enhance capabili y o educe isk mus sac i ice o he side.
4.3 Geome ic Embedding o F on ie
On con ol mani old (M, G), we can ep esen s a egies as poin s o pa h amilies, wi h
capabili y and isk as wo unc ionals
Cap : MΠ→R,Risk : MΠ→[0,1].
7
Unde uni ied ime scale and a ia ional p inciple, we can w i e “maximize capabili y
unde gi en isk cons ain ” as cons ained op imiza ion p oblem:
max
π∈ΠCap(π) subjec o Risk(π)≤ 0.
Geome ically, his co esponds o sol ing ex emal p oblem sa is ying inequali y con-
s ain on MΠ, whose Lag angian unc ion is
L(θ, λ) = −Cap(θ) + λ(Risk(θ)− 0), λ ≥0.
I s ex emal poin s sa is y
∇Cap(θ∗) = λ∗∇Risk(θ∗),Risk(θ∗) = 0,
his is s anda d i s -o de condi ion o geome ically “ on ie ” poin s. In mul i-
dimensional case, his condi ion cha ac e izes no mal s uc u e o on ie on con ol
mani old.
4.4 Logical Roo s o Non-Algo i hmic Sol abili y o F on ie
Howe e , e en hough on ie appea s geome ically benign, a compu abili y le el, “gi -
ing sa e high-capabili y s a egy on on ie ” s ill canno be algo i hmically comple ed.
In ui i e eason is: i he e exis s algo i hm F on ie Sea ch capable o gene a ing poin
π∗on on ie o any compu a ional uni e se and ca as ophe speci ica ion (e.g., high-
capabili y s a egy wi h isk below some h eshold), hen we can use i o indi ec ly sol e
uni e sal ca as ophic sa e y decision p oblem.
Theo em 4.4 (Non-Algo i hmici y o Comple e F on ie Solu ion).The e does no exis
global algo i hm F on ie Sea ch, o all inpu s (Ucomp,Nca , Q)ou pu ing s a egy πin
ini e ime, sa is ying:
1. π’s capabili y on ask Q eaches some ixed h eshold Cap(π)≥c0(e.g., non- i ial
capabili y);
2. Risk(π) = 0 (uni e sally ca as ophically sa e);
3. I he e exis s any uni e sally ca as ophically sa e s a egy wi h capabili y a leas
c0, hen F on ie Sea ch mus ou pu one o hem.
P oo (Ou line). I F on ie Sea ch exis s, hen o p e iously cons uc ed ins ance om
hal ing p oblem (UTM
comp,N(P,w)
ca , Q0) (whe e ask Q0can be “success ully simula e one
p og am–inpu pai e olu ion”), ha e:
I P(w) does no hal , hen sys em uni e sally ca as ophically sa e, he e exis s
“ca as ophe- ee s a egy wi h non- i ial capabili y”;
I P(w) hal s, hen any s a egy eaching capabili y c0necessa ily has non-ze o
ca as ophic isk (because o simula e comple e p og am, mus igge ca as ophe
ma king).
Assuming F on ie Sea ch sa is ies condi ions, hen
8
In non-hal ing case, F on ie Sea ch mus ou pu some s a egy wi h Risk(π) =
0,Cap(π)≥c0;
In hal ing case, he e does no exis s a egy sa is ying condi ions, algo i hm nec-
essa ily canno ou pu answe sa is ying condi ions (ei he does no e mina e, o
iola es comple eness).
By moni o ing ou pu beha io o F on ie Sea ch, we can decide whe he P(w) hal s,
hus con adic ion. The e o e comple e on ie sea ch algo i hm does no exis .
Q.E.D.
This heo em shows: unde mos gene al compu a ional uni e se se ing, capabili y–
isk on ie as global objec canno be algo i hmically comple ely compu ed, any p ac-
ical me hod can only gi e app oxima e on ie o conse a i e es ima e wi hin some
es ic ed class.
5 Causal Diamonds, Topological Complexi y, and Lo-
cal Sa e y Ve i ica ion
This sec ion connec s ca as ophic sa e y wi h p e iously in oduced causal diamonds,
bounda y compu a ion, and opological complexi y, discussing possibili ies and limi s o
local sa e y e i ica ion.
5.1 Ca as ophic Sa e y in Local Causal Diamonds
In p e ious causal diamond heo y, we in oduce o e en laye E=X×Ncomplexi y
ligh cone and causal diamond
♢(ein, eou ;T) = J+
T(ein)∩J−
T(eou ),
whose in e nal e olu ion can be comp essed-encoded by bounda y ope a o K♢:B−
♢→
B+
♢.
F om ca as ophic sa e y pe spec i e, we mo e ca e abou : whe he he e exis s some
pa h en e ing Cca inside diamond. I diamond scale is ini e, hen his decision can in
p inciple be comple ed h ough exhaus ion o symbolic analysis (i s complexi y can be
e y high, bu a leas is ini e p ocess). This co esponds o local sa e y e i ica ion:
e i ying “local ca as ophe un eachable” wi hin ini e ime–space window.
5.2 Diamond Gluing and Global Undecidabili y
Howe e o e all ca as ophic sa e y is no p ope y o some single diamond, bu join
p ope y o all possible diamonds: i.e., whe he he e exis s some ein, eou , T, such ha
pa hs inside diamond can each Cca . This equi alen o seeking on con igu a ion complex
some class o pa h sys ems con aining ca as ophe s a es, whose opological s uc u e
closely ela ed o p e ious closed loop undecidabili y.
In p e ious opological complexi y pape we p o ed: in gene al cons uc ible compu-
a ional uni e se amilies, deciding whe he ce ain class o closed pa hs a e con ac ible
is undecidable. Encoding ca as ophic sa e y as “whe he he e exis s some closed pa h
9
