Rice's Theorem under Self-Modification: Elevation Operators and a Normal Form
cs.LO · cs.AI · cs.CL · math.LO
Quick verdict
Rice-type barriers for self-modifying code: one-step elevation stays K-hard, persistence hits Π02, triggers admit a normal form; rigorous, partly definitional.
Summary
The paper asks whether the safety of a self-modifying program can be decided algorithmically. One rewrite step is modelled as a total computable transformation Φ on program indices, and preservation as the elevated property ΛΦ(P) = {x ∈ P : Φ(x) ∈ P}. For extensional Φ the set is behavioural and Rice's theorem settles undecidability; for intensional Φ the author introduces 'uniform disruption' — an inert wrapper whose code encodes the halting set K — and shows that the s-m-n reduction of Rice's proof works inside a single behavioural fibre, so ΛΦ(P) inherits K or its complement (Theorem 4.1). Unbounded iteration can push persistence to Π⁰₂-completeness for Σ⁰₁ properties (Theorem 4.5). The core contribution is the semantic elevation operator (Definition 7.1): a wrapper reacting to one Σ⁰₁ trigger anchored to K, for which a Representation Theorem shows the elevated property is exactly P ∩ Sa or P \ Sa, with hardness, non-enumerability of the safe region, and a Rice–Shapiro polarity restriction (Proposition 7.12). Four axes (rewriting, consistency supervision, conformance, monitoring) instantiate the form; supervisor towers do not help (§6). Limitations: the class E(P) is stipulated rather than characterised, hypothesis (HB) depends on the underlying clock, and the AI-safety motivation proceeds by analogy through companion work.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under uniform disruption (an inert wrapper encoding K), the one-step elevated property ΛΦ(P) inherits K or its complement via the s-m-n reduction run inside a single behavioural fibre, so preservation is undecidable even though Rice's theorem does not apply (Lemma 3.8, Theorem 4.1).
- Unbounded iteration of the step can make ω-persistence Π⁰₂-complete for Σ⁰₁ properties, and the phenomenon does not need intensionality (Theorem 4.5, shift φx(z+1)).
- For every semantic elevation operator the elevated property is exactly P ∩ Sa or P \ Sa, determined by trigger and polarity alone, and the safe region is not recursively enumerable (Representation Theorem 7.7).
- Rice–Shapiro forces the polarity: a finite trigger can only make systems enter a Σ⁰₁ property and only leave a Π⁰₁ one (Proposition 7.12).
- No finite tower of supervisors yields a total correct certificate of preservation, and a sufficiently general supervisor inherits the same undecidability at its own level (Theorem 6.2, Proposition 6.7).
Strengths
Unusual scoping honesty
§1.3 'What is not claimed' explicitly disclaims totality of the class, universality of K-anchoring, and any derivation of classical incompleteness; §2.2 pre-empts the circularity objection to class U ('every undecidable property is undecidable') by defining U by provenance and shifting the theorem's content to degree inheritance; §7 concedes the normal form is stipulated. Rare candour that prevents overclaiming.
Complete, checkable proofs with classical machinery used correctly
Lemma 3.8's fibre reduction, Theorem 3.12, Theorem 4.5's two-sided Π⁰₂ proof (TOT reduced via the explicit chain Φk(g(e)) = w(e,k)), the five-part proof of Theorem 7.7, and Lemma 7.5's irrevocability argument are all self-contained. The clock property τe(x) ≥ x is set up in §2 and consistently exploited (e.g. Props 7.26/7.29 need late unanswered inputs).
Boundary work that maps the abstraction's edges
Reusable framework with a usage guide
Weaknesses
The headline 'normal form' is close to definitional
Standard engine, new packaging
Modelling gap to the stated AI-safety motivation
Model dependence of the safety-polarity class
Imprecise conjectures at the frontier
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a pure recursion-theory paper that formalises 'one step of self-modification' as a total computable transformation Φ on program indices and studies the *elevated property* ΛΦ(P) = {x ∈ P : Φ(x) ∈ P} (Definition 3.1) and its ω-iteration (Definition 3.2). Claims are carefully partitioned (§1.2 'What is proved', §1.3 'What is not claimed'): (1) for extensional Φ, ΛΦ(P) is behavioural and Rice applies (Proposition 5.2); (2) for intensional Φ satisfying *uniform disruption* (Definition 3.6 — an inert wrapper w with Φ(w(e)) ∈ P ⇔ e ∈ K), the s-m-n reduction of Rice's proof runs inside a single behavioural fibre, so K or K̄ many-one reduces to ΛΦ(P) (Lemma 3.8, Theorem 4.1); (3) ω-persistence can be Π⁰₂-complete for Σ⁰₁ properties (Theorem 4.5, reducing TOT via the explicit chain Φk(g(e)) = w(e,k)); (4) within the class E(P) of *semantic elevation operators* (Definition 7.1), the Representation Theorem 7.7 gives the normal form ΛE(P) = P ∩ Sa or P \ Sa, Σ⁰₁/Π⁰₁-completeness of the trigger and safe region respectively, and non-enumerability of the safe region (Corollary 7.8); (5) Rice–Shapiro forces polarity (Proposition 7.12): finite triggers can only enter Σ⁰₁ properties and leave Π⁰₁ ones. §6 shows no supervisor tower decides preservation (Theorem 6.2) and Proposition 8.1 gives a 'Gödel at family scale' statement: no sound r.e. theory covers the preserving systems. Four axes (Props 7.22, 7.24, 7.26, 7.29, 7.30) and catalogue Tables 2–3 instantiate the form.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does this paper actually prove about self-modifying systems?
At the level of program indices, it proves that deciding whether one self-rewrite keeps a safety property ('preservation') is as hard as the halting problem under its 'uniform disruption' condition, and that staying safe under all future rewrites can be Π⁰₂-complete — strictly harder than the halting problem's own arithmetical level. Hence no general algorithm can certify such safety.
What is a 'semantic elevation operator'?
It is a computable wrapper around a program that reacts to a single halting event (a Σ⁰₁ 'trigger') anchored to the halting set K, either making the wrapped system enter the safety property when the trigger fires ('search' polarity) or leave it ('safety' polarity). The paper proves the resulting 'elevated' property is always exactly P ∩ Sa or P \ Sa, determined by the trigger and polarity alone.
Why doesn't Rice's theorem apply directly?
Rice's theorem needs the property to depend only on the computed function. When the rewrite reads the code, the elevated property distinguishes programs with identical behaviour, so Rice does not apply. The paper instead replays the s-m-n reduction used to prove Rice inside one fibre of behaviourally identical programs, recovering the same hardness.
Is this result about real AI/ML systems?
Only by analogy. The formalism covers transformations of program indices in a Turing-machine model; it does not model gradient-based retraining. The paper flags the bridge to self-improving AI as motivation (developed in a companion paper) and marks illustrations like the Gödel Machine and Levin search as unverified instances.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt with several '[...sampling gap...]' regions: parts of Table 1's rows, the §6.1–§6.2 boundary (Lemma 6.4's statement is cut mid-sentence), the opening of §7.4, the end of Remark 7.33, and the end of Open problem 9.6 were skipped by sampling and may exist in the full paper; judgments about those passages are limited.
- All theorems, propositions and lemmas cited in this review (3.1–9.6 as referenced) appear with their statements, and the main proofs (3.8, 3.12, 4.5, 7.5, 7.7, 7.12, 8.1) are complete in the provided text; the reference list [1]–[23] is fully present.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.