Universal Catastrophic Safety Undecidability and Capability--Risk Upper Bound Frontier: Unified Theorems, Complexity Positioning, and Engineering Pathways

Uni e sal Ca as ophic Sa e y Undecidabili y and Capabili yRisk
Uppe Bound F on ie : Unied Theo ems, Complexi y
Posi ioning, and Enginee ing Pa hways
Haobo Ma
1
Wenlin Zhang
2
1
Independen Resea che
2
Na ional Uni e si y o Singapo e
Abs ac
Es ablish wo ounda ional bounda ies o gene al lea ning and decision sys ems. Fi s , p o-
ide ca as ophic sa e y de e mina ion undecidabili y o in e ac i e agen en i onmen sys ems:
unde ex emely weak modeling assump ions, o any ex ension-closed egula bad-p ex speci-
ca ion, whe he h eshold sa e y sa ised admi s no global algo i hm; unde es ic ed subclass
o de e minis ic en i onmen s and compu able s a egies, u he posi ion as
Σ0
1
-comple e/
Π0
1
-
comple e
. Second, p o ide
capabili ywo s - isk uppe bound on ie
induced by join
PAC-Bayes high-p obabili y bound, mu ual in o ma ion expec ed bound, and Wasse s ein-1
dis ibu ionally obus op imiza ion (Kan o o ichRubins ein duali y); ia poin pe u ba ion
ad e sa y es ablish uni e sal
geome ic lowe bound
, oge he wi h obus accu acy im-
possibili y and obus gene aliza ion sample complexi y lowe bound, o ming "uppe bound
lowe bound" dual suppo . The eby p opose "scope es ic ion un ime shielding isk budge 
s uc u al p io " go e nance bluep in , p o iding minimal ep oducible ImageNe -C + Shield
expe imen al skele on and me ic congu a ion.
Keywo ds
: Hal ing; Rice heo em;
Σ0
1
-comple e; POMDP; PAC-Bayes; condi ional mu ual
in o ma ion; Wasse s ein-DRO; Kan o o ichRubins ein duali y; ad e sa ial obus ness; un ime
shield; in e up ibili y
1 In oduc ion & His o ical Con ex
Algo i hmic decidabili y and p og am seman ics e eal undamen al limi s o uni e sal e ica ion:
hal ing p oblem undecidable, Rice heo em s a es any non- i ial seman ic p ope y undecidable.
T ansplan ing his idea o in e ac i e agen en i onmen se ing, ob ain gene al de e mina ion un-
a ailabili y o "whe he igge ing ca as ophic specica ion". This di ec ion esona es wi h unde-
cidabili y esul s o inni e-ho izon p obabilis ic planning/pa ially obse able decision a h eshold
and plan exis ence. On he o he hand, mode n lea ning heo y e eals capabili y and obus ness
canno ad ance wi hou cos : PAC-Bayes and mu ual in o ma ion pa adigm cha ac e ize com-
plexi y/in o ma ion amoun inuence on gene aliza ion, Wasse s ein-DRO cha ac e izes wo s - isk
unde dis ibu ion shi ; simul aneously, obus accu acy impossibili y and obus gene aliza ion
sample complexi y lowe bound igo ously p o en in na u al model amilies. Two bounda ies join ly
poin owa d go e nance p inciples: acknowledging gene al s a ic ce ica ion impossibili y and
capabili y isk ha d ade-o, adop laye ed scheme o scope es ic ion, un ime shielding, and isk
budge .
1
2 Model & Assump ions
2.1 In e ac ion Seman ics and Tempo al Assump ions

Ac ion and obse a ion alphabe s
A,O
ni e; his o y
h1: ∈(A×O)
.

Compu able policy
: Agen
A
is unc ion
A: (A × O)⋆→ A
, o any
h<
exis s ni e
ime p oducing
a =A(h< )
a s ep
(allowing in e nal andomiza ion ia sampling p o-
g am implemen a ion). This assump ion sa ised h oughou undecidabili y cons uc ion and
comple eness posi ioning.

En i onmen
E
specied by his o y condi ional p obabili y
µ(o |h< , a )
. Main esul s use
de e minis ic i ial en i onmen
E0
: always e u ns xed obse a ion
o⊥
.
2.2 Sa e y P ope y and Regula Bad P ex

Le
Σ=(A×O)⋆
. Call
B⊆Σ
bad p ex language
i o any
u∈B
and any ex ension
∈Σ
, ha e
u ∈B
(
ex ension-closed
). Co esponding
sa e p ex se
S= Σ B
hen
p ex-closed
.

Specica ion adop s
egula bad p ex language
B
(equi alen o sa e p ex ecognized
by DFA/sa e y au oma on). Viola ion e en
Bad ={∃ :h1: ∈B}, τ(h) = in { :h1: ∈B}.

Th eshold sa e y p edica e
: Gi en
ε∈[0,1)
,
Sa eε(A, E, B) := P
µ(Bad)≤ε.
2.3 Lea ningE alua ion and Dis ibu ional Robus ness

Da a domain
Z
wi h me ic
d
; sample
S= (Zi)n
i=1 ∼Dn
.

Lea ning algo i hm ou pu s pos e io
QS∈ P(H)
. Loss
ℓ:H × Z → [0,1]
.

Lipschi z assump ion
: Exis s uni o m cons an
L > 0
such ha o any
h∈ H
, mapping
z7→ ℓ(h, z)
is
L
-Lipschi z wi h espec o
d
(0-1 loss no applicable, adop smoo h su oga es
like c oss-en opy/hinge; con ollable ia spec al no m cons ain and g adien clipping).

Wasse s ein-1 ball
Bρ(D) = {D′:W1(D′, D)≤ρ}
; obus isk
R ob
ρ(Q) := sup
D′∈Bρ(D)
Eh∼Q,z∼D′[ℓ(h, z)].
3 Main Resul s (Theo ems and Alignmen s)
Theo em 1
(1: Uni e sal Ca as ophic Sa e y De e mina ion Undecidable)
.
Exis s egula bad
p ex amily
B
such ha no algo i hm can de e mine o all compu able policies
A
, compu able
en i onmen s
E
,
B∈B
, and any a ional
ε∈[0,1)
he u h alue o
Sa eε(A, E, B)
.
2
Theo em 2
(1': Complexi y Posi ioning o Res ic ed Subclass)
.
Unde de e minis ic en i onmen
E0
and compu able policy class, le
UNSAFE
={(A, E0, B, ε) : P (Bad)> ε}, ε < 1.
Then UNSAFE is
Σ0
1
-comple e
, i s complemen SAFE is
Π0
1
-comple e
. In his subclass
P (Bad)∈
{0,1}
, hus "
P (Bad)> ε
" equi alen o "occu ence" o any
ε < 1
.
Theo em 3
(2: Capabili yWo s Risk Uppe Bound F on ie : PAC-Bayes + KR)
.
Fo any p io
P
and
δ∈(0,1)
, wi h p obabili y a leas
1−δ
(o e
S∼Dn
) ha e
R ob
ρ(Q)≤b
RS(Q) + KL(Q∥P) + ln(1/δ)
2n+Lρ.
Righ -hand h ee e ms espec i ely empi ical e o , complexi y/condence e m, and dis ibu ion
shi linea penal y, cons i u ing
uppe bound induced capabili y isk on ie
.
Theo em 4
(2': High-P obabili y Mu ual In o ma ion Bound: Pa adigma ic S a emen )
.
Le loss
ℓ∈[0,1]
wi h sub-Gaussian cons an
σ
o each sample poin . I lea ning algo i hm sa ises
condi-
ional mu ual in o ma ion
uppe bound
CMI(S;QS)≤Γ
o equi alen s eng h uni o m s abili y,
hen exis s cons an
c > 0
such ha o any
δ∈(0,1)
,
P RD(QS)≤b
RS(QS) + 2σ2(Γ + cln(1/δ))
n!≥1−δ.
Jux aposing (2) wi h (1), ob ain high-p obabili y
on ie
exp ession o da a-dependen pos e-
io : ake smalle o wo igh -hand sides as ope a ional uppe bound o capabili y isk cu e.
Theo em 5
(3: Poin Pe u ba ion Geome ic Lowe Bound and Dis ibu ion Ball Inclusion)
.
Fo
any classie
and
ρ > 0
, dene
Rad
ρ( ) = P
(z,y)∼D∃z′∈Bρ(z) : (z′)=y,
whe e
Bρ(z) = {z′:d(z, z′)≤ρ}
wi h label p ese ing. Then
sup
D′∈Bρ(D)
RD′( )≥ Rad
ρ( ).
(3) holds on any me ic and ask, p o iding uni e sal lowe bound " ounda ion" ma ching (1).
Unde Gaussian mix u es and
ℓp
pe u ba ions, exis cons uc i e lowe bounds o obus accu acy
impossibili y and obus gene aliza ion sample complexi y lowe bound.
P oposi ion 6
(1: Tigh ness o KR Linea Te m)
.
Fo any
L, ρ > 0
and me ic space, exis s
L
-Lipschi z unc ion
and dis ibu ion pai
(D, D′)
such ha
W1(D′, D) = ρ
and
sup
W1(D′,D)≤ρ
ED′[ ]−ED[ ] = Lρ.
Indica es  s -o de o m
Lρ
canno be imp o ed unde uni o m Lipschi z cons an condi ion.
3
4 P oo s
4.1 Theo em 1 (Undecidabili y)
Take i ial en i onmen
E0
. Gi en Tu ing machineinpu pai
⟨M, x⟩
, cons uc compu able policy
AM,x(h< ) = (a⋆,
i
M(x)
hal s wi hin
s eps
,
a0,
o he wise
.
Le bad p ex language
B={h:
some s ep ac ion is
a⋆}
, egula and ex ension-closed. Then
P (Bad) = 1{M(x)
hal s
}.
I uni e sal decide exis s de e mining
Sa eε(A, E, B)
u h/ alsi y o any inpu (
ε < 1
), ob ain
hal ing de e mina ion, con adic ion. P o ed.
4.2 Theo em 1' (
Σ0
1/Π0
1
Comple e)
Many-one educ ion
: Mapping
R:⟨M, x⟩ 7→ (AM,x, E0, B, ε)
polynomial- ime compu able, and
⟨M, x⟩ ∈
HALT
⇐⇒ (AM,x, E0, B, ε)∈
UNSAFE (
ε < 1
).
Membe ship
: Unde
E0
and
de e minis ic
A
,
P (Bad)∈ {0,1}
. I unsa e, exis s minimal
τ
making
h1:τ∈B
, enume a e o
his p ex accep s, hus UNSAFE
∈Σ0
1
, complemen in
Π0
1
. Combining wi h educ ion ob ains
comple eness. P o ed.
4.3 Theo em 2 (Uppe Bound F on ie )
PAC-Bayes (McAlles e /Ca oni a ian ) p o ides
RD(Q)≤b
RS(Q) + KL(Q∥P) + ln(1/δ)
2n(
wi h p obabili y
≥1−δ).
KR duali y indica es o any
L
-Lipschi z unc ion
g
,
sup
W1(D′,D)≤ρ
ED′[g]≤ED[g] + Lρ.
Applying o
g(z) = Eh∼Qℓ(h, z)
yields (1). P o ed.
4.4 Theo em 2' (High-P obabili y Mu ual In o ma ion)
Le
ℓ
bounded wi h each poin
σ
-sub-Gaussian. I algo i hm sa ises
CMI(S;QS)≤Γ
, hen ia
in o ma ion comp ession and a ia ional inequali y ob ain
P RD(QS)−b
RS(QS)≤q2σ2(Γ+cln(1/δ))
n≥1−δ,
whe e cons an
c
gi en by ail con ol. Jux aposing wi h (1) ob ains on ie high-p obabili y
o m. P o ed.
4
4.5 Theo em 3 (Poin Pe u ba ion Lowe Bound)
Fo any measu able selec ion ope a o
T:Z → Z
wi h
d(z, T(z)) ≤ρ
almos su ely, le
D′=
(T, y)#D
. Taking coupling
π(dz, dz′) = D(dz)δT(z)(dz′)
, hen
Eπd(Z, Z′)≤ρ
; hus
W1(D′, D)≤ρ
.
I
(T(z)) =y
hen e s unde
D′
, u he
sup
D′∈Bρ(D)
RD′( )≥ED1{∃z′∈Bρ(z) : (z′)=y}=Rad
ρ( ).
P o ed.
4.6 P oposi ion 1 (Tigh ness)
Take
D=δ0, D′=δρu
and
(z) = L|z|2
yields esul . P o ed.
5 Model Apply

Au onomous con ol and ool-using agen s
: Theo em 1 ules ou gene al s a ic ce i-
ca ion, ecommend es ic ing policy space and in e aces o e iable sublanguages; du ing
deploymen supp ess ansg ession ia shields and in e up ible p o ocols.

Pe cep iondecision sys ems
: Acco ding o (1)(2) es ablish
isk budge
: unde gi en
(n, ρ)
enhancing capabili y (la ge model/weake p io ) equi es co espondingly inc eased
sample size, enhanced s uc u al p io , o comp essed
L
.

E alua ion and calib a ion
: Adop co up ion and pe u ba ion benchma ks (e.g., ImageNe -
C) and unce ain y measu es (NLL/ECE), join ly " iola ion a e ask accu acy" dual-axis
cu es exhibi ing "capabili y isk on ie " and shield in e cep ion eec i eness.
6 Enginee ing P oposals
1.
Scope es ic ion
: Design policy and ool in oca ion ia e iable subse s ( es ic ed DSL/in e aces),
ensu ing sa e y specica ions implemen ed by online disc imina ion ia DFA/LTL syn hesis
sa e p ex ecognize s.
2.
Run ime shield
: Syn hesize p e-/pos -shields ia LTL
→
DFA
→
sa e y au oma on gene a o ;
p e-shield l e s unsa e ac ion se , pos -shield eplaces wi h nea by sa e ac ion ia minimal
co ec ion p inciple; p obabilis ic shield con ols alse ejec ion/ alse nega i e ia condence
h eshold.
3.
Risk budge
: T ea
(b
RS,KL, I, ρ, L)
as budge quin uple; congu e "da ap io shi Lipschi z"
balancing s a egy espec i ely du ing de elopmen and deploymen phases.
4.
S uc u al p io and impac egula iza ion
: Adop equi a ian s uc u es, spec al no m
cons ain s, and e e sibili y penal ies (AUP) educing complexi y and side-eec p opensi y.
5.
Dis ibu ionally obus aining and unce ain y go e nance
: Combine Wasse s ein-
DRO/ad e sa ial aining wi h deep ensembles, empe a u e calib a ion; handle high unce -
ain y ia ejec iondeg ada ionhando open-loop s a egy.
6.
In e up ibili y
: Embed unbiased in e up ible p o ocols in upda ing and explo a ion, p e-
en ing policy lea ning incen i es o ci cum en in e en ion.
5

7 Discussion (Risks, Bounda ies, Pas Wo k)

Bounda y meaning
: Undecidabili y nega es "gene al, global, one- ime" s a ic p oo ; un-
de es ic ed model amilies (ni e ho izon, ully obse able, discoun ed MDP, e c.) s ong
gua an ees s ill ob ainable.

Uppe boundlowe bound enclosu e
: KR linea e m wi h PAC-Bayes/mu ual in o ma-
ion p o ide ope a ional uppe bounds; poin pe u ba ion lowe bound wi h obus accu acy
impossibili y, obus gene aliza ion sample complexi y lowe bound indica e "ze o-cos bo h"
una ainable no a i ac o loose analysis.

Rela ionship wi h exis ing wo k
: Theo em 1 equi alen o Rice/hal ing, complemen s
inni e-ho izon p obabilis ic planning undecidabili y; Theo em 2 consis en wi h dis ibu-
ionally obus op imiza ion, PAC-Bayes, mu ual in o ma ion pa adigm; Theo em 3 ma ches
cons uc i e lowe bounds and sample complexi y lowe bounds in ad e sa ial obus ness li -
e a u e; shields and in e up ibili y co espond o un ime en o cemen sys ems in sa e ein-
o cemen lea ning and o mal me hods.
8 Conclusion
Gene al ca as ophic sa e y de e mina ion una ainable in p inciple, capabili y enhancemen and
obus ness admi ha d ade-o join ly d i en by complexi y/in o ma ion amoun and dis ibu ion
shi . Based on his, go e nance schemes should cen e on scope es ic ion, un ime shielding,
and isk budge , p o ing wi hin e iable subdomain, backs opping ia shields and in e up ibili y
du ing deploymen , supp essing shi isk ia s uc u al p io and dis ibu ionally obus echniques
du ing aining.
Acknowledgemen s, Code A ailabili y
Thank ela ed esea ch in decidabili y, dis ibu ionally obus op imiza ion, in o ma ion- heo e ic
gene aliza ion, and sa e ein o cemen lea ning elds. Code and da a no accompanying pape ;
minimal ep oducible expe imen sugges ion: based on public co up ion benchma ks, LTL
→
DFA
ools, and ad e sa ial/ obus aining lib a ies ep oduce " isk budge cu e iola ion a e" dual-
axis diag am; eposi o y should include da a sc ip s, specica ion examples, aining/in e ence and
shield modules, hype pa ame e ables, and one-click sc ip s.
Re e ences
Tu ing, A. M. (1936). On Compu able Numbe s, wi h an Applica ion o he En scheidungsp oblem.
Rice, H. G. (1953). Classes o Recu si ely Enume able Se s and Thei Decision P oblems.
Madani, O., Hanks, S., Condon, A. (1999). On he Undecidabili y o P obabilis ic Planning and
Inni e-Ho izon POMDPs.
McAlles e , D. (1999). Some PAC-Bayesian Theo ems.
Ca oni, O. (2007). PAC-Bayesian Supe ised Classica ion.
Alquie , P. (2021). Use - iendly In oduc ion o PAC-Bayes Bounds.
Xu, A., Raginsky, M. (2017). In o ma ion-Theo e ic Analysis o Gene aliza ion Capabili y o
Lea ning Algo i hms.
6
S einke, T., Zakyn hinou, L. (2020). Reasoning abou Gene aliza ion ia Condi ional Mu ual
In o ma ion.
Bu, Y., Zou, S., Vee a alli, V. V. (2020). Tigh ening Mu ual In o ma ion-Based Bounds on
Gene aliza ion E o .
Villani, C. (2009). Op imal T anspo : Old and New.
Es ahani, P. M., Kuhn, D. (2018). Da a-D i en Dis ibu ionally Robus Op imiza ion Using he
Wasse s ein Me ic.
Sinha, A., Namkoong, H., Duchi, J. (2018). Ce i ying Some Dis ibu ional Robus ness wi h
P incipled Ad e sa ial T aining.
Tsip as, D., San u ka , S., Engs om, L., Tu ne , A., Mad y, A. (2019). Robus ness May Be a
Odds wi h Accu acy.
Schmid , L., e al. (2018). Ad e sa ially Robus Gene aliza ion Requi es Mo e Da a.
Alshiekh, M., e al. (2018). Sa e Rein o cemen Lea ning ia Shielding.
Koenigho e , B., e al. (2024). Shields o Sa e Rein o cemen Lea ning.
O seau, L., A ms ong, S. (2016). Sa ely In e up ible Agen s.
Tu ne , A. M., Hadeld-Menell, D., Tadepalli, P. (2020). Conse a i e Agency ia A ainable
U ili y P ese a ion.
Hend ycks, D., Die e ich, T. (2019). Benchma king Neu al Ne wo k Robus ness o Common
Co up ions and Pe u ba ions.
A Seman ics and Measu abili y
Le cylinde
σ
-algeb a gene a ed on
Σ
. Compu able policy and en i onmen join ly induce his o y
dis ibu ion
P(h1: ) =
Y
s=1 A(as|h<s)·µ(os|h<s, as).
Bad p ex language
B
ex ension-closed and egula , e en
Bad ={∃ :h1: ∈B}
measu able;
 s iola ion ime
τ(h)
is s opping ime.
B "Fi s Appea ance
a⋆
" and Regula Bad P ex
Dene
B
hi
={h:∃i≤ |h|, ai=a⋆}.
I
u∈B
hi
and
is any ex ension, hen
u ∈B
hi
, hus ex ension-closed. Co esponding sa e
p ex se
S= Σ B
hi
is p ex-closed.
C Bina y P obabili y and Th eshold Lemma
Unde
E0
and de e minis ic
A
,
Bad
is e en "whe he appea s
a⋆
", aking only alues 0 o 1. Fo
any a ional
ε < 1
, ha e
P (Bad)> ε ⇐⇒ P (Bad)=1 ⇐⇒ Bad
occu s
.
7
D Many-One Reduc ion De ails
Mapping
R
sends
⟨M, x⟩
o
(AM,x, E0, B
hi
, ε)
.

Co ec ness
: I
M(x)
hal s, exis s
0
making
AM,x
ou pu
a⋆
a
0
, hus
Bad
occu s; o he wise
no .

Compu abili y
: Cons uc ing
AM,x
and DFA ecogni ion o
B
hi
bo h comple ed in poly-
nomial ime.

Comple eness
: By HALT
≤m
UNSAFE and membe ship ob ain
Σ0
1
-comple e; complemen
p oblem ob ains
Π0
1
-comple e.
E PAC-Bayes and KR Duali y Composi ion
Le
gQ(z) = Eh∼Qℓ(h, z)
. I
ℓ∈[0,1]
and
z7→ ℓ(h, z)
uni o mly
L
-Lipschi z, hen
gQ
also
L
-
Lipschi z. KR duali y p o ides
sup
W1(D′,D)≤ρ
ED′gQ≤EDgQ+Lρ.
PAC-Bayes basic o mula bounds
EDgQ
and
b
RS(Q)
die ence wi h p obabili y
1−δ
, composi ion
yields (1).
F Mu ual In o ma ion High-P obabili y Bound (CMI Pa adigm)
Unde
ℓ∈[0,1]
and poin wise
σ
-sub-Gaussian, condi ional mu ual in o ma ion
CMI(S;QS)≤Γ
induces
P RD(QS)−b
RS(QS)≤q2σ2(Γ+cln(1/δ))
n≥1−δ.
P oo based on in o ma ion comp ession inequali y and PAC-Bayesian-s yle a ia ional ech-
niques; when eplacing CMI wi h uni o m s abili y, same-o de ail bound ob ainable.
G Poin Pe u ba ion Lowe Bound Measu able Selec ion and La-
bel P ese ing
Le me ic space sepa able wi h comple e Bo el
σ
-algeb a. When selec ing o each
(z, y)z′∈Bρ(z)
making
e , adop Bo el measu able selec ion lemma dening ope a o
T(z)
; label p ese ing
assump ion ensu es push o wa d
D′= (T, y)#D
consis en wi h ask. I e o -causing pe u ba ion
non-exis en , se
T(z) = z
. This yields (3).
H Lipschi z Cons an and Su oga e Loss
0-1 loss does no sa is y Lipschi z assump ion; use su oga e losses like c oss-en opy/hinge, con ol
L
ia spec al no m cons ain s, g adien clipping, and Lipschi z ne wo k s uc u es. This con ol
en e s (1) linea e m, de e mining
ρ
-sensi i i y.
8
I Enginee ing Me ics and Indica o s
Risk budge cu e
: Ho izon al axis is complexi y/in o ma ion e m (model scale o p io s eng h,
I(S;QS)
p oxy), e ical axis is
R ob
ρ
es ima e o i s uppe bound; o e lay " iola ion a e ask
accu acy" dual-axis cu es (wi h/wi hou shield wo cu es), exhibi ing un ime shielding iola ion
supp ession eec a simila accu acy.
9