cs.LOSep 10, 2026

Rice's Theorem under Self-Modification: Elevation Operators and a Normal Form

Authors: Jose Pascual Gumbau Mezquita

Abstract

We ask whether it can be certified algorithmically that a self-modifying computational system preserves a safety property at its next step (preservation) and along its whole evolution (persistence). One step of self-modification is a total computable transformation ΦΦ of program indices, and preservation is the elevated property ΛΦ(P)={xP:Φ(x)P}Λ_Φ(P)=\{x\in P:Φ(x)\in P\}. When ΦΦ is extensional, ΛΦ(P)Λ_Φ(P) is behavioural and Rice's theorem applies. When ΦΦ reads the code, ΛΦ(P)Λ_Φ(P) is no longer behavioural, yet under uniform disruption (an inert wrapper encoding KK) the s-m-n reduction that proves Rice's theorem works inside a single behavioural fibre, and ΛΦ(P)Λ_Φ(P) inherits the halting degree: one pullback of Rice, at two scales. One step never exceeds the degree of PP; persistence can be Π20Π^0_2-complete for Σ10Σ^0_1 properties, even for extensional ΦΦ. We then isolate the mechanism shared by rewriting, supervision and system comparison: the semantic elevation operator, which wraps a base system and reacts to one finite event anchored to KK, entering or leaving the property. For this class the elevated property is PSaP\cap S_a or PSaP\setminus S_a, determined by trigger and polarity alone; it inherits KK or its complement; and the safe region is not recursively enumerable. The Rice-Shapiro theorem restricts the polarity: a finite trigger can only enter a Σ10Σ^0_1 property and only leave a Π10Π^0_1 one. Four axes (functional, deductive, conformance to a reference, monitoring) are verified instances, and towers of supervisors do not lower the barrier. We exhibit KK-hard intensional operators outside the class and state the open characterisation problem.

Explore similar work

CardsList
  1. Static Analysis of Recursive SHACL

    May 4, 2026Anouk Oudshoorn, Magdalena Ortiz, Mantas SimkusModal LogicLabel Constraint Modeling