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

Jun 26, 2026cs.LO

Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems

We establish mathematical limits of algorithmic safety verification for Turing-complete self-modifying systems, the class in which recursive self-improvement takes place, both for a fixed system and across its own modification. Statically, no verifier is sound, complete and tractable: over unbounded domains by Rice's and Gödel's theorems, over all finite configurations by Trakhtenbrot's theorem, and over succinctly described finite environments because verifying a policy against an adversary is coNP-complete and synthesising one is PSPACE-complete. Dynamically, we model one step of self-modification as a computable transformation of code and ask whether a safety property survives it. If the transformation depends only on behaviour, this is Rice's theorem one level up; if it reads the code, as self-modification does, the question is no longer semantic, yet the same s-m-n reduction works inside a class of behaviourally identical programs and inherits the halting degree. One step is never harder than the property; persistence along the whole trajectory can be Π20Π^0_2-complete. Certification by a total algorithm is possible only for transformations of restricted expressivity, not merely for systems that stop changing. No tower of supervisors helps, and every total supervisor errs on an undecidable set of systems. For effectively pointwise properties, every faithful bounded scheme that certifies on finite behavioural evidence admits evolution traces certified at every stage while the property is violated. What survives is exact: a monitor that raises an alarm on violation semidecides it, and comparison against a frozen reference keeps the full theory.
Jose Pascual Gumbau Mezquita
May 4, 2026cs.LO

Static Analysis of Recursive SHACL

SHACL (Shapes Constraint Language) expresses constraints on RDF data by means of so-called shapes. Its central service is validation: verifying whether a data graph complies with a SHACL document. But so far, there are no static analysis services to compare documents. In this paper, we study the following problem: decide whether all graphs that validate one SHACL document also validate another. Unlike previous works that have considered the implication of shape expressions only, we consider documents comprising (recursive) shape definitions and targets. We show that implication (a.k.a. containment) is undecidable under the supported and the stable model semantics, even for the fragment that uses the description logic ALCIO for shape expressions. Under the well-founded semantics, in surprising contrast, it is decidable in single exponential time. Our key technical contribution is a translation of SHACL under the well-founded semantics into the full hybrid mu-calculus, revealing a novel link between well-founded models and a fixed point modal logic, and a worst-case optimal automata-based decision procedure.
Anouk Oudshoorn, Magdalena Ortiz, Mantas Simkus
Apr 24, 2026cs.LO

An Undecidability Proof for the Plan Existence Problem

The plan existence problem asks, given a goal in the form of a formula in modal logic, an initial epistemic state (a pointed Kripke model), and a set of epistemic actions, whether there exists a sequence of actions that can be applied to reach the goal. We prove that even in the case where the preconditions of the epistemic actions have modal depth at most 1, and there are no postconditions, the plan existence problem is undecidable. The (un)decidability of this problem was previously unknown.
Antonis Achilleos