arXiv CSopen access

What Syntax Cannot See: The Dynamic Syntactic Invariance Principle and Several Instances of the Same Hidden Assumption, and a Contradiction

What Syntax Cannot See: The Dynamic Syntactic Invariance Principle and Several Instances of the Same Hidden Assumption, and a Contradiction Fabio Francesco Gabriele Buono ORCID 0009-0004-9199-2793 Preprint

arXiv:2608.00958v1 [cs.CR] 2 Aug 2026

August 4, 2026

Abstract This paper develops a single method, find what an accepted result silently assumed, make it a variable, and prove what follows once it is dropped, and shows it keeps working across domains with nothing in common. Its formal core is the Dynamic Syntactic Invariance Principle: a known static inaccessibility result survives when a system’s rules evolve in time, under one sharp necessary condition. A direct cryptographic payoff follows: the secrecy of a rolling-key scheme persists across sessions under a structural update, strengthening a static guarantee from earlier work. The same move is then carried into settings far from each other, special relativity, the reach of a formal theory of physical law, and computable output that is fully meaningful yet indistinguishable from noise to every observer, each established on its own terms, so the recurring structure beneath them is found, not imposed: a distinction real at a full level of description can be invisible at a restricted one. Applied to SAT, this yields a contradiction from which coherence forces P ̸= NP, derived from what standard theory already admits rather than assumed, offered with one reservation, about the proof, not the answer.

Remark (Notation: what is imported, and what is new). a, b, R, P are imported unchanged from [7] (Section 2). O, ⪯, O⊥ , Oprof , O⊤ , prof(x) are imported unchanged from [5] (Sections 4, 6); O⊤ is the complete observer at the top of the richness order, the one reader that receives the whole of its input. Bt , Ct , Kt , Mt , f are imported unchanged from [3] (Section 5.3 and throughout). The update function υ, the history Hn , and the terms “opacity-preserving”, “swapblind”, and “permutation-blind” are new terminology introduced in this paper and have no prior meaning in the cited sources. A few symbols carry more than one meaning across the paper, always in disjoint sections, and are flagged here so the table below can be read without ambiguity. The constants a, b are, throughout, the two frozen Skolem constants of [7], and denote nothing else in this paper. The letter L denotes the space of candidate physical laws in the theory-of-everything material (Definition 11.2) and, separately, the number of confusion layers in the blind-cascade cipher (Section 7.6); the two occur in unrelated sections and the intended reading is always the one local to the surrounding discussion. The letter L carries two further, entirely standard readings, each unmistakable in context: in the observer-hierarchy results it is a formal language, always written L ∈ / {∅, Σ∗ } or, as the object language of the Tarski material, L0 (Proposition 4.2 onward, Section 11.6); and in the Cell (d) instance it is momentarily the length of a mixed-radix ciphertext, in C = (c1 , . . . , cL ) (Proposition 5.1). Likewise Φ denotes a candidate physical law in the theory-of-everything material (with Ψ the law produced by diagonalization), while Φs , always written with the seed subscript s, denotes the full encryption map of the blind-cascade 1

cipher (Section 7.6); the subscript keeps the two apart. Finally b additionally serves as a generic byte string in the MS-DOS worked example (Proposition 7.5), where no Skolem constant is in play. Symbol

Meaning, and where it is introduced

Sections 2–6: static and dynamic SIP Rn , υ, Hn The n-th rewriting system in a dynamic system, its update rule, and the history of derivations so far (Definition 3.1). O, ⪯, O⊥ , A structural observer, the richness order on observers, the trivial Oprof , O⊤ observer, the profile observer, and the complete observer at the top of the order (Definitions 4.1, 6.4; O⊤ imported from [5]). Section 7: semantic frames F , F1 , F2 A semantic frame; two frames disagreeing on the same fact (Definition 7.1, Theorem 7.2). E = An explicit encoding: a rewriting system paired with the set of (R0 , IR0 ) equalities it derives (Definition 7.9). Not to be confused with X below, an unrelated later use. I = An interpreted machine: a Turing machine with a fixed encoding (T, E, F ) and frame (Definition 7.11). Section 8: the orbital machine Esp , Fsp The (countable) space of all possible encodings, and of all possible computable frames (Definitions 8.1, 8.3). σE , σF , σ The encoding and frame selectors; a general selector function from history to a choice of both (Definitions 8.5, 8.7). OF , T OF ,E The semantic oracle for frame F ; the oracle orbital machine that may consult it mid-computation (Definitions 8.18, 8.19). Andromeda and the theory of everything V, φ The space of physical states (velocities); a constrained frame selector over it (Definition 10.1). L, c The space of all candidate physical laws; the cardinality of the continuum (Definition 11.2). Φ, Ψ A candidate physical law; the law diagonalization produces outside a given countable list (Proposition 11.4). Chaitin’s Ω and usable algorithms Ω, ΩU Chaitin’s halting probability, and the halting probability relative to a universal machine U (Proposition 12.1, Proposition 12.2). D, X The answer sequence of an arbitrary decision problem, and its XOR-pairing with Ω (Theorem 12.4); X is unrelated to the encoding E above and is written differently on purpose to avoid confusion between them. C, Ccomp , A class of observers (tests); the class of all computable ones; the Cpoly class of polynomial-time ones (Definition 12.3).

1

Introduction

A system of rewriting rules with addition built in cannot prove that a + b = b + a when a and b are two fixed, distinct constants: the terms are frozen, never touched by any rule, and a system that never touches them can never compare them [7]. The fact is true, and permanently invisible to the syntax that would have to prove it. This is the static Syntactic Invariance Principle: fix the rules once, and whatever they cannot reach stays out of reach forever, however long they run. Real systems, though, do not keep their rules fixed. A cipher takes a new key each session; an adaptive filter rewrites itself as it sees more data. So the question this paper begins from is not whether a fact can be hidden once, but whether it stays hidden when the rules that hide it are 2

rebuilt again and again, each time as a function of everything that has happened so far. We prove that it does — under one sharp and necessary condition: the process doing the rebuilding must itself be unable to tell the two possible facts apart. This is the Dynamic Syntactic Invariance Principle (Theorem 3.3), and its condition has two halves, the second of which — a constraint on the update mechanism with no analogue in the static case — is exactly what the extra freedom costs (Proposition 3.5, Corollary 4.4). Its first application is cryptographic: it shares the shape of an open problem left in earlier work [3], establishing the secrecy target that problem concerns in a restricted regime while leaving its distinctive question open, and it recovers and extends several further results from independent sources, each checked directly rather than by analogy. From there the paper does one thing repeatedly: it takes a result that looks settled, locates the assumption it silently relied on, and asks what happens once that assumption is allowed to vary. The assumptions are not chosen to be exotic; they are the ordinary, load-bearing ones a working result leans on without stating. One sits close to home — that a derivation is read against one fixed intended model (Theorem 7.2) — and the same move then carries into four instances that arise independently, each discovered rather than built to fit: an abstract machine built from two independent selectors (Section 8), special relativity’s Andromeda paradox (Section 10), the question of whether a complete theory of everything could exist (Section 11), and the fact that a computable algorithm’s output can be indistinguishable from noise to every observer, of which Chaitin’s Ω is the sharpest witness (Section 12). These are not brought together for effect, and they are not forced into a frame that does not hold them — a risk any reader is right to guard against. The results are cryptographic at their core, and that practical connection runs through the whole paper even where it is least obvious; the excursions into physics and algorithmic randomness are where the same shape turns up most unexpectedly. Each section is established entirely on its own terms before it is connected to any other, one axis at a time, so that whatever recurrence emerges is found, not imposed. From all of them together, one apparent contradiction emerges, whose outcome, if correct, is the true core of this work.

2

Background: the static principle and its known instances

2.1

The syntactic instance

We begin with one concrete fact about rewriting rules, of the kind used throughout automated theorem proving: two terms built from different outermost symbols can never be forced equal, whatever is substituted into them. This is the same intuition behind why f (x) and g(y) do not unify when f and g are distinct function symbols. Definition 2.1 (First-symbol clash [7, §3]). Two terms s, t have a first-symbol clash if they have distinct outermost function symbols and neither is a variable; no substitution unifies them. This single fact pins two constants in place forever. Read a and b below as two fixed tokens dropped into the system at the start: the rules can move a great deal around them, but they can never touch a or b directly, and so can never compare them. They are called Skolem constants only in the sense that matters here: they are fresh — brand-new symbols that appear in no rule of the system — so no rule mentions them, and a rule that never mentions a symbol can never fire on it. Freshness is the whole reason they stay frozen; the name is just the standard label for it. Lemma 2.2 (Frozen subterm lemma [7, §3]). Let a, b be Skolem constants, fresh and distinct from 0 and from every term s(t), in the language L = {0, s, +} with rules 0 + x = x (A1), s(x) + y = s(x + y) (A2). Then no rule in {A1, A2} fires at the root of a + b or b + a; these subterms are frozen under every derivation of any length; and the relative order of a, b inside any compound term is a global invariant of the entire derivation. 3

The next definition names a pattern familiar to anyone who has verified a loop invariant: a property true at the start and preserved by every step. Here the process is a rewriting system rather than a loop, but the argument has exactly the same shape. Definition 2.3 (Syntactic invariant [7, §4]). A property P of terms is a syntactic invariant for a rewriting system R if every term in the initial clause set satisfies P , and applying any rule of R to a term satisfying P yields a term satisfying P . [7, Def. 4] states this for R a superposition calculus; we use the broader term “rewriting system” throughout, since superposition is one instance of it and nothing below relies on anything beyond what Lemma 2.2 provides. Lemma 2.4 (Syntactic Invariance Principle, static form [7, Lemma 5]). If P is a syntactic invariant for R, every term in every clause derivable by R satisfies P . The proof is induction on derivation length: the base case is the first condition of Definition 2.3, and each step preserves P by the second. To apply this to the Skolem pair, take P (t) to be “every occurrence of a sits inside a subterm a + u with b occurring in u, and symmetrically for b.” This holds of the initial clause and is preserved by {A1, A2} (Lemma 2.2), so no derivable clause ever exposes the relative order of a, b. The empty clause would require unifying a with b, and is therefore never derivable [7, Lemma 9]. Remark (The shape of a lower bound [7, Remark 7]). [7, Remark 7] names the general pattern Lemma 2.4 instantiates: to rule out a fact φ, find a property P that holds at the start, that every rule preserves, and that leaves no room for φ. The target, in that source’s own phrase, is “unreachable rather than merely unreached.” Theorem 3.3 below is built in exactly this shape, with one addition: the sequence (Rn ) itself must not, in its own construction, undo the preservation. This is why Definition 3.2 carries two conditions where the static Definition 2.3 needed one: the second condition is the price of letting R move. Remark (Remark 10 of [7]: a dependency the static paper already flagged). [7, Remark 10] observes that the argument holds unchanged when the rule set is enlarged (factoring, splitting), provided no new rule touches the frozen Skolem constants. The invariance thus depends on which rules are available — a dependency that is a side condition while the rule set is fixed, and becomes load-bearing once the rule set may change over time. Section 3 formalizes it.

2.2

The distributional instance

The same argument has a life outside syntax. Its skeleton — a true property, holding at the start and preserved by every available operation — transfers unchanged to a probabilistic setting, where it becomes the MR-OTP’s own invariance theorem. What was a fact about which clauses a calculus can derive becomes a fact about what a distribution can reveal. Remark (Theorem 8.15 of [3] as a second instance). [3, Remark 8.20] identifies its own Theorem 8.15 as an instance of the same argument shape. There the invariant is P : Pr[M = m | C = c, B = b] = Pr[M = m] for all m, c, b; it holds after any single fresh MR-OTP encryption ([3, Prop. 8.1]) and is preserved by every further operation on the observable (C, B), since C is a function of a fresh key independent of all prior data. The correspondence with the syntactic case is term for term: the message digits mi play the role of the Skolem constants a, b; the ciphertext/base pair (C, B) plays the role of the syntactic system operating on symbols alone; and the frozen compounds a + b, b + a correspond to the message M itself. The two settings differ in one respect only, and the source states it: the invariant holds per-derivation in [7] and distributionally here [3, Rem. 8.20]. Section 5.2 makes this dictionary rigorous, as a generalization of the simpler Cell (d) instance recovered in Section 5.1; Section 5.3 then extends both to a dynamic setting. 4

Both instances share one feature this paper preserves throughout: the invariant P is a true fact, preserved because the operations available preserve true facts — never a false assertion built to force a contradiction.

3

The dynamic setting

3.1

Motivation

Real codes do not sit still: their rules change over time. The static principle of Section 2 freezes two constants under a fixed rule set, but says nothing about what happens when the rules themselves are updated. This section proves that the hiding survives a changing rule set, under one sharp condition on the update, and notes a connection to an open problem posed in the source material. This connects to Open Problem 6.4 of [3], which concerns a base sequence updated at every step as Bt+1 = f (Ct , Bt ) for publicly visible Ct , and asks under what condition on f a hidden quantity stays protected. The connection is one of shape, and the source itself points to it: [3, §6.4] states the difficulty in this paper’s own vocabulary, cites the Syntactic Invariance Principle of [7] by name, and frames its problem as a search for an invariant of the joint distribution that holds after the first session and is preserved by every subsequent application of f — which is the shape of Theorem 3.3. One necessary condition the source identifies informally, that the distribution of Bt+1 given Ct carries no information about Kt , is the distributional reading of this paper’s condition (ii). We record the shared shape and do not claim to settle Open Problem 6.4: its distinctive demand — an f giving an adversary a larger base search space than the partition protocol, without the disjointness condition of [3, Def. 6.1] — lies outside what this paper establishes, and a proper account of the connection would need an argument this paper does not attempt. What this section does prove stands on its own, independently of that problem: that the syntactic hiding of Section 2 survives a changing rule set under an opacity-preserving update (Theorem 3.3), and, distributionally, that the MR-OTP’s Cell (d) secrecy persists across a rolling base under a swap-blind update (Theorem 5.5).

3.2

Dynamic rewriting systems

The idea is familiar from ordinary automata: a machine whose transition rules change over time, the way a state machine’s transition table might be rewritten between runs. The one new ingredient is that the rewriting may depend on everything that happened before it. Definition 3.1 (Dynamic rewriting system). A dynamic rewriting system is a sequence (Rn )n≥0 of finite rewriting systems over a common alphabet Σ, together with an initial term (or clause set) x0 and local derivations (Dn )n≥0 , where D0 uses the rules of R0 on x0 , and, for n ≥ 1, Dn uses the rules of Rn on the term produced by Dn−1 under Rn−1 . Write Hn = (D0 , . . . , Dn−1 ) — the history, the record of everything the system has done up to step n, and the only thing the update below is allowed to look at when it decides the next rule set. An update rule is υ with Rn+1 = υ(Rn , Hn ); the system is generated by υ if this holds for every n. Definition 3.2 (Opacity-preserving update). Let a, b be fixed Skolem constants, fresh w.r.t. Σ. An update υ is opacity-preserving w.r.t. a, b if, for every Rn , Hn , Rn+1 = υ(Rn , Hn ) satisfies: (i) a, b stay frozen and stay fresh: no left-hand side of any rule in Rn+1 has a clash-free unifier with a, with b, or with a subterm rooted at + having a or b as an immediate argument (in particular, no rule fires at the root of a + b or b + a themselves, nor at a or b directly); and, further, neither a nor b occurs in the right-hand side of any rule in Rn+1 , so no rule can introduce a fresh occurrence of a or b anywhere other than where 5

they already sit. This is the same protection Lemma 2.2 establishes for the fixed system {A1, A2}, together with the freshness that source already assumes of a, b throughout, now required to hold afresh at every step of the sequence (Rn ), not merely at R0 . (ii) The update does not leak the order: Hn 7→ υ(Rn , Hn ) is invariant under swapping every a with b throughout Hn : if Hn′ is Hn with a, b exchanged, υ(Rn , Hn′ ) equals υ(Rn , Hn ) with the same exchange applied. The two conditions divide the work cleanly. Condition (i) generalizes Lemma 2.2, made load-bearing exactly where Remark 2.1 flagged it would need to be: the freezing that held for one fixed rule set is now required afresh at every step. Condition (ii) governs the one channel the static case never had. When R may move, the update mechanism itself can carry information about the order of a, b, independently of any rewriting; condition (ii) closes that channel. This is the extra price of letting R move, anticipated in Remark 2.1, and it is why the dynamic principle needs two conditions where the static one needed one.

3.3

The characterization theorem

The theorem below states the guarantee in full: under an opacity-preserving update, the order of a, b stays hidden at every finite step, forever. Theorem 3.3 (Dynamic Syntactic Invariance Principle). Let (Rn )n≥0 be generated by an opacitypreserving υ, started from an initial term (or clause set) x0 in which a, b already occur only inside a + b, b + a, under an R0 satisfying the hypotheses of Lemma 2.2 on a, b. Then for every n ≥ 0, every term produced by D0 , . . . , Dn has a, b occurring only inside a + b, b + a, and their relative order is never exposed at any finite step. Proof. The proof is by induction on n, generalizing the proof of Lemma 2.4. Base case. By hypothesis, x0 already has a, b occurring only inside a + b, b + a: P (“a, b occur only inside a + b, b + a”) holds initially, directly, with nothing further to derive. Inductive step. Assume P holds through step n − 1. By (i), Rn has no rule firing at a, b’s root, so no existing occurrence of a or b (or of the frozen compounds a + b, b + a) is disturbed, by the same first-symbol-clash argument as Lemma 2.2; and, since neither a nor b occurs in the right-hand side of any rule in Rn , no rule can introduce a fresh occurrence of a or b elsewhere in the term either. Together these give that Dn preserves P exactly. By (ii), Hn−1 7→ Rn is swap-invariant: two systems agreeing except for a, b’s order produce, at every step, swap-related rule sets. Combined with (i), the order never influences, nor is influenced by, any observable part of the derivation. By induction P holds at every n. Since unifying a+b with b+a (exposing the order) requires unifying a with b, distinct constants no rule ever unifies, the order is never exposed. Remark (The positive half of a characterization). Theorem 3.3 holds for every opacity-preserving υ, and this conditioning on υ is exactly what the result characterizes: an update violating either condition can expose the order at a finite step. For instance Rn+1 = Rn ∪ {a → 0}, triggered once a public signal in Hn reaches a fixed value, violates (i) and exposes a at once. The theorem is the positive half of a characterization; Section 3.4 establishes what holds about necessity. Remark (Relation to the abstract obstruction framework of [6]). Dynamic SIP and the abstract obstruction theorem of [6] are two generalizations of the same static fact (Lemma 2.2), along two independent axes: that source generalizes across systems, holding the rule set fixed while abstracting the signature, radius, and model; this section generalizes across time, letting the rule set itself evolve. The two meet on condition (i) and diverge on condition (ii). On condition (i) the correspondence is exact. Freeze n and take a single Rn satisfying (i): this is, term for term, a local syntactic system R = (Σ, V, Rules, r0 ) in the sense of [6, Def. 2.5], 6

with r0 = 1 for {A1, A2}. Condition (i) plays two roles from that source’s apparatus at once. For the bare constants a, b it is their protected set ([6, Def. 2.9]): no rule fires at a or b, and the definition’s second half holds automatically, since constants have no subterms to rewrite inside — exactly as that source’s Example 2.11/Lemma 4.1 notes for this same pair. For the compounds a + b, b + a, condition (i) protects their root, which in that source’s more modular architecture is the job of the coherence clause ([6, Def. 2.12(v)]), verified there through its Lemma 4.3. Condition (i) folds both roles into a single requirement. Both papers read the same fact about {A1, A2}, first isolated in Lemma 2.2, through two formal lenses. Condition (ii) is where the two generalizations part. A static local syntactic system has no update mechanism, and so nothing for a swap-invariance requirement to constrain; condition (ii) is this paper’s own contribution, needed exactly because Rn here may change. A dynamic analogue of that source’s Case 2 — a derivation-length lower bound for systems whose protected set evolves under an opacity-preserving update — is left open, in the same spirit as that source’s Question (Q2). This paper does not attempt it. The invariant P used here is the special case, under condition (i), of the refined invariant that source states in its Lemma 4.3 (matching Lemma 9 of [7]): that a occurs only inside some a+u with u containing b, and symmetrically for b. Once condition (i) keeps a+b and b+a frozen at their root at every step, u can only ever be b itself, and the refined and simple invariants coincide on every term this section’s derivations produce. The refined form is needed in that source’s general setting only because its protected set, alone, does not keep a + b’s root frozen; condition (i) does that job directly here. Corollary 3.4 (Static SIP as the degenerate case). Let υid (R, H) := R, and take x0 to be the initial clause N : a + b ̸= b + a (so a, b trivially occur only inside a + b, b + a from the start). Then υid is opacity-preserving whenever R0 satisfies Lemma 2.2, and generates Rn ≡ R0 for all n. Applying Theorem 3.3 recovers exactly Lemma 2.4, and hence [7, Thm. 11] (OI ̸⊆ T CSC). Proof. The base case on x0 . x0 = N has a, b occurring only inside a + b, b + a by construction, exactly as Theorem 3.3’s hypothesis requires. Condition (i). Rn+1 = Rn = R0 by induction; R0 = {A1, A2} satisfies Lemma 2.2 by hypothesis, so (i) holds at every step with nothing further to check. Condition (ii). υid ignores its second argument entirely: υid (Rn , Hn ) = Rn = υid (Rn , Hn′ ) for every Hn , Hn′ , a fortiori for the swapped pair required by (ii). So υid is opacity-preserving and Theorem 3.3 applies. The dynamic system with Rn ≡ R0 for all n is, by Definition 3.1, exactly a single fixed system subjected to unboundedly long derivation — the object Lemma 2.4 already quantifies over. Taking P (t) as in [7, Lemma 9], the conclusion coincides with that lemma’s Steps 1–2 exactly; Step 3 there (the empty clause is underivable) follows identically. Hence T CSC + {A1, A2} ⊬ W , and with [7, Lemma 8] (OI ⊢ W ) and [14, Thm. 4.3] (T CSC ̸⊆ OI), this recovers [7, Thm. 11]. Remark (The corollary verifies that the generalization reduces correctly). The purpose of this corollary is to verify a consistency requirement: since the static case is the υ ≡ υid instance of the dynamic one, a correct generalization must reduce to the original with no discrepancy in hypotheses, conclusion, or proof structure. The check above confirms it does, explicitly rather than by assertion. The Hetzl–Vierling question itself was already resolved by [7, Thm. 11].

3.4

On necessity

Theorem 3.3 shows the two conditions are jointly sufficient. This subsection shows condition (i) alone is not: the update channel condition (ii) governs is real, and its necessity is exactly what the static setting could not see. Proposition 3.5 (Condition (i) alone is not sufficient). There is an update satisfying (i) but not (ii), exposing the order at some finite step. 7

Proof sketch. Let υ leave Rn ≡ R0 unchanged (so (i) holds trivially), but let the visible history additionally record a bit g(Hn−1 ) equal to 1 exactly when a preceded b initially. This sidechannel is not a rewriting rule, so (i) is unaffected, but it is not swap-invariant, violating (ii); the order is read off the bit directly. Remark (The side-channel is a genuine mechanism, not an artifact). The construction is a sidechannel, not a rewriting attack: it shows that condition (i) governs only the rewriting system and says nothing about information flow outside it. The dynamic setting has exactly such a channel by construction — the update mechanism itself — which the static setting lacks. Remark (This concern is named in advance in the source material). [4, Def. 6.7] names this phenomenon structural violation: a problem can be invariant at the level a formal statement checks, while an algorithm solving it leaks, as a side effect, exactly what that invariant was meant to hide. That source states the connection to the static SIP directly: a syntactic calculus cannot derive clauses violating a syntactic invariant, but a semantic computation solving an invariantrespecting problem can leak that invariant as an incidental side effect of how it computes [4, Rem. 6.8]. The same phenomenon appears in this paper’s dynamic setting, through a different channel: where that source’s structural violation is an algorithm’s output leaking what the problem statement kept invariant, here the potential leak is the update mechanism itself, evolving the rules in a way that would betray the order of a, b. Condition (ii) of Definition 3.2 is what rules that channel out. The two are instances of one concern — an invariant formally respected but betrayed by a side channel — named for the static/output case in [4] and closed for the dynamic/update case here. Proposition 3.6 (Individual necessity is open). Whether an update violating (ii) but satisfying (i) must always expose the order, or whether some remain safe by accident, is not established. Theorem 3.3 and Proposition 3.5 show joint sufficiency and that dropping either can fail; neither shows individual necessity nor minimality.

4

The limiting case: total opacity via the observational hierarchy

Condition (ii) is a hypothesis about how υ behaves, and Proposition 3.5 already showed this hypothesis can fail. This section asks a sharper question: can υ be built so that condition (ii) holds automatically, from what υ is even able to see, regardless of how it behaves? The answer is yes. The idea is simple: if the update mechanism is physically blind to the order of a, b — if it cannot even in principle tell the two symmetric cases apart — then however it is programmed, it cannot leak that order. The rest of this section makes “physically blind” precise and proves this. To say what an update mechanism can see, we first need a general notion of an observer. This is nothing more exotic than a hash function: something that sorts strings into buckets, inducing the equivalence “same bucket”, while never claiming that any string, or any bucket, is true or false. Definition 4.1 (Structural observer [5, Def. 3.1]). A structural observer is a function O : Σ∗ → S for some set S. It induces an equivalence x ∼O y ⇐⇒ O(x) = O(y), and does nothing more than this: O groups strings together, but never asserts that any of them is true or false. Say O1 ⪯ O2 (“O1 is no richer than O2 ”) if O1 = f ◦ O2 for some function f : every distinction O1 makes, O2 already makes too. The trivial observer O⊥ : x 7→ ⋆, which sends every string to the same single value, is the poorest observer possible: O⊥ ⪯ O for every O ([5, Def. 3.7, 3.11]). The next fact says precisely what it means for O⊥ to be the poorest observer possible: a system fed only O⊥ ’s output cannot recognise anything nontrivial, no matter how powerful it is otherwise. 8

Proposition 4.2 (Triviality of O⊥ [5, Cor. 2.8]). For any machine T and any language L ∈ / {∅, Σ∗ } (that is, any L that is neither empty nor everything), a system receiving only O⊥ (x) = ⋆ does not recognise L, regardless of computational power. We now specialise “poorest observer possible” to the specific symmetry that matters here: blindness to swapping a and b. Definition 4.3 (Swap symmetry). Write Hna↔b for Hn with every occurrence of a and b exchanged. A structural observer O is swap-blind with respect to a, b if O(Hn ) = O(Hna↔b ) for every Hn : swapping a and b never changes what O reports. Restricted to telling apart the swapped and unswapped case, O is exactly as powerless as O⊥ . The main result of this section follows: when the update mechanism’s only access to history is filtered through a swap-blind observer, condition (ii) holds automatically, for every update built this way — no longer something to be checked case by case, as in Proposition 3.5. Corollary 4.4 (Total opacity). Let (Rn )n≥0 be a dynamic rewriting system in which every update has the form Rn+1 = υ(Rn , O(Hn )), for one fixed swap-blind observer O and some υ satisfying Definition 3.2(i). Then for every such υ — not just some carefully chosen one — the conclusion of Theorem 3.3 holds. Proof. We only need to check condition (ii), since condition (i) is assumed directly. Condition (ii) asks for υ(Rn , Hn′ ) = υ(Rn , Hn ) swapped, where Hn′ = Hna↔b . Here is why this holds. By construction, υ does not see Hn directly; it only sees O(Hn ). Since O is swap-blind, O(Hn ) and O(Hna↔b ) are the same value: O(Hn ) = O(Hna↔b ) = O(Hn′ ). So υ, looking only at this shared value, cannot tell Hn and Hn′ apart either, and produces the same output from both: υ(Rn , Hn ) = υ(Rn , O(Hn )) = υ(Rn , O(Hn′ )) = υ(Rn , Hn′ ). This is exactly condition (ii), and it held without any case-by-case argument — it followed automatically from swap-blindness alone. With both conditions in hand, Theorem 3.3 applies directly. Remark (What swap-blindness buys: condition (ii) becomes structural). Corollary 4.4 changes the status of condition (ii). Before this section it was a hypothesis about behaviour, one that Proposition 3.5 showed can fail; for updates built through a swap-blind observer it becomes a structural guarantee that holds automatically. The reason is the one Proposition 4.2 already illustrated: information never received cannot be leaked, whatever the receiving mechanism then does with it. Condition (i) remains a separate hypothesis, so this is Theorem 3.3 specialised — the swap-blind observer discharges (ii) at the level of what υ can see, rather than (i).

5

Connection to Observer World and to the MR-OTP’s own invariance theorem

The last two sections built an abstract theory. This section connects it to results already published: two theorems from earlier papers are special, single-step cases of Theorem 3.3 once translated into its vocabulary. This serves two purposes. It confirms the new theory reproduces known results, not just plausible-sounding new ones. And it prepares genuinely new results: once a known static fact is recognised as a single-step case of a general dynamic theorem, extending it across many steps becomes a direct application of that theorem rather than a fresh proof.

5.1

Cell (d), the simplest instance, recalled and identified as the n = 0 case

We start with the simplest known result, “Cell (d)” from Observer World: an adversary who sees nothing at all about the plaintext learns nothing at all about it. This is almost a tautology as stated, but worth recalling precisely, because the next proposition shows it is already an instance of this paper’s general theorem. 9

Proposition 5.1 (Cell (d): Cryptomania × O⊥ [4, Prop. 4.9]). In Cryptomania, an adversary with observer O⊥ on the plaintext space cannot recover any information about the plaintext from the ciphertext, for any scheme. For the MR-OTP with C = (c1 , . . . , cL ) = Enc(M, K), C is O⊥ blind on M : the ciphertext-only adversary is structurally, not merely computationally, unable to distinguish any two plaintexts [4, Remark 4.10]. To see this as an instance of Corollary 4.4, we need a dictionary between the two settings. The role of (a, b) — the two symmetric values whose order stays hidden — is played here by two candidate plaintext digits (m, m′ ): “the order of a, b” becomes “which of m, m′ was actually encrypted”. Proposition 5.2 (Cell (d) as the n = 0 instance of total opacity). Fix a position i and two candidate digits m, m′ there, with every other digit and key held fixed. Under the dictionary above, Proposition 5.1 is exactly what Corollary 4.4 concludes in the degenerate case n = 0 (a single step, with nothing further happening), taking O = O⊥ . Proof. Let R0 stand for the MR-OTP map under a fixed base B, extended formally by υid so that the system is well-defined for every n; only n = 0 actually matters here, since no further encryption happens in this setting. We check the two conditions of Corollary 4.4 in turn. For condition (i): the adversary’s observer is O⊥ on the plaintext space, meaning the adversary’s operations never depend on M beyond what O⊥ discloses — which is nothing. So no operation ever “fires at” m or m′ directly, and condition (i) holds. For condition (ii): υid does not depend on history at all (this was already verified, in the strongest possible sense, in the proof of Corollary 3.4), so it is certainly swap-blind. With both conditions verified, Corollary 4.4 applies at n = 0, and its conclusion is exactly Proposition 5.1. Remark (Purpose: calibrating the correspondence). This n = 0 identification calibrates the correspondence before it is put to work below: first to recover a slightly richer static instance (Section 5.2), then to extend both to a dynamic setting (Section 5.3). Cell (d) itself is a known result.

5.2

Recovering the distributional instance as a natural generalization

Proposition 5.2 used the simplest possible observer, O⊥ : the adversary sees nothing about the plaintext at all. The MR-OTP’s own invariance theorem allows the adversary slightly more — the base B — and asks whether that extra information changes anything. It does not, for the same underlying reason. Proposition 5.3 (Theorem 8.15 of [3] as a degenerate instance of Theorem 3.3). Fix a message digit position, and two candidate values m, m′ for M there, with everything else held fixed. Consider a single fresh MR-OTP encryption, with an adversary who is additionally given the base B. This is a length-1 dynamic rewriting system: R0 is the MR-OTP encryption map under base B, there is no R1 , and the adversary’s observer is O = (B, · ) — the base together with the ciphertext, but not the key. Under this reading, Corollary 4.4’s conclusion at n = 0 is exactly [3, Thm. 8.15]: Pr[M = m | C = c, B = b] = Pr[M = m] for all m, c, b. Proof. As in the proof of Proposition 5.2, extend R0 formally by υid so the system is well-defined for every n, with only n = 0 actually mattering. We check condition (ii) first, since it takes more Q work here. K is uniform and independent of both B and M , so Pr[C = c | M = m, B = b] = i 1/bi does not depend on m ([3, Prop. 8.1]). B itself is fixed and public, so it is independent of M and K as well. Together, these two facts say that the distribution of O = (B, C), conditional on M = m, is the same as its distribution conditional on M = m′ — which is exactly swap-blindness with respect to (m, m′ ). 10

Condition (i) follows even more easily, exactly as in the proof of Proposition 5.2: υid does not depend on history at all. With both conditions verified, Corollary 4.4 (with this O) applies at n = 0, giving exactly [3, Thm. 8.15]. Remark (Same argument, richer observer). Proposition 5.3 and Proposition 5.2 (Cell (d)) come from the same n = 0 argument, differing only in what the observer O is allowed to see: Cell (d) uses O = O⊥ , nothing about the plaintext; here O = (B, · ), since the base is public even though the key is not. Both are swap-blind with respect to (m, m′ ) for one underlying reason: because K is uniform and independent of everything else, C’s distribution never depends on M , regardless of what else the adversary is given, as long as it excludes K itself. Theorem 3.3 makes this the same fact doing the work in both cases — a single fact that [4] and [3] each discovered independently, one instance apiece, without citing the other.

5.3

The dynamic extension: base-rolling under a swap-blind update

Both static instances above cover one encryption. Neither [4] (static only) nor [3] (which poses Open Problem 6.4 but proves nothing about it) addresses the base-rolling scenario Bt+1 = f (Ct , Bt ). This subsection supplies the theorem, covering both instances at once. Definition 5.4 (Base-rolling dynamic system). Fix a position i and symmetric candidates (m, m′ ) at session 1. A base-rolling dynamic system is a sequence of MR-OTP sessions in which the base itself evolves, Bt+1 = υ(Bt , Ht ), with Ht = (C1 , . . . , Ct ). This matches Definition 3.1, where Rt plays the role of the MR-OTP map under Bt , and Dt plays the role of session t’s encryption. Theorem 5.5 (Dynamic Cell (d)). Let (Bt )t≥1 be a base-rolling dynamic system. Fix any session s ≥ 1 and symmetric candidates (m, m′ ) for Ms at some position, with everything else at session s held fixed. Assume two things about υ. First, υ(Bt , Ht ) depends on Ht only through O(Ht ), for one fixed structural observer O that is swap-blind with respect to (m, m′ ) at session s. Second, υ never lets Bt+1 depend directly on any session’s key digits. Then for every t ≥ s, Pr[Ms = m | Ht , Bs+1 , . . . , Bt ] = Pr[Ms = m | Hs ], where Ht = (C1 , . . . , Ct ). Two special cases are worth stating on their own. Taking t = s recovers ordinary session-bysession secrecy at every session, Pr[Mt = m | Ct = c, C1 = c1 , . . . , Ct−1 = ct−1 ] = Pr[Mt = m] for every t — the secrecy target whose preservation under a rolling base Open Problem 6.4 is concerned with, here established in the swap-blind, partition-structured regime. Taking t > s gives something stronger and more persistent. Suppose the adversary is handed every subsequent base Bs+1 , . . . , Bt outright, in full — not merely whatever υ’s public behaviour reveals about them indirectly. Even then, nothing in this later, fully-revealed base evolution ever reveals more about which of m, m′ was encrypted at session s than was already knowable immediately after that session. Proof. This proof mirrors the proof of Corollary 4.4, read distributionally (Remark 2.2) and reindexed to start at session s rather than at n = 0: (m, m′ ) plays the role (a, b) played there, and Bt plays the role Rn played there. By Proposition 5.1 (or Proposition 5.3, with Bs included in the observer), P holds right after session s; this is the base case. The hypothesis on υ gives the distributional analogue of condition (i) for every t ≥ s. Swap-blindness of O gives condition (ii) automatically, exactly as in the proof of Corollary 4.4. Each Ct with t > s is produced under a fresh key, independent of session s’s key (this is the partition structure of [3, Def. 6.1]), so Ct carries no further information about Ms beyond what Bt already carries. 11

Induction on t ≥ s now transports Theorem 3.3’s argument distributionally, giving the claim at every session t ≥ s. Since s itself was arbitrary, the claim holds for every session, not only for one distinguished first session. Remark (What this adds, and how it relates to Open Problem 6.4). Theorem 5.5 stands on its own: it extends the static Cell (d)/Theorem 8.15 secrecy to a rolling base under a swap-blind update, and the t > s case adds a persistence guarantee — secrecy about session s survives arbitrarily many further sessions, even when the adversary is handed every subsequent base outright — that no source result states. Its relation to Open Problem 6.4 is one of shared shape, not of solution. The t = s case meets the secrecy target that problem is concerned with, but in the swap-blind regime and under the partition structure of [3, Def. 6.1]; the distinctive thing Open Problem 6.4 asks — whether that target can be met by an f giving a larger base search space than the partition protocol, without its disjointness condition — is not addressed here, and neither is the construction of a concrete, practically superior f . Both remain open, and a fuller account of the connection would need an argument this paper does not undertake. Remark (One theorem covers both static instances). The proof above is agnostic between using Proposition 5.1 and Proposition 5.3 as its base case — they differ only in whether Bs is included in the observer — so Theorem 5.5 extends both Cell (d) and the MR-OTP’s own invariance theorem to the dynamic setting at once. The richer (B, · )-observer instance is already covered, with no separate dynamic theorem required.

6

Connection to the order-blind automaton, and its dynamic extension

This section repeats the pattern of Section 5 with a third source result: an automaton that can only read a count of each symbol, never their order. As before, we recall the static result, show it is a single-step case of this paper’s general theorem, then extend it across many steps.

6.1

The static result recalled

An order-blind automaton does not read a string symbol by symbol. It first reduces the string to its profile — a histogram of how many times each symbol occurs, exactly the “bag of words” representation familiar from basic text processing, with the order thrown away entirely — and only then decides. Definition 6.1 (Profile, order-blind automaton [5, Def. 2.1, 2.3]). The profile of a string x is prof(x) = (c1 , . . . , ck ) ∈ Nk , where ci = |x|ai counts occurrences of the i-th symbol. An orderblind automaton is A = (Q, Σ, δ, q0 , F ) with transition function δ : Q × Nk → Q, recognising L(A) = {x | δ(q0 , prof(x)) ∈ F }: the profile is read in a single step, and the symbol sequence itself is never read at all. Theorem 6.2 (Characterization [5, Thm. 2.5]). L is recognisable by an order-blind automaton if and only if L is permutation-closed (closed under reordering the symbols of any string in it). Corollary 6.3 ([5, Cor. 2.8]). For any machine T and any L ∈ / {∅, Σ∗ }, a system receiving only O⊥ (x) = ⋆ does not recognise L, regardless of computational power. The structural fact behind this, stated in [5, Remark 2.7], is that the power of the machine cannot compensate for the weakness of the observer. Capturing it needs a notion of blindness more general than Definition 4.3: permutation-closure requires invariance under every transposition of positions, not one fixed swap. The difference from the richer observer (B, · ) of Section 5.2 is not quantitative but qualitative: not one more piece of information withheld, but blindness to an entire group of symmetries at once. 12

6.2

Generalizing swap-blindness to permutation-blindness

Definition 6.4 (Permutation-blind observer). A structural observer O is permutation-blind if O(x) = O(y) whenever prof(x) = prof(y): in symbols, O ⪯ Oprof . This is the analogue of Definition 4.3 for a different symmetry: where swap-blindness hides one fixed transposition of the two symbols a, b, permutation-blindness hides the entire symmetric group acting on the positions of the input. The two are not nested — they are blindness to different group actions on different objects (the two Skolem symbols in one case, the input positions in the other) — but they are instances of one scheme, as Remark 6.2 below records. With this notion in hand, Corollary 6.3 follows from the same argument as Corollary 4.4 — this time with the observer’s blindness spread across every permutation of the input positions, rather than the one a ↔ b swap that Corollary 4.4 is stated for. The argument does not depend on which of the two symmetries is in play, only on the observer being blind to whatever the hidden invariant is; Proposition 6.5 carries it out explicitly for the permutation case, and Remark 6.2 states the shared form. Proposition 6.5 (Theorem 6.2’s negative direction as the static, fully-permuted case). Let L ∈ / {∅, Σ∗ } be not permutation-closed. Then Corollary 6.3 follows at n = 0 from the same argument that proves Corollary 4.4, with O permutation-blind (Definition 6.4) in place of the swap-blind observer that corollary is stated for. Proof. Let R0 stand for the order-blind automaton’s classification map, extended formally by υid . For condition (i): classification depends on x only through prof(x), so no operation ever fires on the specific symbol-order information that distinguishes two permutations of the same profile. This is exactly condition (i), under the full symmetric-group symmetry of Definition 6.4. For condition (ii): as in the proof of Corollary 3.4, υid ’s independence from history gives condition (ii) immediately. With both conditions verified, Corollary 4.4 (taking O permutation-blind) applies at n = 0, and its conclusion is exactly the negative direction of Corollary 6.3/Theorem 6.2. Remark (Calibrating the generalization). As in Section 5.1, this identification calibrates the generalization before it is put to work below; the order-blind characterization itself is a known result. Remark (The general form behind Corollary 4.4). Corollary 4.4 is stated for a swap-blind observer, but its proof uses only one property of that observer, and a more general statement holds with the same proof. Let G be any group acting on histories, let O be an observer with O(H) = O(g · H) for every g ∈ G (blindness to the whole G-action), and suppose the hidden invariant — the fact the derivation must not expose — is exactly a G-invariant. Then any update of the form Rn+1 = υ(Rn , O(Hn )) satisfies Definition 3.2(ii) automatically: since υ sees the history only through O, and O cannot separate Hn from any g · Hn , the update returns the same rule set on all of them, so it cannot leak which G-orbit representative the history was. The swap-blind case is G = Z2 acting by the a ↔ b exchange (Corollary 4.4); the permutationblind case is G = S|x| acting on input positions (Proposition 6.5). Both are the same fact: condition (ii) is free whenever the update’s only view of history factors through blindness to the group whose invariance is what must stay hidden. We keep Corollary 4.4 in its swap-blind form, since that is the case the dynamic sections use, and record the general version here rather than as a separate theorem, nothing below depending on more than the two named instances.

6.3

The dynamic extension: streaming under a permutation-blind update

The question asked twice already — does the static guarantee survive if the observer itself evolves? — applies here too. Now the observer changes not across sessions of one cipher, but 13

across a stream of many different inputs. Definition 6.6 (Streaming profile system). Consider a sequence of inputs x1 , x2 , . . . , each read by its own observer O1 , O2 , . . . , where the observer itself evolves as Ot+1 = υ(Ot , Ht ) for Ht = (O1 (x1 ), . . . , Ot (xt )). This matches Definition 3.1, with Rt playing the role of Ot , and Dt playing the role of the t-th classification. Theorem 6.7 (Dynamic order-blindness). Let (Ot )t≥1 be a streaming profile system satisfying two conditions. First, every Ot is permutation-blind. Second, υ(Ot , Ht ) depends on Ht only through a permutation-blind function of Ht . Then, for every t and every Lt ∈ / {∅, Σ∗ } that is not permutation-closed, no machine receiving O1 (x1 ), . . . , Ot (xt ) can correctly decide xt ∈ Lt on both members of some prof(xt )-equivalent pair — regardless of computational power, and regardless of how the observer sequence evolved. Proof. This is Theorem 3.3, transported through Corollary 4.4, with the single transposition a ↔ b generalized to the full symmetric group, exactly as Definition 6.4 generalizes Definition 4.3. By Proposition 6.5, applied at the very first input x1 with O1 in place of the single fixed observer there, P holds right after the first step; this is the base case. Condition (i) holds because every Ot ⪯ Oprof : no observer in the sequence ever exposes order. Condition (ii) holds because υ’s choice depends on history only through permutation-blind data, so two runs that agree on every profile but differ in actual order produce identical observer sequences at every step. Induction, exactly as in the proof of Theorem 3.3, now gives the claim at every t, applying the negative direction of Theorem 6.2 at each step. Remark (What this adds). The time index and the evolving observer are new: [5] has neither. The extension holds for every permutation-blind schedule; constructing a concrete, useful, nontrivial schedule beyond the fixed Oprof remains open. Remark (The pattern across all four recovered instances). Sections 5.1–6 have now shown the same architecture four times, at three levels of observer richness — these four being the recovered instances, results already in the source papers re-derived here as one pattern, distinct from the four independently arising instances taken up later (Sections 8, 10, 11, 12). The simplest, O⊥ level blindness appears twice, in two unrelated domains: which of two Skolem constants was used, in the static SIP itself (Section 3), and which plaintext was encrypted (Cell (d)). These two are parallel appearances of the same simplest case in different settings, at the same level of the observer order, neither ordered relative to the other. Richness then increases genuinely twice: once inside cryptography, from O⊥ to (B, · ) on the plaintext (Theorem 8.15), and once by generalizing from a single transposition to the full symmetric group (the order-blind automaton’s Oprof -blindness). Each of the four instances is recovered as the degenerate, single-step case of Theorem 3.3, and each yields a new dynamic extension via Corollary 4.4, save where one dynamic theorem already covers two static instances at once (Remark 5.3). That the same theorem, at one fixed level of generality, recovers all four independent source instances and extends each is evidence it sits at the right level for the phenomenon common to all four.

7

The silent assumption behind Dynamic SIP: semantic interpretation frames

7.1

The same move, three times

The static Syntactic Invariance Principle (Lemma 2.4) silently assumes a single, fixed rewriting system R; making that assumption explicit and asking what happens when R is allowed to change produced Theorem 3.3, the Dynamic SIP. This move — take a result held finished, find 14

the assumption it never stated, and turn that assumption into a variable — is the recurring engine of this work, and one of its own source papers runs on the same engine. [4, Abstract] observes that all five of Impagliazzo’s worlds [15] assume every party, adversary included, observes the complete input — an assumption so natural that, in that source’s own words, “it is never stated”; that paper’s entire contribution is to make it explicit and relax it. The same sentence structure, applied to a different silent assumption (full observation, rather than a fixed rule set), by the same author, independently motivated an entire second paper. Theorem 3.3 makes a silent assumption of its own. It is stated entirely at the level of derivability — what a syntactic system can or cannot produce — and says nothing about how a reader, or a machine, interprets what is derived. Implicitly, it assumes whoever reads the derivation reads it against one fixed, intended model, the same one throughout. This section makes that assumption explicit, following the same pattern a third time: state the theorem, find what it silently fixed, and let that vary. Once the interpreting model is not fixed, a phenomenon appears that no result so far in this paper, and none in the four source papers, addresses. Remark (A first, concrete encounter with the frame idea). An executable file for MS-DOS, read by a modern Linux kernel, is not corrupted: every byte is exactly what it was written to be. What differs is what the reader takes those bytes to mean. Nothing in the file signals which reading is intended, and a reader committed to one interpretation produces a definite, internally consistent result whether or not that interpretation is the one the bytes were written under. The reader’s choice of interpretation is doing work the bytes themselves leave open — a role played, later in this paper, by an explicit frame chosen independently of the syntax it reads. This section makes the phenomenon precise for the syntactic systems studied here, where it is provable rather than merely evocative; the concrete picture is worth keeping in mind, because the same structure recurs in richer form.

7.2

Semantic frames

A semantic frame is simply a concrete mathematical structure that gives a specific meaning to the symbols 0, s, + and to the constants a, b — one particular way of reading the syntax as being about actual objects. Definition 7.1 (Semantic frame). A semantic frame for L = {0, s, +} is a structure F with domain DF , interpreting 0, s, + as 0F , sF , +F , together with a designated interpretation aF , bF ∈ DF of the Skolem constants a, b. F models a rewriting system R if every rule of R holds in F under this interpretation (e.g. F models {A1, A2} if 0F +F x = x and sF (x) +F y = sF (x +F y) for all x, y ∈ DF ). Remark (Semantics and syntax behave oppositely here). Lemma 2.2 shows the syntax of {A1, A2} never derives either a + b = b + a or its negation: the syntactic system is permanently silent on the question. A semantic frame F cannot be silent this way. Since F is a specific structure, aF +F bF and bF +F aF are specific, definite elements of DF , and either they are equal or they are not — F always has an answer, automatically, whether or not anyone asks. This is the precise sense in which the two behave oppositely: syntax withholds an answer; any given semantic frame supplies one, unasked, and with no mechanism for flagging that the answer it supplies might not be the only one consistent with the syntax it reads.

7.3

Two frames, the same syntax, opposite answers

Here is the phenomenon this section is built around, stated as starkly as possible before any formalism: the same file, byte for byte unchanged, can mean two different and mutually exclusive things to two readers, with nothing in the file able to settle which reading is right. This is not merely possible but forced — for the simplest arithmetic system there is.

15

Theorem 7.2 (Semantic underdetermination). There exist semantic frames F1 , F2 , both modelling {A1, A2}, with F1 |= a + b = b + a and F2 |= a + b ̸= b + a. Proof. F1 : the standard model. Let DF1 = N with the usual 0, s, +, and aF1 = 3, bF1 = 5. Standard addition satisfies {A1, A2} trivially, and 3 + 5 = 5 + 3 = 8, so F1 |= a + b = b + a. F2 : an explicit non-standard model. Let DF2 = N ∪ {a∗ , b∗ } for two fresh elements a∗ ̸= b∗ , ∗ a , b∗ ∈ / N. The idea, stated before the mechanics: a∗ and b∗ act as two different “sinks” that swallow whatever they are added to, and whichever one appears as the left argument wins — this single asymmetry is what breaks commutativity. Define sF2 to agree with the usual successor on N, and sF2 (a∗ ) = a∗ , sF2 (b∗ ) = b∗ (fixed points outside the standard part). Define +F2 by cases: • x, y ∈ N: the usual sum. • x = a∗ (any y ∈ DF2 ): a∗ + y := a∗ . • x = b∗ (any y ∈ DF2 ): b∗ + y := b∗ . • x ∈ N, y = a∗ : x + a∗ := a∗ . • x ∈ N, y = b∗ : x + b∗ := b∗ . (These five cases cover every pair (x, y) ∈ DF2 × DF2 exactly once.) F2 satisfies A1 (0 + x = x). For x ∈ N: standard. For x = a∗ : 0 + a∗ = a∗ by the fourth case (0 ∈ N). For x = b∗ : 0 + b∗ = b∗ by the fifth case. F2 satisfies A2 (s(x) + y = s(x + y)), checked exhaustively over all five shapes of (x, y): • x, y ∈ N: both sides equal the standard s(x + y). • x ∈ N, y = a∗ : s(x) ∈ N, so s(x) + a∗ = a∗ (fourth case); and s(x + a∗ ) = s(a∗ ) = a∗ (fourth case, then fixed point). Equal. • x ∈ N, y = b∗ : symmetric, both sides = b∗ . • x = a∗ (any y): s(a∗ ) + y = a∗ + y = a∗ (fixed point, then second case); and s(a∗ + y) = s(a∗ ) = a∗ (second case, then fixed point). Equal. • x = b∗ (any y): symmetric, both sides = b∗ . So F2 models {A1, A2}. F2 disagrees on the order. Set aF2 = a∗ , bF2 = b∗ . Then aF2 +bF2 = a∗ +b∗ = a∗ (second case), while bF2 +aF2 = b∗ +a∗ = b∗ (third case). Since a∗ ̸= b∗ by construction, F2 |= a+b ̸= b+a. Corollary 7.3 (The MS-DOS phenomenon, made precise). Fix any derivation under {A1, A2} with Skolem constants a, b (which, by Lemma 2.2, never touches a + b or b + a at their root). This single syntactic object is compatible with both F1 and F2 of Theorem 7.2: nothing in the derivation determines, or even hints, which of the two mutually exclusive readings is intended. A reader (or machine) fixed on F1 will treat “a + b = b + a” as available and true; a reader fixed on F2 will treat it as false; neither receives any signal that the other reading exists, is possible, or is equally consistent with everything the syntax says.

7.4

A worked example of use: ciphertexts without redundancy

The arithmetic instance above is deliberately minimal, to make the phenomenon provable in full rather than merely evocative. The same structure recurs, with no further construction needed, in an entirely different and immediately recognisable setting.

16

Proposition 7.4 (Cryptographic instance of semantic underdetermination). Let Σ = {0, 1}, plaintext space M = Σn (every n-bit string a valid plaintext: no header, no reserved bits, no checksum), key space K = Σn , and Enc(M, K) = M ⊕ K = Dec(M, K) (one-time pad). Fix any ciphertext C ∈ Σn . For any two distinct keys K1 ̸= K2 ∈ K, let M1 := Dec(C, K1 ) = C ⊕ K1 and M2 := Dec(C, K2 ) = C ⊕ K2 . Then: (i) M1 ̸= M2 (since M1 ⊕ M2 = K1 ⊕ K2 ̸= 0n ); (ii) M1 , M2 ∈ M: both are, without qualification, valid plaintexts, since M = Σn has no internal structure a decryption could violate; (iii) C alone does not determine which of K1 , K2 (hence which of M1 , M2 ) is correct: every one of the 2n pairs (K, M ) with M ⊕ K = C is equally consistent with C, and nothing in C privileges one over another. Proof. (i) M1 ⊕ M2 = (C ⊕ K1 ) ⊕ (C ⊕ K2 ) = K1 ⊕ K2 , nonzero since K1 ̸= K2 . (ii) Immediate, since M = Σn places no constraint beyond length. (iii) For every K ∈ K, setting M := C ⊕ K gives Enc(M, K) = M ⊕ K = C: every key yields some plaintext consistent with C, and by (ii) every such plaintext is well-formed, so no candidate is excludable on internal grounds. Remark (Why redundancy checks exist). This is the structural reason redundancy checks (headers, MACs, checksums) exist in real cryptographic practice: every key here gives an equally valid reading, with nothing to exclude any of them on internal grounds. A MAC or checksum is exactly an attempt to break this underdetermination by adding a rule — analogous to adding a third axiom to {A1, A2} — that only the intended key’s decryption satisfies.

7.5

Two further worked examples

Proposition 7.5 (The MS-DOS instance, made precise). Let b ∈ {0, 1}N be a byte string with no distinguishing header — as in the classical .COM executable format, where the entire string is executed directly as machine code from a fixed offset, with no reserved signature bytes (unlike .EXE or ELF, both of which do carry a magic header precisely to avoid the phenomenon below). Let L1 , L2 be two interpreters (loaders), each a partial function from byte strings to execution behaviour in some domain B, corresponding to two incompatible instruction-set conventions. Then: b is identical regardless of which loader receives it; neither L1 nor L2 receives, from b alone, any signal indicating which convention was intended; and L1 (b), L2 (b) ∈ B can be arbitrary and unrelated to one another (including one being well-defined, meaningful behaviour and the other being undefined, degenerate, or simply different well-defined behaviour), with b itself giving no indication that a mismatch has occurred. Remark (Level of formality). This proposition is stated at the level of generality the point needs, and no further: it does not fix a specific B or specific L1 , L2 with a full instruction-set semantics, since the claim concerns any header-free byte string under any two incompatible conventions, and formalising two complete ISAs is orthogonal to it. The opening picture (Remark 7.1) is now a claim about arbitrary header-free byte strings and interpreters, rather than an anecdote. Proposition 7.6 (Transformation-cascade cipher). Let Enc0 be a cipher such that, for a uniformly random key, Enc0 (M ) is computationally indistinguishable from a uniformly random string of Σn (a standard assumption on Enc0 , e.g. a strong pseudorandom permutation; we do not prove this property, only assume it). Fix a public toolkit T of classical transformations (permutations, substitutions) on Σn , each a bijection. Given plaintext M , compute C0 = Enc0 (M ), then apply a secret sequence of k ≥ 0 transformations t1 , . . . , tk ∈ T (secret both in number k and in which elements of T , and in what order), obtaining C = tk (· · · t1 (C0 ) · · · ), retained with no header or checksum. Then, for any candidate k ′ ≥ 0 and any candidate sequence b0 := (t′ )−1 (· · · (t′ ′ )−1 (C) · · · ) is a well-defined element t′1 , . . . , t′k′ ∈ T , the candidate recovery C 1 k 17

of Σn (since every t ∈ T is a bijection), and is, under the assumption on Enc0 , computationally indistinguishable from C0 itself regardless of whether the candidate sequence is the correct one: nothing in C certifies which candidate recovery, among the combinatorially many choices of (k ′ , t′1 , . . . , t′k′ ), is correct. Remark (Two phenomena compounded: underdetermination and search). This construction illustrates the interaction of two phenomena the rest of the paper keeps separate. The underdetermination of Section 7 — no internal check distinguishes a correct recovery from an incorrect one, exactly as in Proposition 7.4 — compounds with a combinatorially large search space (candidates range over all finite sequences from T ) to produce a search problem with no verifiable stopping condition short of external information: not merely hard to search, as in the Base Recovery Problem of [3], but, absent external information, not verifiably searchable at all. Two matters bound the scope of this. The noise-likeness of Enc0 is a computational assumption, not the information-theoretic guarantee of the one-time pad in Proposition 7.4; and the classical transformations, all bijections on a fixed-size alphabet, add no entropy of their own. The underdetermination half is this paper’s subject; the resulting search-complexity question is a separate matter, recorded here but not developed.

7.6

The blind-cascade cipher: security by removal of the verification predicate

Proposition 7.6 is worth developing on its own, because when the secret sequence is itself keyed and its length is a further secret, the construction exhibits a security property that deserves to be stated and proved carefully — not because the scheme is one to use in practice, but because it exposes, by carrying it to its limit, the hidden assumption behind almost all of cryptography: that there is some way to recognise a correct decryption. We call the scheme the blind-cascade cipher, there being, as far as we know, no established term in the literature for a construction of this shape. The construction The plaintext M is carried to the ciphertext C in layers. First, a base encryption: one chooses a strong standard cipher Enc0 from among n candidates — the choice itself secret — and a key K1 , and computes C0 = Enc0 (M, K1 ). Under the standard assumption on Enc0 , C0 is indistinguishable from a uniform string: already here, to anyone without K1 , C0 is noise. Next, a confusion cascade: fix a public set T = {τ1 , . . . , τm } of classical reversible bijections on strings — permutations, substitutions, rotations, row and column swaps, and any other confusion operation — and apply to C0 a sequence of L layers of operations drawn from T . The number of layers L is a third secret parameter, given as input, and used to derive a second key K2 . The operations of layer i — which, how many, in what order, with what parametrising bits — are determined by κi = KDF(K1 , K2 , i). No fresh random bit enters after K1 : the whole system is a deterministic expansion of the seed s = (K1 , K2 , L). Write C = Φs (M ) for the entire transformation, and Φ−1 s for its inverse, computable by whoever holds s. The ciphertext C carries no header, no checksum, no verification oracle of any kind: nothing in C records how many layers, which operations, or which base cipher. The legitimate recipient, holding s and the choice of cipher, reconstructs the κi , inverts the layers in order, and decrypts C0 . The attacker’s position The most direct way to see why the scheme is strong is to try to break it. The attacker has C and nothing else: not K1 , not K2 , not L, not which base cipher among n; no header, checksum, or oracle. Suppose the attacker tries to decrypt. The confusion layers must be unwound first, but their number and identity are unknown. Applying the inverse τj−1 of some bijection yields 18

a string — is it closer to the solution? There is no way to tell: the string is noise, as C was, as anything the attacker produces will be. Another operation: again noise. There is no gradient to follow, no signal reading “warmer, colder.” Every move must be tried as though it were the right one, because nothing distinguishes it from a wrong one. Suppose fortune intervenes and the attacker unwinds every layer correctly, arriving at C0 . They would not know it: C0 is the output of a strong cipher, as indistinguishable from uniform as any failed attempt. They hold the intermediate solution and cannot recognise it. And if they went further, guessed K1 and the cipher and obtained M — again, with no expected plaintext to compare against, they would not know they had finished. We now make this experience precise, in two steps: first how many attempts the attacker faces, then — the crux — why no attempt yields any information. Proposition 7.7 (Relative unboundedness of the attack space). Let T be the public, non-empty set of confusion bijections, each with a parametrisation of size at least 2, and let C = Φs (M ). An adversary without the seed s and without a verification oracle has no effective upper bound L⋆ on the number of layers: for every ℓ there is a valid seed s′ with exactly ℓ layers such that Φ−1 s′ (C) is a well-formed plaintext. P The set of operation sequences the adversary must consider therefore has cardinality at least ℓ≥1 |T |ℓ , which diverges whenever |T | ≥ 1. Proof. Since every τ ∈ T is a bijection, every finite composition of operations from T is a bijection, so for each length ℓ and each choice of operations the resulting map sends C to some string, which is a well-formed plaintext (every string is, absent an imposed format). There is thus no ℓ beyond which the attempts are empty: the space to be traversed is not bounded above by any L⋆ derivable from C. Since T is non-empty, the number of sequences of each finite length is at least one and the total diverges over unbounded ℓ. The count alone does not ground the security — an unbounded space whose elements carried a signal of correctness would be traversed by a guided search, eliminating candidates as they failed. The decisive point, established next, is that no such signal exists: no candidate is eliminable, because eliminating one would require verifying its outcome, and no verification is available. It is this, not the size of the space, that does the work. Proposition 7.8 (Indistinguishability of outcomes: no verification predicate). Under the assumption that Enc0 produces output indistinguishable from uniform, for every pair of operation sequences u ̸= u′ applicable to C, the outcomes u−1 (C) and u′−1 (C) have the same distribution in the eyes of any observer not holding the seed s. Consequently there is no function Verify(·) that, given a candidate decryption of C and without access to s, returns “correct / incorrect” with success probability above chance. Proof. Each operation of T is a public bijection; applying or inverting it is a one-to-one transformation that neither adds nor removes information about the seed. The only source of structure that would distinguish the correct outcome is the plaintext M ; but that structure is reachable only after all layers have been inverted with the right parameters and Enc0 decrypted with K1 — that is, only with s. Without s, the outcome of every sequence is a bijective function of C, and C is by assumption indistinguishable from uniform; hence all outcomes are, for the observer without the key, samples from the same distribution. A Verify effective against chance would constitute a test distinguishing the correct outcome from the others — that is, a test distinguishing C0 = Enc0 (M, K1 ) from uniform, against the assumption on Enc0 . It is this second proposition that carries the security to the level required. The first says the paths are unbounded; the second says no path is distinguishable from another — and it is the second that matters, because it is what makes the search not merely long but without a stopping criterion. The structure that would seem to signal success can arise from an incorrect decryption as readily as from the correct one — confusion bijections applied to wrong bits 19

produce apparent structure continually — so that the apparent signal is indistinguishable from the noise that imitates it. The point of view, and a concept to keep in mind What we obtain, which is like what one obtains from Shannon’s one-time pad but from a different point of view, is: an output indistinguishable from noise for anyone without a key. A concept we shall return to, and that it is worth beginning to keep in mind. The point of view is different because the way the information identifying the correct reading is made inaccessible is opposite: in the one-time pad that information is absent because the key is uniform and as long as the message; here it is absent because every verification has been removed, at every layer. In both cases the result, for the observer without the key, is the same — an output fully determined and at once indistinguishable from true noise. The strength is thus one of kind, not of degree: not “the attacker must do a great deal of work,” but “the object — the verifier — that would turn work into an answer does not exist.” This is why the entropy of the seed, finite as it is, is not the right measure: it would count the cost of a search, but a search is defined only where the solution is recognisable, and here it is not. Reflexes to set aside The scheme is simple but far from the ordinary use of cryptography, and one examining it slips almost inevitably into a sequence of reflexes. Each is correct in its usual context and misleading here. “Security is the entropy of the key.” The instinct computes |K1 | + |L| + log2 n and concludes: finite security. But entropy measures the cost of a search, and a search is well defined only if the solution is recognisable. By Proposition 7.8 it is not here. Counting the seed’s bits — correct in itself — measures a procedure that cannot conclude. “The attacker enumerates keys and verifies.” Verifies with what? Proposition 7.8 says that Verify without s does not exist. Enumeration remains possible but does not conclude. “When structure emerges, I have decrypted.” The structure can emerge false, from chance; it certifies nothing. It is the systematic decoy of the proof above. “The space of cascades is finite, hence enumerable.” Finite for whoever holds the seed (the recipient); unbounded and undifferentiated for whoever does not (Proposition 7.7). Finiteness is relative to the observer — as is every notion in this paper. “If it is secure it must be usable, so there is a flaw.” Usability is not a requirement: this is a theoretical object, studied for its mathematical properties. Unusability is not a flaw but the direct manifestation of the property. A note on robustness A scheme with no internal verification is fragile against transmission errors. This is resolved without touching the property, by enclosing the blob in an external container with a checksum — a compressed archive, say. The checksum verifies the channel, not the reading: it confirms that the bits arrived intact, not which of their decryptions is correct. Verification of transport integrity sits outside the blob and reinstates no oracle on the content. Why it has not been isolated before That a property this sharp has not been isolated is not an oversight of the field: it is that the object lies in the exact blind spot of the five reflexes. The standard cryptographic eye measures entropy, presupposes a verifier, trusts emerging structure, counts a finite space, assumes usability.

20

An object that becomes more secure precisely where it becomes unusable, and whose security grows by subtraction of verification rather than by addition of work, falls outside all five. Remark (A further silent assumption removed: the verification oracle). Most discussions of ciphertext recovery, including standard security-game formalizations, silently assume some means of recognising a correct decryption once found — a header or checksum, or, in the knownplaintext setting, the adversary’s prior knowledge of what the plaintext should look like. The construction of Proposition 7.6 removes this assumption too, not only the header: with no checksum and no known plaintext to compare against, nothing — internal to the ciphertext or b0 is the right one, even to someone who external to it — certifies that any candidate recovery C has correctly guessed the transformation sequence. This is one more instance of the pattern the paper traces throughout: an assumption so natural it usually goes unstated. Making it explicit is what lets the construction reach the same structural property Theorem 7.2 isolates — no check, of any kind, available to any party, distinguishes a correct reading from an incorrect one — rather than the information-theoretic guarantee of the one-time pad, which Remark 7.5 already separates off. A system built this way has essentially no practical use, since the legitimate recipient equally has no way to confirm success; this is exactly why real systems reinstate a verification oracle deliberately. The point of recording it is the same as the rest of this section’s: to show precisely which assumption does the protective work, by exhibiting what remains once it is removed. Remark (Scope: a fixed frame, read against a static or dynamic syntax). Theorem 7.2 and Corollary 7.3 concern a single, fixed semantic frame F , read against a syntactic system that may itself be dynamic (Section 3) or static (Section 2). A frame that itself changes over the course of a derivation — a “semantic frame selector” ϕ with Fn+1 = ϕ(Fn , Hn ), parallel in shape to the syntactic update υ of Definition 3.2 — is a different object, not treated here. An evolving frame alongside an evolving rule set (Rn ) is a genuine two-axis system, and the frame constructed here stays on one axis: F1 , F2 are simply and verifiably true frames, not assertions engineered to contradict anything. There is also a prior question of what “opacity-preserving” should even mean for a frame selector ϕ: a frame update changes what is true, not merely what has been derived, and the two are governed by different logical rules, so the two conditions of Definition 3.2 do not transfer to ϕ by analogy. Remark (Why this is a separate fact from Theorem 3.3). A theorem that does not mention a phenomenon is not thereby a theorem about it. Theorem 3.3 quantifies over derivations and says what they can never expose; Theorem 7.2 quantifies over models and says they can, individually and unavoidably, decide what the derivation does not — and disagree with each other while doing so. The first is a fact about syntax, the second a fact about semantics; neither is a special case of the other. Corollary 7.3 exists to state the relationship between them precisely, rather than leave it as an analogy.

7.7

Interpreted machines: encoding and frame fixed once, at the start

We now package this section’s phenomenon as a property of computing machines directly. The simplest case is a machine that fixes both its encoding and its interpretation once, before computation begins, and never revisits either. First we need one more piece: a precise way to say exactly which facts a given encoding does, and does not, settle on its own. Definition 7.9 (Explicit encoding). An explicit encoding is a pair E = (R0 , IR0 ) where R0 is a rewriting system and IR0 := { s = t : s, t terms, R0 ⊢ s = t } is the set of equalities derivable from R0 (in the sense of Lemma 2.4: s = t ∈ IR0 iff some derivation using the rules of R0 identifies s and t). IR0 is not chosen independently of R0 : it is a deterministic consequence of it, fixed the moment R0 is fixed. 21

Proposition 7.10 (Soundness of explicit encodings). Let E = (R0 , IR0 ) be an explicit encoding and let F be a semantic frame modelling R0 (Definition 7.1). Then F |= s = t for every s = t ∈ IR0 : every frame modelling R0 agrees with everything R0 derives. Proof. The proof is by induction on the length of the derivation witnessing s = t ∈ IR0 . Each step of the derivation applies a rule of R0 ; since F models R0 , that rule holds in F (Definition 7.1), so the step preserves truth in F . The base case (the empty derivation, s = t already syntactically identical) is immediate. Hence the term identifications IR0 certifies all hold in F . Remark (The exact boundary Theorem 7.2 lives on). Proposition 7.10 says every frame modelling R0 agrees on IR0 , and says nothing about facts outside IR0 ; that silence is its exact content, not a gap. For R0 = {A1, A2}, Lemma 2.2 gives a + b = b + a ∈ / IR0 (neither it nor its negation is derivable): the Skolem pair’s order is precisely a fact the explicit encoding does not settle, which is why F1 , F2 in Theorem 7.2 are free to disagree on it without either violating Proposition 7.10. An explicit encoding thus does more than list what it exposes: it draws, provably, the exact line between what every legitimate interpretation must agree on and what is genuinely open for interpretation to decide. The four examples above — the bare arithmetic derivation of Section 4, the header-free cipher, the loader mismatch, and the transformation cascade — are independent applications of the same phenomenon (Theorem 7.2), given to show it has genuine, recognisable instances outside the toy arithmetic language. This subsection develops something additional: a formal packaging of the phenomenon as a property of computing machines directly, in the simplest case, where the machine does not use the dynamic apparatus of Section 3 at all. It fixes one explicit encoding and one interpretation once, before computation begins, and never revisits either — the familiar situation of a program compiled once against one fixed target architecture, with neither the source language nor the hardware’s semantics changing mid-run. Definition 7.11 (Interpreted machine). An interpreted machine is a triple I = (T, E, F ) where T is a standard Turing machine, E = (R0 , IR0 ) is an explicit encoding (Definition 7.9) fixed once, before computation begins, governing the syntax T operates on (in the sense of Definition 3.1 with the degenerate update υid of Corollary 3.4: R0 is chosen at the start and never updated), and F is a semantic frame (Definition 7.1) modelling R0 . Both E and F are chosen once and never changed during the run. Proposition 7.12 (Interpreted machines are externally indistinguishable across frames). Let I1 = (T, E, F1 ) and I2 = (T, E, F2 ) share the same underlying machine T and the same explicit encoding E = (R0 , IR0 ), differing only in the frame: F1 ̸= F2 , though both model R0 (take, for instance, the F1 , F2 of Theorem 7.2). Two things are true of this pair at once. First, the two machines are computationally identical as syntactic processes: every step T performs under R0 is the same for I1 and I2 , since R0 alone governs derivability. They agree with each other, and with T ’s own derivations, on every fact in IR0 . Second, they disagree wherever R0 leaves a fact undetermined. If either machine’s semantics ? is queried on a fact outside IR0 — such as a + b = b + a — I1 and I2 give opposite answers, by construction of F1 , F2 . Put these together: no output or observable computational trace of either machine, taken alone, reveals which of the two it is. The only way to tell them apart is if Ii ’s own program is explicitly written to query Fi and report the answer — and even then, this requires Fi to already be given to the machine as input or oracle; it cannot be inferred from E alone. Proof. The first claim is Corollary 3.4: the behaviour of T under fixed R0 is exactly the standard Turing-machine case, independent of F . Agreement on IR0 then follows from Proposition 7.10, applied once to F1 and once to F2 . The second claim is Theorem 7.2: F1 , F2 model the same R0 yet give opposite answers to a fact that Remark 7.7 already showed lies outside IR0 . 22

Remark (A machine is doubly silent by default). Corollary 3.4 already shows a standard Turing machine is the υ ≡ υid instance of Dynamic SIP: encoding fixed, never updated. Definition 7.11 through Proposition 7.12 add the orthogonal, independent observation that fixing the encoding this way — even an explicit one, which names precisely which facts it does and does not settle (Definition 7.9) — says nothing about fixing an interpretation for what it leaves open. A standard Turing machine is compatible with any frame F modelling its encoding, agreeing with all of them on IR0 and with none of them necessarily on anything outside it, and nothing internal to the machine signals which frame, if any, is intended. A machine is therefore doubly silent by default: about how its rules may evolve (resolved, when they do not, by Corollary 3.4) and about how whatever its rules leave open is to be read (the subject of this section). Making the encoding explicit narrows the second silence without removing it: it tells you exactly where the silence lies, not how to break it.

8

A first, independently arising instance: two selectors over countable spaces

Motivating Analogy Before presenting the main results, it is useful to introduce a short conceptual analogy that highlights the type of semantic and structural limitations that motivate this work. Once upon a time there was a machine of incredible power, capable of answering any question not by performing calculations, but by extracting the answer directly from the very structure of reality itself. but we will understand this later. Unfortunately, there is a problem: no one truly knows how to ask the question. Even if such a question existed, there would be infinitely many ways to formulate it, infinitely many ways to “select” the encoding through which the question is posed, and infinitely many (perhaps even more) ways to interpret it. Infinite universes of meaning in which each specific encoding of the question might admit one answer, two answers, infinitely many answers, or none at all. In some worlds the question would not make sense; in others it would be the primordial question at the origin of the universe, yet asked to a hamster. In another world it might be addressed to the only entity capable of answering it, but that entity would be unable to understand it. Or perhaps the problem lies in the answer itself, which might be impossible for us to interpret. As with Deep Thought in Douglas Adams’ The Hitchhiker’s Guide to the Galaxy, the answer might well be 42, but we would have no idea how to make sense of it. And there is more. Even if we had one selector for the encoding and another for the semantic reality in which the question is to be evaluated, we could not even attempt to test all possibilities. If we combine the values of both selectors into a list of pairs, Cantor would immediately remind us that there will always be a new pair which, by diagonalization, was not in the original list. But even that is not enough, because things get worse. Every combination carries a different degree of semantic blindness that compromises the result. And even if we happened to guess the one reality that is completely transparent for a given encoding, we would obtain an answer which, once produced as output by our hypothetical machine, would acquire its own points of blindness. We cannot guarantee that it preserves its semantic value, in fact, statistically, it is impossible. In a sense, it is a reflection of Rice’s theorem, like a famous separation problem. And the legend has it that this same phenomenon is the nonexistence at the base of every logical paradox, but this is another story. 23

This analogy does not affect the rest of the text or the results and should not be considered part of the formal scientific contribution. It is simply intended to provide a useful mental image that facilitates reading. Remark (This section formalizes the fable, and owes it a real debt). The story came first. It is not a theory arrived at independently and then illustrated by the story above; the order is the reverse. The story already contained, in informal and narrative form, essentially every structural idea this section makes precise: the two selectors, the diagonalization over their combinations, the varying degrees of blindness, and the explicit invocation of Rice’s theorem. The debt runs further still. Two of the story’s lines — an answer received correctly and still “no idea how to make sense of”, and every combination carrying “a different degree of semantic blindness” — reach past this section entirely. The first is a phenomenon the fable states in its own right — a correct answer that no reader can tell from noise — of which Chaitin’s Ω (Section 12) is later shown to be one sharp instance; the phenomenon was in the fable before Ω had been introduced into this paper at all, and does not depend on it. The second is the fact, proved in Remark 8.5 once Categories 1–3 were in hand, that those degrees are countably infinite in each direction, not a manner of speaking. Neither was visible as a precise claim when the fable was written; both were already sitting, correctly, in it. The “machine of incredible power” that answers by reading reality rather than by computing is owed to Douglas Adams’ The Hitchhiker’s Guide to the Galaxy and its Deep Thought: that is where the author first encountered the shape of the problem this section formalizes, and it is the genuine origin of the intuition, not a decorative reference. Narrative and metaphor arriving before formal proof is not unusual in the history of mathematics and science; the correspondence between this story and what is proved below, checked line by line at the end of the section (Remark 8.8 and the table preceding it), is close enough to be worth setting out explicitly, once there is something to compare it against.

From here on, the formal content begins The fable asked what happens when a question can be posed in infinitely many ways, and read back in infinitely many more. We now build the machine the fable was describing — starting with its two knobs: one choosing the encoding the question is posed in, one choosing the frame it is read back through. This section shows one thing: both knobs, despite offering infinitely many settings, offer only countably infinitely many. This is worth proving carefully, because the next section shows a closely related space is not countable at all, and the two must not be confused. The impossibility results and the connection back to the rest of the paper come later, once the machine is on the table. Remark (A name, and where it comes from). We call the machine below an orbital machine. The name carries no mathematical content: it is inherited from an earlier, unrelated piece of code in which the settings of a pair of selectors were labelled “orbits”, and which first suggested the construction here as an intuition pump. Nothing proved or assumed in this section is inherited from anywhere else, and the name implies no continuity with any other construction that may have used it; it is kept only because it carries the original intuition for the author.

8.1

Two countable spaces

Picture the machine’s two knobs concretely. The first chooses an encoding: which finite set of rewriting rules the question gets posed in. The second chooses a frame: which structure the answer gets read back through. Both, in principle, offer infinitely many settings — but “infinitely many” hides a distinction the rest of the paper depends on, and this subsection nails it down before anything is built on top of it. Definition 8.1 (Encoding space). Fix a countable alphabet Σ0 = {0, s, +, a, b, c1 , c2 , c3 , . . . } (the base symbols together with countably many auxiliary constants available to be used as 24

fresh Skolem symbols). The encoding space Esp is the set of all finite rewriting systems R0 over (a finite subset of) Σ0 . Proposition 8.2 (Esp is countably infinite). Esp is countably infinite. Proof. Terms over the countable alphabet Σ0 are finite strings (or finite trees) over a countable set of symbols, hence countably many (a standard Gödel numbering: enumerate Σ0 = {σ0 , σ1 , . . . } and code each finite term as a natural number via its syntax tree). A finite rewriting system R0 is a finite set of pairs of terms; finite subsets of aPcountable set are themselves countably many (a finite subset of N is coded by, e.g., the sum i∈R0 2i under any fixed enumeration of pairs-of-terms by N), so Esp is countable. Infinitude: for each n ≥ 0, letting (n) R0 = {A1, A2} ∪ {ci → ci : 1 ≤ i ≤ n} gives infinitely many distinct finite rewriting systems, hence infinitely many distinct encodings. Definition 8.3 (Computable frame). A computable frame is a structure with domain DF = N, interpreting 0, s, + as 0F = 0 and total computable functions sF : N → N, +F : N × N → N, together with designated elements aF , bF ∈ N. It models a rewriting system R0 if every rule of R0 holds under this interpretation. The frame space Fsp is the set of all computable frames modelling {A1, A2}. Proposition 8.4 (Fsp is countably infinite). Fsp is countably infinite. Proof. Fix a standard enumeration (φe )e∈N of all partial computable functions N → N (respectively N × N → N, coding pairs via a fixed computable pairing), via Turing machine indices. A computable frame is determined by a tuple (es , e+ , aF , bF ) ∈ N4 (the index for sF , the index for +F , and the two designated elements), subject to φes , φe+ being total and to F modelling {A1, A2}: Fsp is in bijection with a subset of N4 , and N4 is countable (a finite product of countable sets), so any subset of it is countable. Infinitude: for every a, b ∈ N with a ̸= b, taking sF , +F to be the standard successor and addition functions (a single fixed pair of indices e∗s , e∗+ , which model {A1, A2} since ordinary addition satisfies A1, A2) gives a distinct computable frame; there are infinitely many such pairs (a, b). Remark (Relation to Theorem 7.2’s F1 , F2 ). Both F1 and F2 of Theorem 7.2 are, after recoding, computable frames in the sense of Definition 8.3: F1 (the standard model with aF1 = 3, bF1 = 5) is already one, taking e∗s , e∗+ to code the standard successor and addition functions. F2 ’s domain N ∪ {a∗ , b∗ } is countably infinite, hence in bijection with N; composing that bijection with F2 ’s operations (mapping a∗ , b∗ to two fixed naturals not otherwise used, e.g. via any computable enumeration of N ∪ {a∗ , b∗ }) yields a computable frame isomorphic to F2 . Both F1 , F2 ∈ Fsp once so recoded; this confirms that Fsp is rich enough to contain the frames already shown to disagree, and is used nowhere below.

8.2

Two selectors, and countably many pairs

Definition 8.5 (Encoding and frame selectors). An encoding selector is a function σE taking values in Esp ; a frame selector is a function σF taking values in Fsp . The orbital machine (Remark 8) with selectors (σE , σF ) is a standard Turing machine T together with a value (E, F ) = (σE , σF ): T ’s syntax is governed by the rewriting system E, and (where a specific fact about T ’s computation is to be read off) that fact is evaluated under the frame F . What, if anything, σE , σF are permitted to depend on is not specified in this section and is left open for later work. Countability matters twice here, in opposite directions. The theorem below shows the space of possible settings (E, F ) is countable — an honest, complete list of them exists. Section 8.3 then shows the space of selectors choosing among those settings is not countable at all. Pinning down the first fact precisely now is what makes the second a genuine surprise rather than a confusion about which space is in play. 25

Theorem 8.6 (Countably many pairs). Esp × Fsp is countably infinite: there are countably infinitely many possible pairs (E, F ) ∈ Esp × Fsp , i.e. countably infinitely many possible settings of the pair of selectors (σE , σF ) at a single evaluation point. Proof. By Propositions 8.2 and 8.4, Esp and Fsp are each countably infinite, hence each in bijection with N: fix bijections α : N → Esp , β : N → Fsp . The Cantor pairing function π : N × N → N, π(i, j) = 12 (i + j)(i + j + 1) + j, is a bijection, obtained by enumerating N × N along successive finite diagonals {(i, j) : i + j = k}, k = 0, 1, 2, . . . (each diagonal finite, so every pair is reached at a finite stage). Composing, (i, j) 7→ (α(i), β(j)) is a bijection N×N → Esp ×Fsp , and π −1 composed with it gives a bijection N → Esp × Fsp directly. Hence Esp × Fsp is countably infinite (infinite since each factor is infinite and nonempty; countable as a countable union, indexed by i ∈ N, of the countable sets {i} × Fsp ). Remark (On the word “diagonalization” here). The enumeration used above — listing pairs along successive finite diagonals i + j = 0, 1, 2, . . . of the grid N × N — is the classical technique showing a countable union of countable sets is countable, sometimes itself called a “diagonal enumeration”. It is a different technique, doing the opposite job, from Cantor’s better-known diagonal argument for uncountability (used, e.g., to show 2N or R is strictly larger than N). Keeping the two apart matters here: Theorem 8.6 uses only the countability-preserving enumeration, and the uncountability argument enters only in the next subsection, on a different space. Remark (What has, and has not, been shown). This section shows exactly one thing: the space of possible (encoding, frame) pairs available to a two-selector orbital machine is countably infinite, via an explicit, checked bijection. It does not yet address how σE , σF might depend on a computation’s history, whether any analogue of Definition 3.2’s two conditions applies to a pair of selectors jointly, or whether any result of the preceding sections transfers to this two-selector setting. Those are taken up later, each checked step by step rather than assumed to carry over.

8.3

The genuine diagonalization: selector-functions, not selector-values

Theorem 8.6 shows the space of possible values (E, F ) is countable: a complete, honest enumeration of it misses nothing. The motivating analogy’s appeal to Cantor (“there will always be a new pair... not in the original list”) refers to something different — not the space of values, but the space of selectors: functions from a computation’s history to a choice of (E, F ), exactly what a policy is in control theory or a strategy is in game theory, a rule for choosing based on everything seen so far. Most of these are not computable at all, and that is where the diagonal argument for uncountability applies. Definition 8.7 (Selector, computable selector). Let Hist be the set of finite sequences of local derivation steps (a countably infinite set, by the same finite-object-over-a-countable-alphabet argument as Proposition 8.2). A selector is any function σ : Hist → Esp × Fsp , with no further restriction. A selector is computable if it is computed by some Turing machine (total on Hist, under a fixed effective coding of Hist and of Esp × Fsp by naturals, available since both are countable by Theorem 8.6). Proposition 8.8 (Selectors are uncountable; computable selectors are not). The set of all selectors has cardinality 2ℵ0 . The set of computable selectors is countably infinite. In particular, almost all selectors, in the cardinality sense, are non-computable. ∼ N (both available: Hist is countably infinite by Proof. Fix bijections Hist ∼ = N and Esp × Fsp = construction, and the second by Theorem 8.6). Selectors then correspond exactly to functions N → N, i.e. to elements of NN . This set has cardinality 2ℵ0 : it injects into 2N trivially (functions into {0, 1} ⊂ N already give 2ℵ0 elements), and 2ℵ0 is an upper bound since |NN | ≤ |(2N )N | = 26

2ℵ0 ·ℵ0 = 2ℵ0 ; by Cantor–Schröder–Bernstein [1], |NN | = 2ℵ0 . (This is exactly Cantor’s original diagonal argument: given any purportedly complete countable list g0 , g1 , g2 , . . . of functions N → N, the function h(n) := gn (n) + 1 differs from every gn at input n, so no countable list exhausts NN .) Computable selectors, by contrast, are each specified by a finite Turing machine program; there are only countably many finite programs over a fixed finite alphabet, so the set of computable selectors is countable, and infinite (e.g. the constant selectors σ ≡ (E, F ), one for each of the countably many (E, F ) ∈ Esp × Fsp , are each computable and pairwise distinct). Remark (The uncountability does not come from the richness of the choices, but from the shape of the selector). It is worth being exact about where the 2ℵ0 comes from, because the natural guess is wrong. One might think the selector space is uncountable because there are infinitely many pairs (E, F ) to choose among — that the size of the codomain is what drives it. It is not. The proof above already used only a two-element slice of the codomain: functions Hist → {0, 1} alone are 2ℵ0 of them. So even if the two selectors ranged over a finite menu of settings — even just two, one bit of choice per history — the space of selectors would still be uncountable, and a complete list of them would still be defeated by the same diagonal argument (h(n) := 1 − gn (n) suffices when the codomain is {0, 1}). What makes the selector space uncountable is the infinite domain — Hist, the unbounded history a selector reads — not the number of values it may return. This is the sharp form of the point: the two-selector machine’s unlistability survives shrinking the pool of encodings and frames all the way down to a finite one, because it was never the pool that was too large; it was the space of policies over an unbounded past. It is exactly here, and not in Theorem 8.6’s countable space of values, that Cantor’s uncountability argument does its work (Remark 8.2). Definition 8.9 (Oracle selector). An oracle selector is any selector (Definition 8.7) that is not computable. Corollary 8.10 (Oracle selectors exist, by cardinality alone). Oracle selectors exist: since the computable selectors are countable (Proposition 8.8) and all selectors are uncountable, at least one — in fact, all but countably many — of the selectors is not computable. Remark (The existence claim rests on cardinality alone). This existence claim uses nothing beyond a cardinality comparison: a countable set cannot cover an uncountable one, so oracle selectors are left over automatically, without any of them being singled out or constructed to defeat anything specific. No assertion is made about what any particular oracle selector does; none is needed. This is the same style of argument used for the static case in Section 3: an oracle-computable object escapes any fixed countable enumeration of computable ones purely because it is not among them. What cardinality alone gives is existence, not a specific task at which every computable selector provably fails and some specific oracle selector provably succeeds; constructing such a task is a separate question, and one to approach with the caution urged throughout this paper — an earlier, unrelated attempt at a construction of this shape could not be completed without manufacturing a false semantic assertion.

8.4

The problem reopens on the output: a Rice-style obstruction

Even granting a selector, computable or not, that picks a good (E, F ) for a computation’s input, whether the resulting output remains semantically well-behaved under that same frame is a separate question. Checking it, in general, is impossible for a computable process — not by any construction specific to this paper, but as a direct instance of one of the oldest results in computability theory. Theorem 8.11 (Rice’s theorem [22]). Let P be any property of partial computable functions N → N that is non-trivial (some partial computable function has it, some does not) and extensional 27

(depends only on the function computed, not on which program computes it). Then {M : the function M computes has property P} is undecidable. Definition 8.12 ((F, φ)-transparency). Fix a computable frame F ∈ Fsp and a target fact φ (an equality s = t or inequality s ̸= t between terms). A machine M is (F, φ)-transparent if, for every input x on which M halts, the output M (x), read as a term and evaluated under F , satisfies φ. Proposition 8.13 (Transparency is undecidable, when non-trivial). Let F, φ be such that some machine is (F, φ)-transparent and some machine is not (e.g. F = F2 of Theorem 7.2, recoded as a computable frame per Remark 8.1, and φ : “output = a”: the machine that always outputs the term a is (F2 , φ)-transparent, the machine that always outputs the term b is not, since aF2 ̸= bF2 ). Then {M : M is (F, φ)-transparent} is undecidable. Proof. (F, φ)-transparency depends only on the partial function M computes (two machines computing the same function produce identical outputs on identical inputs, hence agree on whether every output satisfies φ under F ): it is extensional in the sense required by Theorem 8.11. It is non-trivial by the hypothesis (and the worked example given). Theorem 8.11 applies directly. Remark (The recursive reopening). Even after a selector has fixed a frame F that correctly interprets a computation’s input, no algorithm can decide, in general, whether a given machine’s output continues to respect any fixed, non-trivial semantic fact under that same F : by Proposition 8.13, the transparency problem is exactly as hard, in the sense of ordinary undecidability, as any other non-trivial semantic property of programs. Interpretability of the question does not propagate to interpretability of the answer, and provably cannot in general. Remark (What hides the output, and what is merely undecidable about it, are different things). The undecidability just stated should not be mistaken for the reason the output is opaque. What hides the output is structural, and there are two such structural reasons, both already in play in this paper. First, the static principle acting on the output: M (x) is itself a syntactic object, so whatever semantic invariant is protected in it — partially or totally — is invisible to any purely syntactic inspection of it, for the structural reason of Lemma 2.4, that syntax cannot see semantic invariants. Second, the encoding–frame relativity this very section is built on: whether the output reads as meaningful is relative to a pair (E, F ), and under a pair other than the intended one it may fail to parse, answer a different question, or answer nothing discriminating (Categories 1–3, Propositions 8.15–8.17) — so an output can be opaque because no available reading renders it, quite apart from any syntactic hiding. Either inaccessibility is the blindness, and each is present whether or not anything about the output is decidable. Rice’s theorem concerns a different question again: not what hides the invariant, but whether one can algorithmically decide that a fixed invariant holds — which, by Proposition 8.13, one cannot in general. The three must be kept apart: the SIP and the encoding–frame relativity are why there is, or is not, a readable invariant at all; Rice is why verifying a fixed one is beyond an algorithm. The fable’s “reflection of Rice’s theorem” is a narrative allusion, gesturing at material outside this paper’s scope, not a claim that Rice is the source of the blindness. This same separation is set out for the output row of the fable’s table (Section 8.8); it is recorded here because this is where the output’s reopening is first proved.

8.5

One correct pair, and three ways to fail: the fable made precise

The motivating analogy describes a question with an intended meaning, posed under some encoding, read under some frame, where only one pair of choices recovers what was meant; every other pair either fails to parse, answers something else, or answers nothing discriminating at all. This subsection makes each precise, for a specific, fully worked question, in the same spirit as Section 4’s worked examples: concrete enough to prove completely. 28

Remark (Scope: one concrete question). This is worked for the specific question of Theorem 7.2, fully rigorously. Doing the same for an arbitrary externally chosen target question would require a general model-existence fact — if an encoding E derives neither a question nor its negation, models of E disagreeing on it exist — which holds in general (it follows from Gödel’s completeness theorem) but is built here only for the specific case at hand, by direct construction. Extending to arbitrary (E ∗ , q ∗ ) is open, and would need that general model-existence argument built with the same care given to every other construction here. To make the fable’s three ways of failing precise, we need a fixed target to fail against: a specific question, posed under a specific encoding, with a specific frame that gives the answer meant. This target is fixed once, from outside the construction — exactly as the true key K ∗ was fixed externally in Proposition 7.4. Definition 8.14 (External target). Fix, once and externally, three things: a target encoding ?

E ∗ = {A1, A2} ∈ Esp ; a target question q ∗ , taken to be “a + b = b + a”; and a target frame F ∗ ∈ Fsp modelling {A1, A2} that gives the intended answer (say F ∗ = F1 of Theorem 7.2, recoded as computable, so the intended answer is “true”). A candidate pair (E, F ) recovers q ∗ if E = E ∗ and F |= a + b = b + a. Proposition 8.15 (Category 1: syntactic vacuity). There are countably infinitely many E ∈ Esp under which q ∗ is not even a well-formed term: E’s rewriting system does not have a and b both among its symbols. Proof. For each n ≥ 1, let En = {cn → cn } (using one of the countably many auxiliary symbols of Definition 8.1, none of them a or b): a + b is not a term over En ’s alphabet at all, so q ∗ cannot be posed under En . The En are pairwise distinct (distinct symbols cn ), giving countably infinitely many such E. Proposition 8.16 (Category 2: semantic disagreement). There are countably infinitely many F ∈ Fsp modelling E ∗ = {A1, A2} that disagree with F ∗ on q ∗ , i.e. with F |= a + b ̸= b + a. Proof. Theorem 7.2 exhibits one such frame, F2 (recoded as computable per Remark 8.1). For infinitely many pairwise-distinct variants, note that Remark 8.1’s recoding already moves F2 ’s domain from N ∪ {a∗ , b∗ } to N itself, by relabelling a∗ , b∗ as two natural numbers not otherwise used. The same freedom gives further variants directly, each built on the same “leftmost sink wins” idea as F2 itself (Theorem 7.2’s proof): for each n ≥ 1, pick a fresh pair pn ̸= qn ∈ N, (n) (n) disjoint from all previously chosen pairs, and define sF , +F to agree with the standard (n) (n) successor and addition on N \ {pn , qn }, but with sF (pn ) = pn , sF (qn ) = qn (fixed points), (n) (n) (n) (n) and +F (pn , y) := pn , +F (qn , y) := qn for all y, +F (x, pn ) := pn , +F (x, qn ) := qn for x∈ / {pn , qn } (the same five-case definition as Theorem 7.2’s F2 , now with pn , qn literal elements of N rather than adjoined outside it). The same case-by-case check as that theorem’s proof (A1, A2 verified exhaustively over the five shapes of argument pairs) applies verbatim with pn , qn in (n) (n) place of a∗ , b∗ , giving F (n) ∈ Fsp modelling {A1, A2}, with aF := pn , bF := qn satisfying (n) (n) F F (n) a+ b = pn ̸= qn = b + a. The F are pairwise distinct (distinct pairs (pn , qn )), giving countably infinitely many such F . Proposition 8.17 (Category 3: semantic vacuity — the “beaver” frames). There is a frame F (1) ∈ Fsp modelling {A1, A2} under which q ∗ receives a well-defined answer that carries no discriminating information whatsoever: F (1) answers “a + b = b + a” regardless of what a, b are, or what q ∗ was really asking. Countably many formally distinct (though isomorphic) recodings of it exist in Fsp . Proof. Let F (1) have domain D = {0}, with 0F = 0, sF (0) = 0, and +F (0, 0) = 0. Checking A1: 0 +F 0 = 0 matches 0F = 0, as required. Checking A2: sF (0) +F 0 = 0 +F 0 = 0, and separately sF (0 +F 0) = sF (0) = 0; the two sides agree. So F (1) models {A1, A2}. 29

(1)

(1)

Now, since D has only one element, aF = bF = 0 is forced — there is nowhere else for (1) (1) either to point. Hence a +F b = 0 = b +F a holds trivially, whatever a, b were originally intended to name. This is not a correct answer so much as an inability to ask the question at all: the frame cannot express, let alone correctly or incorrectly answer, anything depending on two things being distinguishable, because it has nowhere to put a second thing. Finally, recoding this same one-element frame under any of the countably many naturals as the name of its single point produces countably many formally distinct elements of Fsp , all isomorphic to F (1) . Remark (The same idea as O⊥ -blindness, in a new setting). F (1) is the same underlying idea as Proposition 4.2, transplanted from language recognition to equality queries: a structure with only one point cannot distinguish any two things put into it, exactly as an observer collapsing everything to ⋆ cannot distinguish any two inputs. The two are not literally the same instance — one concerns a machine receiving O⊥ (x) = ⋆, the other a degenerate frame answering equality queries — but the shape is identical. This is the fable’s hamster, or beaver: not wrong, not silent, but structurally incapable of holding the distinction the question depends on. Remark (Uniqueness of the correct pair, up to extensional identification). (E ∗ , F ∗ ) recovers q ∗ by construction (Definition 8.14). Every E of Proposition 8.15 fails outright (Category 1); every F of Proposition 8.16 gives the wrong answer to a well-posed question (Category 2); F (1) of Proposition 8.17 gives an answer that agrees numerically but for the wrong reason, carrying no information about a, b specifically — arguably a fourth, degenerate way of not recovering q ∗ , the agreement being accidental to total collapse rather than a correct resolution of the Skolem pair. Categories 1–3 are salient, each-infinite ways of failing to recover q ∗ , exhibited to show how varied and how numerous the failures are; they are not claimed to be an exhaustive or mutually exclusive partition of every failing pair (the “fourth way” just noted already shows the boundaries are not sharp), and nothing below depends on their being one. What is used is only the other direction: that (E ∗ , F ∗ ) recovers q ∗ and, up to the extensional identification below, does so uniquely. As already noted for encodings (Remark 8.3) and selectors (Section 8.3), the correct pair is unique only up to extensional identification: any frame computing exactly the same function as F ∗ , however differently coded, recovers q ∗ equally well and counts as the same pair, not a second one. Remark (What the orbital machine shows that no binary verdict can). What has just been proved has a shape worth stating in its own right. Categories 1–3 are not merely non-empty; each contains countably infinitely many genuinely distinct members: countably many encodings under which the question cannot even be posed (Proposition 8.15), countably many frames that pose it correctly and answer it wrongly, each in its own distinct way rather than one shared error repeated (Proposition 8.16), and countably many degenerate framings that answer without saying anything at all (Proposition 8.17) — set against exactly one pair that gets it right. A plain accessible/blocked verdict, of the kind the static and Dynamic SIP each return, cannot show this: it reports whether a fact can be seen or not, one bit, where the orbital machine resolves the whole space of ways of almost seeing it, or failing to, into a structured landscape of distinguishable failures, most of them countably infinite in their own right. The same finergrained question recurs later in a different vocabulary: an algorithm’s output is there called C-usable or C-opaque (Definition 12.3), a single cut for a fixed class C, appropriately coarse for the statistical question that section asks. Binary usability tells you which side of one line an object falls on; the orbital machine maps the terrain the line was drawn across.

8.6

The orbital machine as an active instance of “all assumptions made explicit”

Section 7.7 defined an interpreted machine as a standard Turing machine equipped with a fixed encoding and a fixed frame, the frame used only passively, to read a specific target fact off the 30

machine’s output once computation halts. The orbital machine, defined independently above, instantiates that same idea of “an encoding and a frame, made explicit” — but with the frame used actively, consulted during the computation itself, not only at the end. Definition 8.18 (Semantic oracle). For F ∈ Fsp , the semantic oracle OF is the function taking a pair of terms (s, t) to OF (s, t) = 1 if F |= s = t, and OF (s, t) = 0 otherwise. (Since F is a computable frame, OF is itself a computable function; it is called an “oracle” because of the role it plays — direct, one-step consultation of a specific world’s answer — not because it exceeds what a Turing machine can compute. This matches the fable’s Einstein example: being asked a question in ancient Egyptian rather than German is not a matter of the answerer’s raw intelligence, but of which channel the question arrives through.) The architecture about to be defined — a computable function consulted mid-computation, with later queries free to depend on earlier answers — is an already-studied notion. [4, Remark 7.2] formalizes exactly this, independently, as an adaptive observer, of which a computational oracle queried sequentially is one instance. What follows is, in that source’s vocabulary, an adaptive observer of unbounded depth, built on a computable oracle rather than an arbitrary one; this uses only that basic point, not that source’s further Landauer-cost or quantum development of the idea. In plain terms, before the formal definition: an oracle orbital machine works like an ordinary Turing machine, except that at any point it may pause and ask the semantic oracle a yes/no question about two terms it has built so far, then continue using the answer. Definition 8.19 (Oracle orbital machine). Given selectors fixed to values (σE , σF ) = (E, F ), the oracle orbital machine T OF ,E is a Turing machine T with three properties. First, it reads its input as a term over E’s alphabet, halting and rejecting immediately if the input is not wellformed under E (Category 1, Proposition 8.15). Second, at any point during its computation it may query OF on any pair of terms it has constructed so far, receiving a definite answer in one step. Third, apart from these queries, it proceeds as an ordinary Turing machine operating under E’s rewriting rules. Proposition 8.20 (The passive Interpreted Machine is the never-query case). An oracle orbital machine T OF ,E that never queries OF during its computation, consulting F only once, passively, after halting, to evaluate a single target fact about its output, is exactly the interpreted machine I = (T, E, F ) of Definition 7.11. Proof. This follows immediately from the two definitions. With no queries during computation, T OF ,E ’s run is identical, step for step, to T operating under E alone (Definition 3.1 with the degenerate update υid , as already used in Corollary 3.4). The only remaining role for F is the single post-halting evaluation, which is exactly Definition 7.11’s passive reading. Remark (What active querying adds, precisely). The passive case is recovered exactly, not approximated (Proposition 8.20): nothing built in Section 7.7 is lost, and the oracle orbital machine is a strict extension of it. What active querying adds is availability during computation of facts E alone cannot derive. By Lemma 2.2 applied to E = {A1, A2}, T operating on E’s rules alone can never determine whether a + b = b + a, no matter how long it runs; T OF ,{A1,A2} can ask OF and receive a definite answer in a single step, mid-computation, usable in its subsequent behaviour (e.g. branching on the answer). This is the precise sense in which the oracle matters here: not because OF computes anything T could not eventually compute by other means, but because E’s own rules never license deriving that specific fact at all. Remark (Every machine here is, in raw power, exactly a Turing machine). Three results in three separate places combine into one worth stating plainly, in a single place: every machine built in this paper is, in raw computational power, an ordinary Turing machine, no more and 31

no less. The interpreted machine of Section 7.7 is one by definition, with F read only passively at the end (Definition 7.11), and the syntactic process it runs is exactly the standard, singlefixed-system case (Corollary 3.4). The orbital machine, before any oracle is added, is the same object with (E, F ) chosen by selectors rather than by hand (Definition 8.5); once a value is chosen, it is again exactly that case. Even the oracle orbital machine, which can query OF mid-computation rather than only at the end, adds nothing beyond Turing power: F being a computable frame (Definition 8.3) makes OF a computable function, so a mid-run query could always be replaced by an ordinary Turing machine computing that same answer inline, with no oracle (Remark 8.6 makes this precise). This extends to a richer setting exactly what [5, Remark 9.1] establishes for a plain structural observer: such an observer answers no queries and never extends the underlying computational model, since, in that source’s words, “the observer only reduces available information and never increases computational power”. What each layer here adds is not computational power but honesty: making explicit a choice — which encoding, which interpretation, when to consult it — that an ordinary, unlabelled Turing machine always makes too, silently, through whoever builds it. Remark (E and F do distinct jobs: what is askable, and what the answer is). Turingequivalence is one half of the architecture; the other half is that E and F play genuinely different roles, neither substituting for the other. E decides which semantic invariants are even askable: if E’s alphabet lacks a or b, the question “does a + b = b + a” is not merely unanswered but not well-formed at all (Category 1, Proposition 8.15). F then decides, for whichever question E has made askable, what the answer is when OF is consulted (Definition 8.18). Change E alone and the menu of questions changes; change F alone, holding E fixed, and the answers to that same menu can change (Category 2, Proposition 8.16). What the oracle orbital machine can learn mid-computation takes the pair, doing two distinct jobs, together. Remark (What remains unconnected, and why). This subsection connects the orbital machine to Section 7.7’s Interpreted Machine only. The connection to the Dynamic SIP of Sections 3– 4, to the structural-observer framework of Sections 4–6, and to Observer World ([4]) is the third and final step, made next — after the orbital machine’s standalone construction and this active-oracle instantiation, in that order.

8.7

The third connection: Dynamic SIP, the observational hierarchy, and Observer World

This connection is made in two independent pieces, one per selector, never jointly. Making both σE and σF history-dependent at once would be a genuine two-axis system — new mathematics, not an application of what is already proved — and nothing below attempts it; the two axes are connected one at a time, each a direct application of results already in hand. Remark (What is at stake throughout: a semantic invariant). [7]’s own title states the target: syntactic systems cannot see semantic invariants. The two connections below should be read with that target in view. In the encoding-axis connection, the semantic invariant at stake is the one Theorem 3.3 already concerns: the relative order of a, b, a fact about truth (whether a + b = b + a holds), not about symbols. In the frame-axis connection, the invariant differs across its three settings but is the same in kind: membership of a string in a language L (the non-recognition of [5, Cor. 2.8] is exactly non-access to whether x ∈ L, a property of what x means), and identity of a plaintext (the impossibility of recovery in [4, Prop. 4.9] is non-access to which M was sent). Both axes connect to these targets, not to a generic notion of syntactic restriction.

32

The encoding axis, alone, is Dynamic SIP Remark (Direct identification, not analogy). Suppose the encoding selector σE is permitted to depend on history, En+1 := σE (Hn ), while the frame is held fixed. Then (En )n≥0 , together with the local derivations it generates, is a dynamic rewriting system generated by the update υ := σE , in the exact sense of Definition 3.1 — literally, term for term, one. Consequently: • if σE is opacity-preserving (Definition 3.2), Theorem 3.3 applies to the encoding axis directly: the semantic invariant at stake — the relative order of whichever Skolem pair is frozen in E0 , i.e. the truth of a+b = b+a — remains inaccessible at every subsequent value En the selector produces, however long the computation runs; the syntax never settles it, and the selector’s own updates cannot make it settle it either; • if, further, σE ’s access to Hn is filtered through a swap-blind structural observer O (Definition 4.3), Corollary 4.4 upgrades this to hold for every such σE satisfying condition (i), with no case-by-case verification of condition (ii). No new theorem is proved here: this is a direct application of Sections 3–4 to the encoding selector, made precise by noting that the orbital machine’s encoding axis was, from Definition 8.5 onward, already the same object as Dynamic SIP’s Rn — simply not yet identified as such, per the deliberate independence of Section 8’s opening. The frame axis, alone: the beaver, O⊥ , and Cell (d) The frame axis is not identified with a structural observer in the same direct way: a structural observer O (Definition 4.1) only partitions strings and asserts nothing, while a frame F decides definite truth values. These remain distinct objects throughout. What connects them, per Remark 8.7, is that each blocks access to a specific semantic invariant by the same underlying shape. Remark (The same shape, three times, on three semantic invariants: beaver, O⊥ , Cell (d)). Remark 8.5 noted that Category 3’s one-element beaver frame (Proposition 8.17) shares its underlying shape with O⊥ ’s triviality (Proposition 4.2): both collapse every distinction to a single output, and both are unbreakable by computational power for the same reason — there is nowhere for a second value to be told apart from the first. The blocked invariant differs across the three settings, and naming it case by case is the point here. For the beaver frame, it is the truth of a + b = b + a. For O⊥ , it is membership x ∈ L, for whatever non-trivial L is asked. For Cell (d) (Proposition 5.1), it is which plaintext M was sent. The chain runs: beaver frame (Category 3, this section), then O⊥ (Section 4), then Cell (d) (Section 5.1), with Proposition 5.2 already making the last step precise as the degenerate, single-step case of total opacity. Three different semantic invariants, in three different formal settings (a one-element algebraic structure, a string-partitioning function, a cryptographic adversary), all blocked by the identical collapse-to-one-point argument. Remark (An order on frames: the natural next definition). Sections 4–6 order structural observers by richness (O⊥ ⪯ · · · ⪯ Oprof ⪯ · · · ). The analogous order on frames — F1 ⪯ F2 if every fact F1 decides, F2 also decides and agrees with — is the natural next definition, under which the beaver frame sits at the bottom, exactly where O⊥ sits in the observer order. What has been shown here is the bottom point of that order: the beaver (Category 3) behaves like O⊥ . Whether the order as a whole is rich enough to support results of the same strength as Sections 4–6 — a full characterization, a dynamic extension — is open. Remark (The two-axis case, deliberately left alone). Both connections above hold one selector fixed while the other varies. A joint statement — an analogue of Theorem 3.3 or Corollary 4.4 for σE , σF evolving together — is not attempted here, for a reason this paper has met before: 33

this is precisely the shape of construction that, in a separate and unrelated project, could not be completed without manufacturing a false semantic assertion. The identifications above are safe because each is a one-axis application of results already fully proved; a two-axis version would be new mathematics, not an application, and is left for future work approached with the same caution.

8.8

The fable, mapped

With the formal content built, the correspondence promised in Remark 8 can be checked line by line, rather than asserted in general terms.

34

What the fable says

What this section proves

A machine that answers by reading reality directly, not by calculating

The active-query architecture built above: Definitions 8.18, 8.19 (Section 8.6); named informally already at Definition 8.5 (Remark 8). The encoding selector σE and encoding space Esp (Definitions 8.1, 8.5).

Infinitely many ways to select the encoding through which the question is posed Infinitely many ways to interpret it In some worlds the question would not make sense; addressed to the only entity capable of answering it, yet unable to understand it The primordial question, asked to a hamster

The answer might be impossible for us to interpret — 42, with no idea how to make sense of it

Even with both selectors, we could not test every possibility: Cantor reminds us there is always a new pair not in the list, by diagonalization

Every combination carries a different degree of semantic blindness

Even the one transparent reality produces an answer that acquires its own points of blindness — a reflection of Rice’s theorem, like a famous separation problem

The frame selector σF and frame space Fsp (Definitions 8.3, 8.5). Category 1, syntactic vacuity: infinitely many encodings under which the question is not even a well-formed term (Proposition 8.15). Category 3, the “beaver” frames: a frame structurally incapable of holding the distinction the question depends on, answering something well-defined but discriminating nothing (Proposition 8.17, Remark 8.5). Two results, not one: no algorithm decides, in general, whether a machine’s output remains semantically transparent (Proposition 8.13) — and, more literally, an output can be produced correctly by the right pair and still be statistically indistinguishable from noise to every observer who receives it, however powerful, as Section 12 shows much later in this paper (Definition 12.3, Proposition 12.1, Remark 12.2): not merely undecidable whether it is readable, but actually opaque, and opaque for reasons that do not turn on the reader’s computational power — Ω being the sharpest witness, not the only route. The genuine diagonal argument, applied correctly to selector-functions rather than to selector-values (Proposition 8.8; see Remark 8.3 for why this is not the same claim as “the pairs themselves are uncountable”, which is false — Theorem 8.6 shows the opposite for values). Not a loose figure of speech: Categories 1, 2, and 3 are each shown to contain countably infinitely many, genuinely distinct members, not one representative apiece (Remark 8.5), together with the graded disagreement of Category 2 itself (Proposition 8.16) and the spectrum of observer/frame richness running through Sections 4–6 (O⊥ , (B, ·), Oprof blindness). The blindness is the static SIP: an output, once produced, is again a syntactic object, and whatever semantic invariant is protected in it — partially or totally — is invisible to any later syntactic inspection of it (Lemma 2.4, “syntax cannot see semantic invariants”). This is the “separation problem” the fable places next to the phrase, the same separation running through this paper’s source material ([7]’s title; [6]’s syn35 tactic separation). The fable’s “reflection of Rice’s theorem” is a narrative allusion, not a claim that Rice explains the blindness; Rice enters as a separate, genuine fact — whether

Remark (Where the correspondence is not exact). Two entries above are looser than the rest, and worth flagging as such. First, the Category 1 row folds together two images the fable states separately — “the question would not make sense” and “addressed to the only entity capable of answering it, yet unable to understand it” — and reads both as syntactic vacuity, an unparseable question; the fable’s “asked to a hamster” is placed one row down, with Category 3’s structurally undiscriminating answerer. The fable does not itself draw the line exactly where Categories 1 and 3 draw it (unparseable question versus well-formed question put to an answerer that cannot discriminate), so these placements are by best fit, not by a claim that the fable distinguishes precisely these formal cases. Second, the oracle-consultation architecture in the first row is named early (Remark 8) and built as an explicit mechanism earlier in this section (Section 8.6); by the point this table appears, that mechanism is already complete, not merely promised.

9

Scope

Two separate limitations apply to the two halves of this paper, and this section states them plainly. For the Dynamic SIP of Sections 3–6: this paper generalizes the single-encoding case — one dynamic rule sequence, one update mechanism, one limiting case filtered through a single structural observer. Two independently varying axes, and an unconditional oracle-based separation theorem, are outside its scope. An earlier, independent attempt at the latter, in a different project, rested on manufacturing a false assertion and was abandoned rather than repaired; every result here stays on the side of that line where the invariant is a true fact, preserved because the available operations preserve true facts. For the semantic frames of Section 7: every result there concerns a single, fixed frame, never one that evolves over the course of a derivation. A frame that updates dynamically, in the same shape as the encoding update υ, is identified but not attempted (Remark 7.6): it would combine with a dynamic encoding into the genuine two-axis system just referred to, and the right notion of opacity-preservation is itself unclear once frame updates can change what is true rather than only what has been derived.

10

A second, independently arising instance: the Andromeda paradox

This section develops, on its own terms and without depending on anything constructed above, a second phenomenon that instantiates this paper’s central theorem in a completely different domain, discovered independently rather than built to fit. It is presented exactly as Section 8 was: standalone for now, with the reconnection to the rest of the paper deferred rather than forced.

10.1

The story On a planet in the Andromeda galaxy, Chicco stands on the beach looking at the Earth, and uses his own concept of “now” to define which events on Earth are simultaneous with this instant. According to Chicco, the events happening on Earth right now are, say, those of 1026 AD. Then there is Bruno Sacchi, who is lazy and decides to go visit his friend Chicco on planet 3C with his spaceship. So he takes the shuttle and travels very fast toward Chicco. But Bruno has a different space of simultaneity. His concept of “now” is rotated, relative to Chicco’s, in spacetime. So when Bruno looks toward the Earth to see what is happening now, he sees a completely different epoch — perhaps the year 3026 AD. 36

But at the very same physical instant, Chicco sees the past and Bruno sees the future, and both are right. One might think this creates a paradox, but it does not, because the speed of light imposes a delay that sets everything right again. The story retells a real and well-established phenomenon in special relativity, the relativity of simultaneity. The underlying argument was discovered independently twice: first by C. W. Rietdijk in 1966 [23], then by Hilary Putnam in 1967 [20], each using it to argue for a substantive philosophical thesis — that the relativity of simultaneity, combined with a transitivity requirement on what counts as “real”, forces a block-universe view in which future events are already as real as past ones. Roger Penrose, crediting earlier related work by Rindler, gave the argument its now-standard, vivid concrete form in 1989 — two pedestrians passing on an Earth street, one walking toward the Andromeda galaxy, disagreeing by days about whether a distant space fleet has already launched [19]. That is the version most readers know as “the Andromeda paradox”, and the version this paper’s retelling is built to be recognised against. Remark (How this retelling differs, and why). Two things distinguish the telling above from Penrose’s. First, the geometry is reversed: Penrose places both observers on Earth, looking outward across the vast distance to Andromeda, so that an ordinary walking-speed velocity difference is amplified, by that distance alone, into a difference of centuries in what each calls “now”. The telling here instead places one observer (Chicco) far away, on the Andromeda side, looking back at Earth, with the second observer (Bruno) making the crossing at genuinely relativistic speed. Second, and following from the first, the effect here is driven directly by a large relative velocity between the two observers, rather than by an imperceptible velocity difference amplified by cosmic distance. The physical content, the relativity of simultaneity itself, is identical in both, and Remark 10.2 below applies to each without modification. The reversal is expository: separating the two effects that do the work in Penrose’s version — a tiny velocity difference and an enormous distance, multiplying together — into one observer at rest and one moving fast isolates the relativity-of-simultaneity effect on its own, with nothing left for a reader to attribute, mistakenly, to the distance. This paper’s use of the argument is also narrower in purpose than Rietdijk’s or Putnam’s: it takes no position on their philosophical conclusion about the reality of future events, determinism, or eternalism, and needs none. It uses only the uncontested physical fact — two valid, disagreeing simultaneity planes — as an instance of Theorem 7.2.

10.2

Getting the physics precisely right

Remark (What is, and is not, hidden). The story’s line “both are right” needs a careful reading, since an imprecise one would misstate the physics. It does not mean that there exists a single, true, global “now” on Earth that both observers fail to see and that some more privileged vantage point could recover: special relativity gives no such fact to fail to see. What is genuinely invariant, independent of every observer’s state of motion, is the entire four-dimensional causal structure of spacetime — the complete history of events and their causal relations. Each observer’s “now” is a three-dimensional slice through that structure, cut at a different angle depending on velocity; no slice is the whole structure, and none is privileged over any other. Chicco’s slice and Bruno’s slice are two different, equally legitimate cuts through one and the same invariant four-dimensional reality, neither of which exposes that reality whole. The speedof-light delay in the story’s last line is what keeps this from producing any causal contradiction: neither observer can act on what they see as “now” on Earth before a light signal could, in principle, have made the relevant influence causally possible.

37

10.3

The precise mapping

Remark (Level of formality). As with the MS-DOS instance (Proposition 7.5, Remark 7.5), this mapping is stated at the level of precision the physics supports: a precise structural correspondence to Theorem 7.2, without reducing the Lorentz transformations themselves to a rewriting system in the sense of Definition 3.1. The correspondence with Theorem 7.2 is direct. The laws of special relativity, shared identically by Chicco and Bruno, play the role of the encoding E ∗ = {A1, A2}: neither observer violates them, and the laws alone — like {A1, A2} alone — do not settle the target question. The target question q ∗ is “which events on Earth are simultaneous with here-now”: the direct ? analogue of “a + b = b + a”. Each observer’s state of motion fixes a specific, legitimate frame (FChicco , FBruno ), each a genuine, internally consistent structure satisfying the shared laws, exactly as F1 , F2 both model {A1, A2} in Theorem 7.2. Chicco’s answer (the events of 1026 AD) and Bruno’s answer (the events of 3026 AD) are the direct analogue of F1 |= a + b = b + a against F2 |= a + b ̸= b + a: two frames, both modelling the same shared laws, giving different, individually consistent answers to a question those laws leave open. This is specifically an instance of Category 2 (semantic disagreement, Proposition 8.16), not Category 1 or 3: neither observer fails to pose the question (it is perfectly well-formed for both), and neither observer’s frame is degenerate or uninformative (each gives a definite, non-trivial answer) — they simply, and correctly, disagree.

10.4

The hidden assumption, developed: constrained selectors

Remark (The hidden assumption, stated precisely). In this physical instance, unlike the general orbital machine of Section 8, the frame selector is not free: which frame an observer has is determined by their state of motion, not chosen independently of it. Definition 8.5 deliberately left what σE , σF may depend on unspecified; the Andromeda paradox is the case where σF is constrained to be a function of something else entirely — velocity — rather than free. The rest of this subsection develops that case. Definition 10.1 (Constrained selector). Let V be a set of physical states (for Andromeda, V = [0, c), the possible relative speeds). A constrained frame selector over V is a function φ : V → Fsp , with σF := φ understood as depending on the physical state alone, not on history or on any other input. This is the pigeonhole principle, run at infinite scale: with only countably many holes and uncountably many pigeons, some hole must catch uncountably many of them. Proposition 10.2 (Constrained selectors over a continuum collapse uncountably many states onto a single frame). Let V be uncountable (in particular, of cardinality 2ℵ0 , as for [0, c)) and let φ : V → Fsp be any constrained selector. Then there exists F ∈ Fsp with φ−1 (F ) uncountable: some single frame is the image of uncountably many distinct physical states. S Proof. Fsp is countable (Proposition 8.4), so V = F ∈Fsp φ−1 (F ) expresses V as a countable union of the fibres φ−1 (F ). If every fibre were countable, this union would be a countable union of countable sets, hence countable, contradicting |V| = 2ℵ0 . So some fibre is uncountable. Remark (What this means physically). In the real physics, the map from velocity to “which year is simultaneous with here-now” is continuous and, on any interval, essentially injective: distinct velocities give distinct simultaneity answers, with no natural collapsing. Proposition 10.2 is therefore not a fact about the physics; it is a fact about this paper’s own formal apparatus. Fsp (Definition 8.3) was built countable on purpose, tied to Turing-machine codes, because Section 8’s selectors were meant to range over effectively describable objects. Andromeda’s 38

velocity parameter has no such restriction — it is a genuine continuum — and Proposition 10.2 shows that forcing it through Fsp necessarily discards information: uncountably many physically distinct states are identified, by the pigeonhole argument alone, regardless of how φ is chosen. A fully faithful model of the constrained selector would need a frame space rich enough to distinguish continuum-many states — an extension of Definition 8.3 to uncountably many, not necessarily computable, frames — which is outside this paper’s scope. Remark (A blindness one level up). Every other instance of semantic-invariant inaccessibility in this paper (Remark 8.7) concerns an observer, selector, or adversary inside the framework being blind to a fact the framework can nonetheless state. This one is different in kind: it is the framework itself — Fsp ’s countability — that is blind to distinctions a physically continuous parameter genuinely carries. This is one further instance of the pattern traced since Remark 8, a silent assumption revealed (here: “every frame worth considering is countable, hence effectively describable”), but with the assumption located in the paper’s own modelling choices rather than in any object the paper studies. Whether lifting it — allowing Fsp to be uncountable — preserves, breaks, or changes the shape of Theorem 7.2 and everything built on it in Section 8 is a substantial further question, not a small addendum, and is left open. Remark (Independence, and the promise of reconnection). The Andromeda paradox’s core mathematical content — its instantiation of Theorem 7.2 as a Category 2 disagreement (Section 10.3) — needs only that theorem and depends on nothing else in this paper. Section 10.4’s development of the hidden assumption stands differently: its central proposition (Proposition 10.2) uses Fsp ’s countability (Proposition 8.4) directly, a genuine dependency on Section 8, not a light comparison. The paradox’s main claim is independent; its further development is not. How this section reconnects more fully to the rest of the paper’s thread — beyond the dependency just named — is deferred, in the same spirit as Remark 8.6 deferred the orbital machine’s own reconnection.

11

A third, independently arising question: can a formal theory of everything exist? The answer, stated plainly before anything else, proved below. No theory of everything that could ever actually be written down — by a person, by a computer, by any process producing symbols one at a time, however long it runs — can capture every true law of physics. This is not a limitation of present-day science that better instruments or cleverer physicists might overcome. It is a mathematical certainty, of exactly the same kind as Cantor’s 1891 diagonal proof [8] that there are more real numbers than natural numbers: the space of possible physical laws is simply too large, in a precise, countable sense, for any theory that could be written on paper or run on a machine to equal it. And this is not bad news for physics. It means physics can never be finished: for any theory physicists ever reach, there is provably — not just possibly — a further true law still waiting to be found. The rest of this section proves this claim rigorously, names precisely what kind of barrier it is, and explains, in Section 11.7, why this is the right way to read it.

This section, like Sections 8 and 10 before it, is developed on its own terms, without depending on anything constructed above, and its reconnection to this paper’s main thread is deferred rather than forced. A speculative idea, checked as rigorously as it can be checked at this stage, is worth setting down explicitly — including exactly where it is rigorous and exactly where it is not. Marking that line precisely is treated here as an obligation.

39

11.1

What follows, and what it does not claim

Remark (Reading key, stated before the argument). The argument below is developed in the vocabulary of a computer scientist — cardinality, diagonalization, formal undecidability — applied to theoretical physics, and is offered as a seed for physicists to examine, correct, or develop, rather than as a finished result in physics. Two commitments follow, and this section keeps them: every step that can be made a rigorous mathematical statement is made one, with a complete proof, exactly as elsewhere in this paper; and every step that cannot yet be made rigorous — because it rests on an assumption about physical reality this paper does not establish, or on an analogy rather than a theorem — is marked as such at the point it occurs, not folded silently into the rigorous parts. Section 11.7 returns to this at the end, once the mathematics is on the table, to say why a result of this shape is an opening rather than a closure.

11.2

The Buckingham π theorem, recalled correctly

The argument starts from a classical, universally accepted theorem about physics: any physical law involving several quantities can always be rewritten using a smaller number of dimensionless combinations of them. We recall it precisely, because getting exactly what it does and does not say right matters for everything that follows. Theorem 11.1 (Buckingham π theorem, classical [2]). Let q1 , . . . , qn ∈ R>0 be physical variables, each with a dimension expressed as a product of powers of k independent fundamental quantities ([M ], [L], [T ], . . . ), and let F (q1 , . . . , qn ) = 0 be a relation among them that is invariant under changes of the units used to measure the fundamental quantities. Then there exist r = n − k dimensionless products π1 (q), . . . , πr (q) and a function Φ : Rr → R such that F (q) = 0 ⇐⇒ Φ(Π(q)) = 0,

Π(q) := (π1 (q), . . . , πr (q)).

Remark (This theorem is a completeness result, not an incompleteness one). Theorem 11.1 is a statement about a fixed, given list of n variables: once that list is settled, dimensional analysis captures every dimensionally-consistent relation among exactly those variables, completely, via the r = n − k groups. It says nothing about whether the list q1 , . . . , qn is itself the right or complete list of variables for the phenomenon at hand; that is an empirical question the theorem does not address. This matters below: nothing in Theorem 11.1 asserts that “something is always left out”. Whatever incompleteness is established below comes from a different, independent argument.

11.3

The space of candidate physical laws is not merely uncountable, but far larger

Definition 11.2 (The space of candidate laws). Fix r ≥ 1. After Theorem 11.1 has reduced a phenomenon to r dimensionless variables, every candidate physical law governing it is, formally, a function Φ : Rr → R (with Φ(Π(q)) = 0 picking out the physically realised configurations). Write c := 2ℵ0 for the cardinality of the continuum, and L := {Φ : Rr → R}. Proposition 11.3 (|L| = 2c ). |L| = 2c , strictly greater than c = |Rr | itself. Proof. |Rr | = c for any finite r ≥ 1 (a finite product of continuum-cardinality sets has continuum cardinality). The set of all functions from a set of cardinality c to a set of cardinality c has cardinality cc . Using c = 2ℵ0 and standard cardinal arithmetic (ℵ0 · c = c for infinite c): cc = (2ℵ0 )c = 2ℵ0 ·c = 2c . So |L| = 2c . By Cantor’s theorem, 2c > c strictly, for any cardinal c. 40

Remark (A more conservative L gives the same conclusion). Proposition 11.3 allows Φ to be an arbitrary function, most of which have no physical or even computational meaning (e.g. functions definable only via the axiom of choice, with no finite description). Restricting L to continuous functions Rr → R — a far more physically defensible choice, since a continuous function is determined entirely by its values on the countable dense set Qr — gives |Lcont | = cℵ0 = c, a strictly smaller cardinality but still uncountable (c > ℵ0 ). Everything proved in Section 11.4 uses only that L (or Lcont ) is uncountable, not the specific value 2c ; the argument is robust to this more conservative choice, and to any choice of L in between.

11.4

No countable theory can equal the space of laws

Here is the argument’s decisive step, stated as a challenge before it is stated as a theorem. Hand over any theory of physics you like — one law, a thousand laws, even a list that grows forever, one new law added at every tick of a clock. It makes no difference. From that list alone, a specific new law can always be built that is guaranteed not to be on it. This is not a trick special to physics: it is the same move Cantor used in 1891 to show the real numbers outnumber the counting numbers, aimed here at laws instead of numbers. Proposition 11.4 (Diagonalization: an explicit law outside any given countable list). Let S = {Φ1 , Φ2 , . . . } ⊆ L be any countable subset. Then there exists Ψ ∈ L with Ψ ∈ / S. Proof. Fix an injection e : N → Rr (e.g. e(n) = (n, 0, . . . , 0)). Define Ψ : Rr → R by ( Φn (e(n)) + 1 if y = e(n) for some n ∈ N, Ψ(y) := 0 otherwise. This is a well-defined function Rr → R, hence Ψ ∈ L. For every n, Ψ(e(n)) = Φn (e(n)) + 1 ̸= Φn (e(n)), so Ψ and Φn disagree at the point e(n): Ψ ̸= Φn . Since this holds for every n, Ψ∈ / S. Remark (This is Cantor’s argument, and it alone already suffices). Proposition 11.4 is the classical Cantor diagonal argument, and it is already implied by Proposition 11.3 alone: a set of strictly smaller cardinality than L cannot equal L, with no diagonal construction needed to see it. The explicit construction is kept because it exhibits a specific, concrete law Ψ escaping any given countable S, which is more informative for what follows than the bare cardinality inequality; it invokes no obstruction beyond Proposition 11.3’s cardinality gap. Corollary 11.5 (No countable, ever-growing sequence of theories reaches L). Let S0 ⊆ S1 ⊆ S2 ⊆ · · · be any sequence of countable subsets of L (each Sk+1 a candidate “repaired” theory S extending Sk by countably many further laws). Then k Sk ̸= L. S Proof. A countable union of countable sets is countable, so k Sk is countable; Proposition 11.4 S applied to this countable union gives Ψ ∈ L \ k Sk . Remark (What this establishes, precisely). Corollary 11.5 is the rigorous content behind the regression “S ⊂ S ′ ⊂ S ′′ ⊂ · · · ”: however many times, even countably infinitely many times, a candidate physical theory is patched by adding new laws, the result remains countable and never equals L. This holds for any countable theory — in particular, for any theory that could ever be written down, since anything written down, however long, uses finitely or countably many symbols. This is a rigorously established obstruction to a complete, countably-writable theory of everything. Remark (The argument is already complete before Gödel or Tarski enter). What has been established, in full, by Sections 11.3–11.4 alone, is worth stating plainly before Gödel or Tarski are mentioned at all: no countable theory of everything can equal L (Proposition 11.4), and 41

no sequence of countably many patches to a countable theory, however long, closes the gap (Corollary 11.5). This is a complete proof, using only cardinal arithmetic and one classical theorem of dimensional analysis, of exactly the claim the claim box set out to make. Everything that follows in this section is commentary, comparison, and a separate further question: none of it is a premise the argument above waits on, and none of it weakens or qualifies what is already shown. Remark (“Could not have been there before”, in two senses that both hold). The escaping law Ψ “could not have been present before” in two distinct senses, and both hold. First, already fully established: Ψ ∈ / S for the specific countable list S diagonalized against (Proposition 11.4), with no further hypothesis. Second, at the level of the Buckingham apparatus turning on itself: fix the diagonal construction of Proposition 11.4 using, as the indexing coordinate e(n), not an arbitrary embedding but the first dimensionless group itself, e(n) := π1 =n (available directly from Theorem 11.1, needing no external apparatus). Then Ψ, at the point π1 = n, is defined as Φn ’s own value there, altered: the escaping law is built by turning the n-th candidate law’s behaviour, at the coordinate value π1 =n that names its own position in the list, against itself. This is a genuine self-application — the n-th object addressed by its own index, using only the coordinates Buckingham’s theorem already supplies — and it is this feature, not mere counting, that licenses reading Ψ as something no given countable list built from the level-one vocabulary could already have contained: not because no formula happened to find it yet, but because the very act of listing candidate laws by index, using the theory’s own coordinate, is what the escaping law is defined against. Ψ uses no new vocabulary, only the same r groups every level-one law uses; what it escapes is not the vocabulary but any specific countable enumeration built from it. This is lighter than Tarski’s requirement — no syntactic self-representation, no diagonal lemma, no encoding of proofs — which is why it is a metaphor relative to Tarski’s actual theorem and not an instance of it; it is no less formal, since Proposition 11.4 proves it outright under this natural choice of e. Remark (Corollary 11.5 is the Tarski-shaped content, precisely). Corollary 11.5 contains, precisely and without needing Tarski’s theorem as a premise, the feature that makes the parallel with Tarski substantive rather than decorative: not merely that some Ψ escapes a given S (Proposition 11.4 gives that), but that no amount of patching within the same kind of move — adding countably many further laws, however many times, using the same variables and the same r groups — ever closes the gap. This is exactly the shape of Tarski’s theorem: no formula added within L0 , however cleverly chosen, ever defines truth-in-L0 ; only a genuinely richer metalanguage does. Proposition 11.4 supplies the Buckingham-side half (every reduction leaves something out), and Corollary 11.5 supplies the Tarski-side half (that something is not patchable by more of the same, only by a genuine change of level) — and it is the combination that rules out both “we just haven’t found Ψ yet” and “we can add axioms indefinitely and eventually get there”. What a single joint theorem, rather than this combination of two, would additionally require is one construction, named precisely later in this section: an account of what it means for a physical theory to be a self-referential-capable formal system. A literal Tarski application and a literal Gödel application both wait on that one construction, not on two separate ones; building it is a well-defined further project. None of this affects Remark 11.4: the conclusion already stands, in full, without it.

11.5

Cantor’s argument and Gödel’s simile

Remark (Gödel enters as a simile, at the level of formality it earns). Gödel’s theorem is invoked as a simile, the way this paper’s own opening fable invoked Douglas Adams (Remark 8): a recognisable, illuminating parallel, not a premise the proof above uses. The parallel holds in one place and not in another, and both are worth being exact about. Everything proved in Section 11.4 is a cardinality argument, needing no notion of provability or any specific formal 42

system. Gödel’s first incompleteness theorem [11] is a different mechanism: for a consistent, recursively axiomatizable theory T expressive enough to encode arithmetic, one specific sentence GT , in T ’s own countable language, is true but unprovable in T — with no cardinality gap anywhere, since T ’s language, its true sentences, and its provable sentences are all merely countable. What the two share is the family resemblance the simile points at: a formal system, however carefully built, cannot capture everything true about its own domain. What they do not share is the mechanism: Cantor’s argument needs only counting; Gödel’s needs self-reference and a specific undecidable sentence. The simile is kept and named as a simile; the proof above does not rest on it. Remark (Where a literal use of Gödel could enter, and what building it requires). Beyond the simile, there is a place a literal application of Gödel’s theorem could enter, distinct from Section 11.4’s cardinality argument. Fix any single candidate theory of everything S — not the whole space L, one specific countable, consistent, recursively axiomatized S, rich enough to encode arithmetic. Gödel’s theorem, applied directly, would say S contains a sentence, in S’s own language, true of the physical system S describes but unprovable from S’s own axioms: a second, independent obstruction to completeness, this time within one theory rather than across the whole space of laws. Making this literal requires one construction: a formal language in which physical laws are sentences, a deduction system in which physical reasoning is proof, and a demonstration that this system can encode arithmetic (e.g. by encoding natural-number statements as statements about a countable family of physical configurations, the way Gödel numbering encodes syntax as number theory). That construction is not carried out here. Remark (What kind of barrier this is, named precisely). The barrier established in Sections 11.3–11.4 is worth naming for what it is, rather than only distinguishing it from Gödel’s by elimination. Three families of formal barrier are well known, and this one belongs to the oldest and logically simplest. Gödel’s barrier is self-referential : one fixed system, expressive enough to talk about its own proofs, cannot prove one specific sentence about itself. Turing’s barrier, from the halting problem, is algorithmic: no single algorithm decides, for every program and input, whether that program halts — again a fact about one fixed decision procedure failing on a diagonal instance built from itself. The barrier here needs neither self-reference nor an algorithm failing on a specific instance: it is cardinal, in the sense Cantor identified in 1891, older than either of the other two and requiring only counting — a set of one size cannot equal, or be enumerated by, a set of strictly larger size. Every countable theory is, in this precise sense, simply too small an object to be the uncountable object L, for the same reason a list of natural numbers is too small to be a list of real numbers: no cleverness in how the countable theory is built, no self-reference, no undecidable instance, changes this. This is why Section 11.4’s proofs needed nothing beyond the arithmetic of infinite cardinals — the barrier is exactly as elementary as that arithmetic.

11.6

The Buckingham–Tarski parallel, at the level of formality it earns

You might think that once Buckingham has handed you your r dimensionless groups, the reduction is finished: the phenomenon fully described, nothing left to add. In one sense it is — Theorem 11.1 really does promise that no dimensionally-consistent law among your original variables escapes those r groups. But ask a different question. Does anything escape a countable list of specific laws written using those same r groups? Cantor already answered, in Section 11.4: yes, always, however the list is built. And could you patch the list — add the missing law, then the next, then the next, forever — and finally close the gap? Corollary 11.5 already answered that too: no, never, not even with infinitely many patches. This is the same shape Alfred Tarski found in a completely different setting, and it is worth seeing why, in his own terms. Remark (Level of formality). As with the MS-DOS instance (Remark 7.5) and the Andromeda mapping (Remark 10.3), what follows is a structural parallel, not a joint theorem in which 43

Tarski’s theorem is a premise used to derive a fact about dimensional analysis. The two theorems concern different objects — languages and truth-predicates on one side, physical variables and dimensionless groups on the other — and are not shown here to be instances of one common formal statement. The precise sense in which Tarski’s theorem genuinely matters here, naming exactly what Corollary 11.5 already establishes, was given in Remark 11.4; what follows is the illustrative table version of the same point, kept for its expository value now that the precise content is on record. Tarski’s undefinability theorem [26] is usually quoted, as just above, in its conclusion only: for a sufficiently expressive formal language L0 , no formula of L0 itself can define “true in L0 ” for sentences of L0 . The conclusion alone leaves the theorem an assertion; the mechanism that turns it into a demonstration is worth giving explicitly, both for its own sake and because it is what makes precise, below, exactly how far the Buckingham/Cantor argument shares it. Remark (How Tarski’s idea becomes a theorem: the mechanism). Suppose, for contradiction, that some formula TrueL0 (x) of L0 itself correctly defines truth: for every sentence φ of L0 , TrueL0 (⌜φ⌝) ↔ φ (where ⌜φ⌝ is a name, inside L0 , for the sentence φ). Because L0 is expressive enough to represent its own syntax (the one substantive hypothesis the theorem needs), the diagonal lemma applies: for any formula θ(x) of L0 , there is a sentence ψ of L0 with ψ ↔ θ(⌜ψ⌝) — a sentence that, via its own code, asserts θ of itself. Apply this to θ(x) := ¬TrueL0 (x): there is a sentence λ with λ ↔ ¬TrueL0 (⌜λ⌝) — a Liar sentence, asserting its own untruth. Combined with the assumed defining property of TrueL0 , applied to φ = λ: TrueL0 (⌜λ⌝) ↔ λ ↔ ¬TrueL0 (⌜λ⌝), a direct contradiction. No such TrueL0 can exist. This is what turns the idea into a theorem: not the intuition that truth “feels” like it should need an outside vantage point, but a specific, checkable contradiction, manufactured by the diagonal lemma turning L0 ’s own expressive power against the assumption. Remark (The precise family resemblance with Proposition 11.4, and the one real difference). Both Remark 11.6’s construction and Proposition 11.4’s are, in the most literal sense, diagonal arguments: each builds an object (the sentence λ; the function Ψ) by making it disagree, at a self-selected point, with what a fixed enumeration or a fixed assumption says about that very point. This is kinship at the level of mechanism, not merely of outcome. The one substantive difference is the one Remark 11.5 flagged for Gödel, and it applies here identically: Tarski’s construction needs L0 to represent its own syntax, so the diagonal lemma has something to act on — self-reference is the engine, not an incidental feature. Proposition 11.4’s construction needs none of this: Ψ is built directly, by evaluating the n-th candidate at the n-th point of a fixed enumeration of Rr and changing the answer, with no sentence naming itself, no code for anything, and no representability hypothesis. Cantor’s original 1891 argument is, in this precise sense, the strictly simpler ancestor of both Tarski’s and Gödel’s: it diagonalizes against an enumeration directly, where they diagonalize against an enumeration via a system representing itself. This is why Remark 11.4’s claim needs nothing from this subsection: the completed argument uses only the simpler, ancestral technique. Remark (What is rigorously forced: a new law, not necessarily a new variable). Assume, as the sketch does, that the starting list q1 , . . . , qn is complete for the phenomenon at hand. Then Theorem 11.1 guarantees the r = n − k dimensionless groups capture every law expressible in q1 , . . . , qn (Remark 11.2); the diagonal law Ψ of Proposition 11.4 is, precisely, a function Ψ : Rr → R of those same r groups, not of any new dimensionless quantity. What is rigorously forced is only this: Ψ is a law not on any given countable list, using variables already at hand — a new law, not, by the mathematics alone, a new variable. Reading Ψ as forcing a genuinely new physical quantity (a new fundamental dimension, as thermodynamics introduced entropy or quantum mechanics introduced Planck’s constant) is a further, physically motivated step, not one the mathematics necessitates: a reasonable expectation about how such laws tend to 44

be discovered and organised — an arbitrary function of r existing quantities is rarely tractable until some new organising quantity simplifies it — but an empirical claim about physics, not a consequence of Theorem 11.1 or Proposition 11.4. With that distinction in place, the “new variable” language below is the sketch’s own framing of this expectation, marked here rather than presented as proved. The sketch’s framing, read with Remark 11.6’s distinction in mind, is that the new law Ψ, applied level by level and taken to motivate a new organising variable at each stage, cannot already belong to the dimensionless groups of the level before it — for if it did, Theorem 11.1 would already have captured it there. Both settings share the same recursive shape: a level-k description, however complete on its own terms, cannot express something that only becomes visible from level k + 1, and this repeats without terminating: Tarski’s hierarchy

The Buckingham/Cantor hierarchy

Level 0: language L0 and its sentences Level 1: metalanguage defining truth-in-L0 , provably outside L0

Level 0: variables and their dimensions Level 1: dimensionless groups (Theorem 11.1), complete for the given variables Level 2: a law Ψ (Proposition 11.4) outside the level-1 groups by construction, and so on

Level 2: a further metalanguage for truth-in-level1, and so on

The two results reinforce each other in this qualified sense: Theorem 11.1 guarantees each level is complete for what it was given (Remark 11.2), and Proposition 11.4 guarantees something new is always constructible outside it; Tarski’s theorem is the source of the template — a hierarchy that cannot be collapsed to a single level — not a premise feeding into either proof above. Whether a single, unified theorem joining Buckingham-style completeness with Tarski-style level-separation exists, rather than a parallel between two structurally similar but formally separate arguments, is an open question this section does not resolve. IMPORTANT: To conclude, and to say it once more: these observations are developed the way a computer scientist would develop them, and are offered as a seed for physicists, who may read them and develop the idea further should it prove correct. They do NOT preclude the possibility that a metatheory exists that bypasses this result, nor the existence of other hidden assumptions that could change the results.

11.7

Why this is not a closure: the key point

This is the promise made in the claim box at the very start of this section, now made precise: the barrier just proved is not bad news. Remark (Incompleteness as an opening, not a wall). It would be a misreading of Corollary 11.5 to take it as saying physics is impossible, or the search for deeper laws futile. The correct reading is the opposite, and it is the same reading Gödel’s own theorem earned, after decades of being misread as a limitation: incompleteness is not a wall at the edge of a finite territory, but a guarantee that the territory has no edge. Corollary 11.5 does not say any particular true law is unreachable forever; it says no finite or countable stopping point can ever be the last one — that whatever countable theory physics has reached at any moment in its history, Sk , there is always a Ψ ∈ / Sk still to be found, by the same argument applied again. This is a statement 45

about the shape of the search, not its termination: the search for physical law is not a project that could, even in principle, be completed and closed off, and Corollary 11.5, if its hypotheses are granted, makes this a theorem rather than a hope. Read this way, what looks like a negative result is a positive one: a rigorous argument that, on the premises it names, the project of physics is inexhaustible, that every advance provably leaves further advances still to be made, and that this inexhaustibility is a structural fact about the space of possible laws so described, not a contingent fact about the current state of knowledge. The difference this makes is concrete. Before Corollary 11.5, a physicist who suspects a current theory Sk is incomplete has a hope, not a guarantee: Sk might, for all anyone can rule out, actually be complete, and the search for Ψ ∈ / Sk might be a search for something that does not exist. After Corollary 11.5, the situation differs in kind, not merely in confidence: for every countable Sk , whatever it is, Ψ ∈ / Sk is guaranteed to exist, and Proposition 11.4’s construction produces it explicitly once Sk is given. Finding a new law Ψk and folding it into Sk+1 := Sk ∪ {Ψk } does not close the search; it hands the same guarantee, applied to Sk+1 , a new Ψk+1 ∈ / Sk+1 to look for — a specific discovery that was not visible, and could not have been asked for, before Ψk was found and Sk+1 existed to diagonalize against. This is the precise sense in which every barrier here creates a new, previously invisible possibility: not a metaphor, but the literal input-output structure of Proposition 11.4, iterated as far as Corollary 11.5 allows — which is to say, without end. Remark (Not absolute — and saying so is part of the argument). Corollary 11.5 is not claimed as an absolute barrier, and saying so belongs to reading the result correctly, for two reasons. First, this whole paper has been built on the discovery, repeated several times over, that a result taken as settled rests on a silent assumption once someone thinks to look for one (Remark 11.1); this section’s own argument has no special exemption from that pattern, and every premise — that “physical law is a function Rr → R”, that “countable” is the right notion of what a theory or a mind can produce, or some premise not yet identified — is left open as a place a future hidden assumption could be found. Second, and separately, nothing here rules out a metatheory that changes the terms of the question entirely, rather than defeating the argument on its own terms; this is the expected shape of a result like this one. Gödel’s incompleteness theorem did not close mathematics — it opened metamathematics, proof theory, and a century of work on what formal systems can and cannot do, precisely because mathematicians read it as a discovery about the shape of formal systems rather than a wall. Turing’s halting problem did not close computer science — it opened computability theory and, eventually, complexity theory, read the same way. If Corollary 11.5 is correct and its hypotheses hold for physics, the response the same precedent recommends is not to treat physics as closed off at some boundary, but to treat the corollary as the first theorem of a new inquiry into the shape of that boundary. This is why the section is offered as a beginning, and why Remark 11.1’s obligation to flag every open point is the entire point of writing it down. Remark (Independence of the proof; the connection now made). This section’s rigorous content (Sections 11.2–11.4) depends on nothing constructed elsewhere in this paper: it is self-contained cardinal arithmetic and one classical theorem of dimensional analysis, and the proof stands exactly as given regardless of what follows. What follows is the connection promised, and deferred, since Section 8’s own opening. Remark (The same shape, a third time: countable description against a larger space). Proposition 11.3 and Proposition 11.4 are a third instance of a pattern this paper has already proved twice, in two unrelated domains. Section 8.3’s Proposition 8.8 shows the space of all selectorfunctions has cardinality 2ℵ0 , while the computable ones — everything a Turing machine can produce — are only countably many. Section 10.4’s Proposition 10.2 shows a continuum of physical states, forced through this paper’s countable frame space, must collapse uncountably many of them onto a single frame. Both are instances of the same elementary fact used throughout 46

Section 11.4: a countable object cannot equal, or faithfully represent, an object of strictly larger cardinality, however that countable object is built. Here the countable object is any theory that could ever be written down — by a person, a computer, or any process producing symbols one at a time, forever — and the larger object is L itself. The three instances share no formal machinery beyond cardinal arithmetic and, in each case, an explicit diagonal witness (a selector escaping any computable enumeration; a physical state escaping any single frame’s fibre; a law escaping any countable theory); they are not one theorem restated three times, but the same one-line fact — a countable set cannot exhaust an uncountable one — recognised, independently, as the load-bearing obstruction in three domains that have nothing else in common: abstract computation, special relativity, and the foundations of physical law. This is evidence of the same kind Remark 6.3 and Remark 8.7 already offered for their own repeated shapes: not a single grand theorem unifying all of this paper’s results (Section 9 explains why none is attempted), but a record that the same elementary fact, checked freshly and independently each time, turned out to be exactly what was needed, three times running. The core argument of this section is now complete and stands on its own, exactly as concluded above. What follows is a further, independently arising instance of the same silent-assumption pattern, in a different domain — computability and cryptography rather than physics — developed here because it, too, connects back to this paper’s central theme, not because it continues the Buckingham/Cantor argument just finished.

12

A fourth, independently arising instance: an algorithm’s output can be indistinguishable from noise

Like Sections 8, 10, and 11 before it, this section stands on its own and depends on nothing built above; it uses none of the theory-of-everything’s results, and reaches its conclusion from Turing’s 1936 definition of computability directly. It is placed here not to extend the paper but because the hidden assumption it isolates is the sharpest of all the ones this paper takes apart, and the only one that can be witnessed unconditionally. The assumption is the silent identification of “indistinguishable from random” with “meaningless” — and once it is dropped, the notion this whole paper has been circling, an object fully determined yet opaque to a stated class of observers, is finally named in its own right (Definition 12.3), which is why the section is load-bearing rather than illustrative. One distinction governs everything that follows, and it is worth stating before the claim, because the section’s most famous object tends to eclipse it. The phenomenon here is that an output can be fully determined and meaningful and yet indistinguishable from random noise to every observer in a stated class. This does not require the output to be non-computable. Ordinary, perfectly computable algorithms already produce such output, and they do so for reasons that are not all of a kind: the weakest is computational — a secure pseudorandom generator’s output is the standard example (Remark 12.1), computable and halting, its seed fully recoverable in principle, yet indistinguishable from noise to every polynomial-time observer, though an unbounded one could in principle break it — while the stronger reasons are structural and cede to no amount of computational power at all, so that a computable algorithm’s output can be opaque not merely to efficient observers but to every observer at once (Remark 12.1). Chaitin’s Ω, which the next subsection leads with, is a third thing again, on its own axis: not the output of any algorithm, and opaque to every computable observer for the distinct reason that reading it would require computing the uncomputable. It is included because it is the cleanest unconditional witness that meaning and opacity can coexist, the sharpest single object of the three kinds — but it is one witness of the phenomenon, not the phenomenon itself, and the everyday computable versions, the ones that reach cryptographic practice and that this paper is really about, must not be collapsed into it (Remark 12.1 keeps them apart).

47

12.1

The hidden assumption: meaningful output indistinguishable from noise Claim, stated directly, proved below. Standard computability theory implicitly permits — and this permission is realized, not merely left open — output that is fully determined and meaningful yet indistinguishable from noise to a stated class of observers. The opacity comes in more than one form, and running them together is the error this section exists to prevent. Three forms will matter, and it helps to hold them apart from the outset: one that a powerful enough observer can break (the pseudorandom case), ones that no observer can break because the obstacle is structural rather than a matter of power (the SIP and the encoding–frame mismatch), and one sharper still that no computable observer can break because reading it would mean computing the uncomputable (Ω). Now each in turn. The weakest is computational: for a computable algorithm, the opacity may be to a bounded class only — a halting, computable procedure can have output indistinguishable from noise to every polynomial-time observer (Remark 12.1), conditional on standard cryptographic assumptions, and an unbounded observer may in principle break it. That form cedes to more computational power. The others do not, because they are not about power at all. A computable algorithm’s output can be indistinguishable from noise to every observer, bounded or unbounded, when what hides it is structural: a semantic invariant syntax cannot see (the static SIP, Lemma 2.4), or an encoding–frame mismatch under which no reading renders it (the orbital machine, Section 8) — neither of which draws any distinction of computational power, so the opacity they produce holds against every observer alike, unconditionally (Remark 12.1). And in its sharpest unconditional form the opacity is total to every computable observer for a further, distinct reason — non-computability — but is then witnessed by an object that is not an algorithm’s output at all: Chaitin’s Ω (Proposition 12.1), and, beyond Ω alone, a pairing available for every computable decision problem whatsoever (Theorem 12.4). None of these is an edge case tolerated by a loophole: the pseudorandom form is the load-bearing assumption behind modern cryptography, the structural forms are the subject of this whole paper, and the non-computable form follows directly from Turing’s own 1936 definition of computability (Remark 12.1). Underneath every one of them lies the single fact this section is built to expose: the standard theory admits such algorithms implicitly and with no distinction of computational power of its own — it permits output indistinguishable from noise not merely to efficient observers but to every observer, and it does so regardless of which of these reasons, or which other reason, makes any particular output opaque. The remainder of this section establishes the computational and non-computable forms rigorously, invokes the structural ones from where they are proved, and keeps all of them apart; the unconditional half is proved, not inferred from what the theory declines to forbid.

Remark (The root: the founding definition of computability never opened this question). A Turing machine M computes a function f if, for every input x on which f is defined, M (x) halts and outputs f (x) — Turing’s 1936 definition [27], unchanged since. Nothing in it constrains what f (x) looks like: no clause requires the output to be compressible, statistically unremarkable, or recognisable by any observer as meaningful. The distinction is exact, and worth stating in the algorithm’s own terms rather than an observer’s: the output of M is the string written on the tape; the interpretation of that output is a separate question, about whether some agent, reading the tape, can recover what it means. Computability theory, from its founding definition onward, is a theory of the first — the existence of a correct, halting, deterministic map from input to output — and says nothing about the second. If f (x) happens to look like noise to some observer, that is, in the theory’s own terms, a fact about decoding, not about computation; 48

the theory neither requires nor forbids it, because readability was never part of what “solving a problem” was defined to mean. Remark (The boundary the definition itself already draws: a die roll is not an algorithm). Turing’s definition already settles a boundary worth stating explicitly, since it is what makes the rest of this section coherent rather than permissive of anything whatsoever. “M computes f ” requires a function f : a fixed, well-defined correspondence between input and output, the same f (x) every time M is run on x. A process that outputs unrelated noise on repeated runs of the same input — a die roll wired to the tape, independent of x — computes no function at all, and so is not an algorithm in Turing’s sense; this is not an added restriction on top of the classical definition, it is already inside it. What the classical definition permits, and this section shows can genuinely occur, is the opposite case: a fixed, deterministic, correct correspondence between input and output, in which f (x) itself, for each x, happens to look like noise to a stated class of observers. The two cases are not close variants: one fails to be an algorithm at all, the other is exactly as valid an algorithm as any other, precisely because the definition was never about how f (x) looks, only about whether f (x) is what it is supposed to be, every time. Chaitin’s Ω, discussed next, sits on neither side of this boundary — it is not computable at all, hence not an algorithm’s output in either sense — but the pseudorandom-generator family below is squarely on the valid side: G is a genuine algorithm, G(s) its actual, deterministic output for each seed s, and the existence of a key (the seed, or the search inverting G) to recover the input is exactly why the classical theory accepts this case without reservation — information preserved rather than destroyed, appearance of disorder notwithstanding. Remark (What computability theory is about, and what it is not). If an algorithm’s output has high entropy yet contains the exact solution to the problem it was built to solve, the information is present, and computability theory concerns itself with the presence of information and the possibility of generating it, not with its aesthetics or with how easily it can be recognised by inspection. Accepting this limiting case is required for the theory’s own logical consistency, not an optional generosity toward exotic examples: excluding algorithms on the basis of the quality or readability of their output would import a subjective criterion into a discipline whose definitions are built to need none — two observers could disagree about whether an output “looks like” a solution, where they cannot disagree, given the specification, about whether it is one. This is not hypothetical: many genuinely hard problems are solved by reducing them to simpler ones, and the intermediate or final representations produced along the way routinely have no intuitive sense to a human reader, while being exactly, formally equivalent to the solution. An algorithm solving a problem this way is accepted without qualification, because the classical theory defines a solution as the capacity to map an input to a correct output, deliberately setting aside whether that output is comprehensible, elegant, or apparently random. Remark (The same point, from algorithmic information theory). This connects directly to Kolmogorov complexity [16]. By the Levin–Schnorr theorem [24, 17], an infinite sequence is MartinLöf random exactly when its finite prefixes are Kolmogorov-incompressible up to a bounded additive constant: “looking like noise to every statistical test” and “carrying the maximum possible information density, with no redundancy left to compress away” are, formally, the same phenomenon, not opposites. Apparent disorder in an algorithm’s output is not evidence of missing information; for the output of a valid algorithm it can be exactly the reverse — information at maximum density, in a representation with nothing left over for an unequipped observer to exploit. Remark (Why this is the root, and what the rest of this section adds). Remarks 12.1 and 12.1 are why a relative, per-observer-class vocabulary for usability, introduced later in this section, could not be reached by strengthening the classical definition of algorithm: that definition never opened the question of usability, for any observer class, in the first place. What the rest of this 49

section adds is not a correction to this founding silence — the silence is exactly right, by design — but the strongest available concrete witness that the silence has real content: not merely that the classical definition permits noise-like output in principle, already established above, but that a specific, meaningful answer to a specific, genuine question can be produced this way, unconditionally, and shown so with proof, starting from Chaitin’s Ω next. Remark (What standard theory silently conflates, in the matter of pseudorandomness). Standard treatments of pseudorandomness and algorithmic output speak of a string being “computationally indistinguishable from random” as if this settled a single question. It settles only an access question — no computable procedure succeeds at telling this string apart from a fair coin sequence — and says nothing, by itself, about a different, ontological question: whether the string encodes something meaningful at all. The silent assumption is that these two questions collapse into one. They do not, and both a specific mathematical object with no algorithm behind it and a specific algorithm’s actual output can independently witness this, as the rest of this section shows for each in turn. Here is a real number that seems, at first hearing, impossible. It answers a genuine question completely, bit by bit. And yet no computer on Earth, however long you let it run, could ever tell its digits apart from the flip of a fair coin. It exists. Chaitin found it in 1975. It is called Ω. Proposition P −|p| 12.1 (Chaitin’s Ω: meaningful and indistinguishable from noise at once). Let Ω = p↓ 2 , summed over halting programs p of a fixed universal prefix-free machine. Then: (i) knowing the first n bits of Ω decides the halting problem for every program of length ≤ n [9], so Ω is, bit for bit, a complete and meaningful answer to a genuine decision problem; and (ii) Ω is Martin-Löf random [18, 9]: no computable statistical test detects any deviation whatsoever from a fair coin sequence. (i) and (ii) hold of the same object at once. Remark (What Ω is, and what it does not license). Ω is famously not a computable real number: an algorithm outputting its bits one by one would decide the halting problem, contradicting Turing [27]. So Proposition 12.1 is a fact about Ω as a well-defined mathematical object (a specific real number, given by a convergent sum), not about the output of any halting Turing machine, and this sharpens Remark 12.1’s distinction further: an algorithm whose output happens to look like noise is a different thing from an object, like Ω, that is not an algorithm’s output at all — a case the classical theory was never asked about, since it was never a question about algorithms to begin with. Ω’s role here is as the cleanest unconditional mathematical witness that meaning and full computable-opacity can coexist in principle; the genuinely algorithmic witness — a real, halting, computable procedure whose actual output is noise-indistinguishable to a stated class — comes later in this section, from a conditional pseudorandom-generator family. This licenses a narrower claim than it may seem to: most strings indistinguishable from noise carry no hidden meaning at all. A genuinely Martin-Löf random sequence from a real random source has nothing encoded in it for any observer, however powerful, to find — Ω is special not merely for being indistinguishable from noise (true of almost every infinite binary sequence) but for being, additionally and independently, a specific, meaningful answer (Proposition 12.1(i)) that also satisfies (ii). The general statement this licenses is conditional: if a string is the output of a valid algorithm solving a genuine decision problem, and that output is computationally indistinguishable from noise, then reading it requires a key beyond any computable observer’s reach. Proposition 12.2 (Not one instance but infinitely many, unconditionally). For each universal P prefix-free machine U , let ΩU := p↓ under U 2−|p| . For infinitely many choices of U , the resulting ΩU are pairwise distinct real numbers, each independently satisfying Proposition 12.1(i) and (ii) for its own U (and each, by Remark 12.1, equally not computable, hence equally not the output of any algorithm). Chaitin’s Ω is therefore not a singular mathematical curiosity: it is one point in an infinite, unconditionally proven family of objects with complete, meaningful content that is Martin-Löf random. 50

Remark (A second, conditional family, tied directly to cryptographic practice). A weaker, more widely applicable version of the same phenomenon is standard in cryptography, conditional on an assumption this paper does not prove: if a secure pseudorandom generator G : {0, 1}k → {0, 1}m exists (following, unconditionally, from the existence of one-way functions, themselves unproven but standard), then for a uniformly random seed s, G(s) is meaningful in exactly the sense required here — it determines s completely, answering the genuine question “which seed produced this string” — while being computationally indistinguishable from a uniformly random string of {0, 1}m for every polynomial-time observer. This is a strictly weaker opacity than Proposition 12.1(ii) (only polynomial-time, not every computable, observer is excluded, and the guarantee is conditional, not unconditional), stated separately and not conflated with the Ω case; but it shows the same structural point is the load-bearing assumption behind an entire field’s central security definitions, not an exotic edge case confined to algorithmic information theory. Remark (A computable algorithm’s output can be noise-indistinguishable to every observer, not only efficient ones). The pseudorandom case above is the weakest of these, and it is worth being explicit about why, because the weakness is easy to mistake for the whole phenomenon. Its opacity is tied to computational power: a secure pseudorandom generator’s output is indistinguishable from noise to every polynomial-time observer, but an observer with unbounded resources can, in principle, tell it from random; and the guarantee is conditional on an unproven assumption. Power-bounded and conditional — that is the floor, not the ceiling. A computable algorithm can do strictly more: it can produce output that is indistinguishable from noise to every observer, human or machine, bounded or unbounded, always and everywhere. What makes this possible is that the reasons need not be computational at all. At least two are structural, and neither draws any distinction of computational power, because the blindness they cause is not a matter of resources. The first is total or partial semantic inaccessibility — the static SIP (Lemma 2.4): a semantic invariant carried in the output is invisible to any syntactic inspection of it, for every observer alike, since syntax cannot see semantic invariants no matter how much power is brought to bear. The second is the encoding–frame relativity of the orbital machine (Section 8, Remark 8.4): whether the output reads as meaningful is relative to a pair (E, F ), and under a pair other than the intended one it may fail to parse, answer a different question, or answer nothing discriminating (Categories 1–3, Propositions 8.15–8.17) — again with no dependence on the reader’s power, since no amount of computation supplies a reading the frame withholds. Both hold against every observer at once, unconditionally, exactly where the pseudorandom case holds only against bounded ones and only conditionally. The output might also be indistinguishable from noise for some further reason entirely, and it does not matter which: the list is not meant to be exhaustive, and nothing here depends on having found every route. What matters is the one thing common to all of them, and it is the load of this section: the standard theory admits the existence of such algorithms — computable procedures whose output is indistinguishable from noise — implicitly, and without any distinction of computational power of its own. Its implicit permission is not for “opaque to efficient observers” but for opaque, full stop; it grants the strong, every-observer case no less than the weak, bounded one, and grants it regardless of which of the reasons above, or which other reason, is what makes a particular output opaque. This is why no algorithm need be exhibited for each case, and the reason is positive, not a concession. The pseudorandom case is already the existence of one-way functions in another guise: to deny that a computable algorithm can have output indistinguishable from noise is to deny that secure pseudorandom generators exist, which is to give up the foundations of modern cryptography and, with them, part of the standard theory itself. The structural cases stand on ground just as firm: the static SIP and the encoding–frame relativity are theorems, proved in their own sections, and they produce indistinguishability from noise with no dependence on the observer’s power. The theory grants the possibility; these mechanisms are what realize it; 51

both are already in hand. To insist that such an algorithm cannot exist until one is displayed is therefore not a demand for rigor but a rejection of the theory that admits it — the same theory whose definitions were used to raise the question. This is not the weak move of reading existence off what the theory merely fails to forbid; it is the strong one of reading it off what the theory positively contains — one-way functions in the pseudorandom case, proved theorems in the structural cases. The existence is fixed by that content, and exhibiting a separate witness in each case would add nothing the standard theory does not already own. The two structural reasons are established elsewhere in this paper on their own terms and only invoked here; the pseudorandom case, the two structural reasons, any further reason, and the theory’s power-blind permission over all of them are kept distinct, the same discipline applied throughout. Both cases above are instances of a single notion the classical theory never named, though cryptographers have long used a narrower special case of it under the name computational indistinguishability. Naming it is not bookkeeping: without a word for it, there is no way to say, precisely and without contradiction, “this algorithm’s output is real, correct, and meaningful, merely unverifiable by anyone in this observer class” — the sentence has nowhere to attach, and the two questions Remark 12.1 separates collapse back into one by default, exactly the error Ω and Theorem 12.4 were needed to expose. The definition below exists to block that collapse: it gives the vocabulary to state, of a real algorithm accepted by every classical criterion, that its output is opaque to some observers without that opacity being mistaken, even silently, for absence of meaning. In plain terms, before the formal statement: an algorithm is usable, relative to a class of observers, exactly when its output is not indistinguishable from pure random noise to everyone in that class — at least one observer in the class can tell it apart from randomness. It is opaque, relative to that same class, when its output looks like noise to every observer in it. Nothing is ever claimed absolutely usable or absolutely opaque; the class is always named. Definition 12.3 (C-usable algorithm). Fix a class C of observers (tests), each a procedure taking a string and returning a verdict. A valid algorithm A (in the ordinary, classical sense: a total or partial computable function, correctly computing whatever it is specified to compute) is C-usable if some observer in C distinguishes A’s output from a uniformly random string of the same length; otherwise A is C-opaque. This is a property of the pair (A, C), not of A alone: the same algorithm can be C-usable for one class and C ′ -opaque for another. Remark (What this adds, what it leaves unchanged, and how far it reaches). Definition 12.3 adds a name for something the classical theory left implicit and unparametrized: usability is always relative to C, never absolute, in exactly the sense every other notion in this paper has been relative (a frame, a selector, an oracle). What it leaves unchanged is “algorithm” itself: an algorithm’s validity, in the classical sense, still depends only on whether it correctly computes its specified function, regardless of any observer class. Making “algorithm” itself depend on C, rather than adding a separate relative notion beside it, would have risked exactly the error Remark 12.1 warns against — treating a non-computable mathematical object as an algorithm’s output that had somehow stopped qualifying — and the definition’s wording avoids it: “some observer in C distinguishes this from a uniformly random string” makes sense verbatim for any fixed mathematical object (a specific real number’s bit sequence, a specific string), whether or not any algorithm produces it, since nothing in the wording requires A’s output to come from a halting computation, only that it name a specific string to test. Ω (Remark 12.1) is exactly such a case: not an algorithm’s output, but an object with a well-defined Ccomp -usability profile all the same, studied identically to the algorithmic case below. Remark (The whole point, in one place: this definition was already there, unnamed). A Cusable algorithm is not a new kind of algorithm, built by relaxing or strengthening Turing’s 1936 definition; it is an ordinary algorithm, unchanged, that happens to also satisfy one further, 52

independently checkable property. C-usability is, in the precise sense of the word, a restriction: the C-usable algorithms are a subset of all algorithms, singled out after the fact by a criterion — does some test in C tell this output from noise — that Remark 12.1 already showed the classical definition never asks about. This is why the distinction was already there, latently, before this section named it: since classical computability theory accepts an algorithm’s validity regardless of how its output looks, it was, all along, silently accepting both kinds at once, usable and opaque alike, without a name to tell them apart. Naming C-usability adds nothing to what counts as an algorithm and takes nothing away; it draws, after the fact, a line through a distinction the classical theory’s own silence had already made room for. This is what makes the definition worth having rather than an arbitrary addition: it does not compete with the classical theory, it reads a distinction out of what that theory was quietly permitting the entire time. Remark (Does the restriction cost the same for every C? It does not, and the difference is substantial). Restricting attention to C-usable algorithms takes nothing from classical computability theory and adds nothing to it — but only for one specific choice of C. Whether this holds for every C is worth asking directly, since the answer is no. For C = Ccomp , the restriction really is free, exactly as Remark 12.2 shows: an unbounded observer can always redo the same computation and check the output matches, so nothing is thrown away when the watcher is allowed unlimited time. Restrict instead to Cpoly -usable algorithms — watchers confined to a reasonable, polynomial amount of time, the kind any real computer has — and the picture changes completely. An enormously useful class of real algorithms exists whose whole purpose is to take a short, easily produced secret and stretch it into a long stream of bits that no efficient watcher, however cleverly built, can tell apart from a fair coin flipped over and over: this is exactly what makes a stream of digital keystream, the raw material behind most everyday encryption, safe to use. Such a construction is a pseudorandom generator, and calling one secure means precisely that no polynomial-time observer can win at telling its output from true randomness — the property this paper has been calling Cpoly opaque, under a different name. So the moment “algorithm” is redefined to exclude anything Cpoly -opaque, every secure pseudorandom generator stops counting as an algorithm at all — absurd on its own, and with a precise, provable cost behind it. Building a secure pseudorandom generator is exactly as hard, mathematically, as building a one-way function [10]: a rule easy to compute in one direction and, once computed, practically impossible to run backwards — mixing two colours of paint is the everyday version, trivial to do and, once done, not undoable by looking at the result. The Håstad–Impagliazzo–Levin–Luby theorem [13] makes the equivalence exact: a secure pseudorandom generator exists if and only if a one-way function does. So restricting “algorithm” to Cpoly -usable outputs is not a harmless bookkeeping choice parallel to the Ccomp case; it is equivalent, in effect, to declaring outright that no one-way function exists anywhere — that paint-mixing can always be undone by someone clever and fast enough. In the vocabulary of Impagliazzo’s worlds, used elsewhere in this paper for Cell (d) but naming a different world here — Cell (d) sits at the opposite, strongest end, Cryptomania (Proposition 5.1), while this restriction sits at the weak end — that declaration places us in Pessiland or below, per [4]’s own account. Nobody has proved that assumption false, but nobody has proved it true either, and it is the single most consequential open question modern cryptography is built on — most of the field actively expects it to be false, and has built an entire applied science on that expectation. The two halves of this remark are not two examples of the same kind of cost. That the Ccomp restriction is free is a theorem: an algorithm blind regardless of time and computational power does not exist, and provably so — not because none has been found, but because the recomputation argument rules it out for every case at once. That the Cpoly restriction is costly rests on no proof in either direction: whether a secure pseudorandom generator, blind only to efficient watchers, exists is exactly as open as whether a one-way function does. One side of this remark is settled; the other is one of the genuinely open questions of the field, and it matters that a reader come away knowing which is which, not with the two blended into a single “it 53

depends”. The lesson is not about Cpoly specifically: “restrict algorithm to its usable part” is not one move with one fixed price, free at the very top of the hierarchy and, one step down, equivalent to deciding one of the deepest open problems in the field by declaration rather than by proof. Remark (“Blind regardless of resources” is not one mechanism but several, and they must be kept apart). The Ccomp case above is a blindness that holds no matter how much computational power a watcher is given. This is not the only place in this paper where power stops mattering, and the other place gets there for a completely different reason — so different that calling both “absolute blindness” would blur something worth keeping sharp. Take O⊥ (Definition 4.1): a system fed only O⊥ (x) = ⋆ cannot recognise anything nontrivial, regardless of computational power (Proposition 4.2). The static and Dynamic SIP results, and Categories 1 and 3 of the orbital machine’s taxonomy (Propositions 8.15 and 8.17; Category 2 is a different phenomenon — underdetermination rather than blindness — deliberately excluded here, exactly as Remark 12.2 insists), all share this shape. In every one, no amount of computational power helps, for a reason that has nothing to do with computation: the information was never carried through in the first place. O⊥ maps every input to the same symbol, so nothing distinguishing two inputs ever reaches what receives its output; the frozen constants of the static SIP are never touched by any rule, so no derivation brings their order into view; a beaver frame has only one point to send anything to, so no distinction survives being evaluated there. This is blindness by destruction: the channel discards the information, once and for all, before any watcher — powerful or not — gets a turn. One qualification keeps this from being read too rigidly. The SIP is placed under destruction here for the case it was first proved in — the invariant on the input, the frozen constants never carried through — but the same principle produces unreachability, not destruction, when it acts on an output instead. An output is itself a syntactic object; a semantic invariant protected in it is genuinely present, carried through in full, yet inaccessible to any syntactic inspection of it (the reopening of Section 8.4, where this is separated from the distinct question of decidability in Remark 8.4). There the information is not destroyed but unreachable, and the SIP is the reason, exactly as it is the reason on the input side. So the SIP is not confined to one column: it is destruction when the protected invariant never enters, and unreachability when it enters but syntax cannot see it — one principle, appearing wherever a semantic invariant is put beyond syntactic reach, by either route. Ω’s blindness to Ccomp adds a second, independent route to unreachability on top of that one. The information is not destroyed; Ω’s bits are a specific, fixed, fully determined sequence, present in the strongest sense (Proposition 12.1(i)). What makes it unreachable to every computable watcher is not that the channel discarded anything, but that recovering it requires Ω itself to be computed, and Ω cannot be. This is unreachability by non-computability, a sharper obstruction than the syntactic inaccessibility just described and not to be conflated with it: Ω’s answer is beyond syntactic reach in the SIP’s sense and, further, beyond any computable reach at all. It is exactly why no algorithm can ever land here, while O⊥ -style blindness by destruction is something an ordinary, mundane algorithm produces routinely, on purpose, whenever it is built to discard information. Three mechanisms, then, not one generic “totally blind”, sit side by side in this paper: blindness by limited resources (the pseudorandom generator, contingent on an open conjecture), blindness by destruction (O⊥ , the frozen SIP constants, Categories 1 and 3, proved and unconditional), and blindness by unreachability — itself of two kinds, the syntactic inaccessibility of an invariant present in an output (the SIP acting on the output side, Remark 8.4) and, sharper still, Ω’s non-computability (proved and unconditional, available only to objects no algorithm computes). Keeping these mechanisms apart is the same discipline this paper has applied to every other pair of things that resemble each other without being the same. Ω is remarkable, but is it a freak accident of one particular number, or does the same trick work everywhere? It works everywhere. Take any decision problem you like — any yes/no 54

question a computer could ever be programmed to answer, however mundane — and there is a way to dress its answer up so that it, too, becomes indistinguishable from noise, while staying completely recoverable to whoever holds the key. Theorem 12.4 (Every decision problem admits a noise-indistinguishable, fully meaningful pairing). Let D = (d1 , d2 , d3 , . . . ) be the answer sequence of any computable decision problem (an algorithm deciding, for each i ∈ N, some yes/no question indexed by i). Define X := D ⊕ Ω, the bitwise XOR of D with Chaitin’s Ω from Proposition 12.1 (written X, not E, to avoid any collision with this paper’s unrelated use of E for an explicit encoding in Sections 7.7 and 8). Then: (i) X is fully meaningful — given oracle access to Ω, D is recovered exactly, bit for bit, via D = X ⊕ Ω; and (ii) X is Martin-Löf random, hence Ccomp -opaque (Definition 12.3), regardless of which decision problem D was. As with Ω itself (Remark 12.1), X is not computable (if it were, Ω = X ⊕ D would be computable too, D being computable, contradicting Proposition 12.1): this theorem is a mathematical pairing fact about well-defined sequences, not a construction any algorithm carries out. Proof. (i) is immediate: XOR is its own inverse, so X ⊕ Ω = (D ⊕ Ω) ⊕ Ω = D. (ii): Martin-Löf randomness is preserved under bitwise XOR with any computable sequence. If some computable statistical test T detected non-randomness in X = D ⊕ Ω, then, since D is computable, T ′ := T composed with “XOR the input with D’s bits” is itself a computable test, and T ′ applied to Ω recovers exactly T ’s verdict on X (since Ω = X ⊕ D), giving a computable test detecting nonrandomness in Ω — contradicting Proposition 12.1(ii). So no such T exists: X is Martin-Löf random. Remark (What this theorem does, and does not, claim). Theorem 12.4 answers directly why Definition 12.3 is not motivated by two narrow examples: the phenomenon is not exotic to Ω and secure pseudorandom generators — every computable decision problem whatsoever, including ordinary combinatorial and decision algorithms of every kind, can be paired, as a mathematical fact, with an equally meaningful, fully Martin-Löf-random object, via a single fixed transformation. This pairing, exactly like Ω itself (Remark 12.1), is not something any algorithm performs — it requires Ω, which is not computable — so the theorem does not claim any decision algorithm can be made to directly output such a pairing; the genuinely algorithmic witness of the phenomenon remains the pseudorandom-generator family (Remark 12.1). What the theorem does claim is narrower and still worth having: the mathematical phenomenon Proposition 12.1 exhibits for one specific case is available, as a fact about objects, for every decision problem without exception. It does not claim that decision algorithms typically produce noise-indistinguishable output (the untransformed answer sequence D of an ordinary algorithm — a satisfying assignment, a shortest path, a primality verdict — is usually far from noise-indistinguishable), nor that the pairing is itself computable. It is an existence statement about a mathematical relationship, not a claim about typical algorithmic behaviour or about what any algorithm can be made to output — the same distinction Remark 12.1 drew for Ω, now extended to every decision problem. Proposition 12.5 (A usability profile, not a single verdict — for objects and for algorithms alike). Let Ccomp be the class of all computable observers and Cpoly ⊊ Ccomp the class of polynomialtime observers. Three examples show that usability is a profile across classes, not a single verdict. First, take ΩU for any U as in Proposition 12.2. This is an object, not an algorithm’s output, but Remark 12.1 already covers this case under Definition 12.3. By Proposition 12.1(ii), ΩU is Ccomp -opaque, hence also Cpoly -opaque. Yet it is {OF }-usable for a frame F with oracle access to ΩU (Section 8.6). Second, take a genuine algorithm: one computing G(s) for a secure pseudorandom generator G (Remark 12.1). This is Cpoly -opaque, conditionally on G’s security. Yet it is Ccomp -usable: a single unbounded search, either over all seeds or over Image(G), distinguishes it computably, though not efficiently. 55

Third, take an ordinary algorithm producing, say, a sorted list. This is Cpoly -usable directly, since sortedness is a polynomial-time-checkable property. No single one of Ccomp , Cpoly , or a specific oracle class settles usability once and for all: each object or algorithm has a profile across classes, not a verdict, and comparing the first example against the second and third shows that this profile is worth tracking whether or not any algorithm is behind the object in question. Proposition 12.6 (Usability is monotone in the observer class). If C ⊆ C ′ , then C-usable implies C ′ -usable (equivalently, C ′ -opaque implies C-opaque). Proof. If some observer in C distinguishes A’s output from random, that same observer is also in C ′ ⊇ C, so A is C ′ -usable too. Monotonicity lets us define the exact dual of opacity cleanly: what it means for an algorithm’s output to be usable at every level at once, not just some. Definition 12.7 (Transparent algorithm: the dual notion). Fix a baseline class C0 (in practice, Cpoly , the weakest class this paper treats as practically relevant). An algorithm A is transparent if it is C0 -usable. By Proposition 12.6, a transparent algorithm is automatically C-usable for every C ⊇ C0 considered in this paper, up to and including Ccomp : transparency is not one more point on the profile, but a guarantee that closes off the entire richer end of it at once. Remark (Why this completes the picture, and how it names cryptographic failure precisely). Definition 12.7 is the exact dual of Proposition 12.1(ii) and Remark 12.1’s security guarantee, not a new idea bolted on afterward: an ordinary algorithm (Proposition 12.5(iii)) is transparent by construction, and this is the overwhelmingly typical case, exactly as Remark 12.1 insists. It also gives cryptographic insecurity its precise name in this vocabulary: a cipher or generator is broken, in the sense every security proof in cryptography is trying to rule out, exactly when its output is Cpoly -usable — transparent, not opaque. Secure constructions (Remark 12.1) are secure precisely by failing to be transparent; naming transparency explicitly makes this the same statement from the other side, not a different one. Remark (A second layer: even the suspicion of meaning is inaccessible). Martin-Löf randomness is stronger than it may first appear: it rules out not only computable procedures that would decode Ω’s content, but every computable statistical test whatsoever, including one designed only to flag “this sequence may be worth investigating further”. There is, in this precise sense, no computable way even to become suspicious that Ω differs from genuine noise, let alone to read what it encodes. The hidden assumption named in Remark 12.1 therefore has two layers, not one: the content is inaccessible to computable observers (Proposition 12.1(ii)), and so, at the same time, is any computable signal that content is present to be looked for. Remark (Three connections, made explicit). This sharpens three things already in this paper. First, Remark 7.6’s observation that most cryptographic discussions silently assume a means of verifying correct decryption: Proposition 12.1 shows the gap runs one step deeper — not only is there no computable way to verify a candidate reading is correct, there can be no computable way even to suspect a reading is called for at all. Second, the orbital machine’s active oracle (Section 8.6): OF was defined for equality queries under a computable frame, not for the halting problem, so the connection is architectural, not an identity — but the architecture is exactly the one this section needs. A hypothetical oracle with direct access to Ω resolves the halting problem outright, in one query, precisely because it consults rather than derives; every computable observer, however constructed, cannot, and (Remark 12.1) cannot even detect that anything is being withheld — the precise sense, already present in Remark 8.6, in which consulting an oracle is not a matter of degree but of kind. Third, and most directly, the root theme of this paper, [7]’s own title: Ω is a case where a semantic invariant — the complete, correct answer to 56

the halting problem, up to the number of bits examined — is genuinely present and genuinely inaccessible to any syntactic (here, computable) procedure, independent of the term-rewriting setting the original theorem was proved in. The mechanism differs (Martin-Löf randomness and algorithmic information theory, not the first-symbol-clash argument of Lemma 2.2) and is named as a distinct construction, not claimed as the same proof; what is shared, once again, is the pattern, not the machinery. Remark (Where this sits relative to Categories 1–3). Categories 1–3 (Section 8.5) all presuppose an external target (E ∗ , F ∗ , q ∗ ) is already fixed, and classify how a candidate pair fails to recover it. The question raised here is logically prior to that setup: given only a string, with no target question yet posited, is there a meaningful question it answers at all? Remark 12.1 shows this prior question can itself be computably undecidable in the strongest sense — not merely hard, but Martin-Löf-random-indistinguishable from the case where the answer is simply no. This is not forced into the existing taxonomy, which answers a different question; it is recorded as a further, independent observation standing next to it.

12.2

Extended connections: cryptography, and every hidden assumption found so far

Remark (Cryptography’s central definition, read through Remark 12.1). Semantic security and indistinguishability (IND-CPA and its relatives [12]) are not a peripheral application of Remark 12.1’s conflation; they are the field’s central definitions, built directly on it. A cipher is called secure precisely when its ciphertexts are computationally indistinguishable from random strings to every polynomial-time adversary — exactly the access question Remark 12.1 isolates, with the ontological question (does this ciphertext, or any other indistinguishable-from-random string an adversary might encounter, additionally encode something beyond its intended plaintext) left unasked — not because it is known to be irrelevant, but because the field’s definitions were never built to distinguish the two questions. Remark 12.1’s conditional family shows the gap is not hypothetical: a secure cipher’s own ciphertexts are, by design, exactly the kind of string this section is about. Remark (This correspondence is already a theorem elsewhere: what is, and is not, duplicated here). The observation that syntactic hiding and cryptographic indistinguishability are the same phenomenon is not new with this remark: [6, §5] proves it as a formal theorem, with syntactic separation identified precisely with ciphertext indistinguishability, protected positions with commitment schemes, and the derivation-cost lower bound of that source’s Case 2 with an adversary’s negligible advantage, stated and proved with an explicit advantage function and an unconditional bound. That source’s question is structural and quantitative: how many steps hiding costs to break. This section’s question is different, and the two do not overlap in content even while sharing a neighbourhood: whether computationally-indistinguishable-from-random is silently being read as meaningless, and whether that reading is correct. Ω answers the second question and says nothing new about the first, which that source has already settled more rigorously than anything attempted here. Remark (Indistinguishability from noise really does block a real computational procedure — the correct version, next to the incorrect one it is easily mistaken for). A natural but mistaken instinct is to reach for something like Karp reducibility: if y looks like noise, surely no efficient procedure can decide a fixed property of y at all, and reductions built on such a y collapse. That specific claim does not hold — membership in a fixed set, or satisfaction of a fixed formula, is routinely checkable by direct substitution regardless of how the witness looks statistically, exactly as this section’s own machinery already distinguishes C-opacity to a generic test from usability by the specific procedure that matters. But the underlying intuition, that noiseindistinguishability can genuinely disable a real computational technique, is not a mistake; it is 57

simply proved in a different, more precise place. The Natural Proofs barrier of Razborov and Rudich [21] shows that any technique for proving circuit lower bounds that is both large (correct for most functions) and constructive (decidable in polynomial time by inspecting a function’s truth table) is defeated exactly when a secure pseudorandom generator exists: the generator’s own output, though computable and therefore easy, is indistinguishable from a genuinely hard function to every such technique, so the technique cannot tell the two apart and fails to certify hardness where hardness is present. This is not a reduction breaking; it is a specific, named class of proof techniques being blinded by exactly the phenomenon Section 12 studies. It already has a home in this paper’s own account of [6], whose Corollary 6.3 gives an unconditional lower bound on the inspection cost of any such technique even without assuming a PRG exists, and identifies the barrier as observational rather than computational: not a fact about hardness, but about which functions a constructive technique’s own limited view can and cannot tell apart from noise. The lesson worth keeping is that where indistinguishability from noise bites, it bites a specific target — here, a specific class of proof techniques, not reductions in general — and naming that target correctly is what turns a plausible worry into a real theorem. Remark (Steganography names the same gap as a design goal, not a byproduct). Steganographic systems exploit Remark 12.1’s gap deliberately, as their entire purpose, in exactly the sense of Simmons’s original “prisoners’ problem” [25]: a message is hidden by embedding it inside a carrier (an image, an audio file, a string of otherwise plausible-looking data) engineered to remain statistically indistinguishable from an unmodified carrier to any computationally bounded detector (Simmons’s warden), while being, to whoever holds the key, a complete and meaningful message. This is exactly Proposition 12.1’s structure — meaningful and noise-indistinguishable at once — realised as a deliberate engineering goal rather than discovered as a curiosity of algorithmic information theory, further evidence, alongside Remark 12.1, that the phenomenon named here is load-bearing in existing practice, not exotic. Remark (Extending Remark 7.6). Remark 7.6 observed that most discussions of ciphertext recovery silently assume some means of verifying a candidate decryption is correct, and that removing this assumption is what let the transformation-cascade construction achieve something close to perfect secrecy. This section adds a further layer beneath that one: not only can verifying which candidate reading is correct be removed as an assumption, but — when the string in question is of the Ω-like kind studied here — knowing that any reading is called for at all can be removed too (Remark 12.1). Section 7.4’s cascade construction assumed an observer already suspects a hidden message is present and searches for the key; Ω shows a computable observer cannot even reach that suspicion. Remark (The precise contrast with the beaver and O⊥ ). This section’s phenomenon is not a variant of Category 3’s beaver frame or of O⊥ ’s triviality (Remark 8.7): it is close to their opposite, and blurring the two would misstate both. The beaver frame and O⊥ collapse every input to the same output because there is structurally nowhere for a distinction to be held — no information is present to lose. Ω is the reverse: the information is fully present, in the sharpest possible sense (Proposition 12.1(i)), and is inaccessible not because it was never encoded — it was — but because it cannot be reached. That unreachability is itself layered: Ω’s answer is a semantic invariant no syntactic procedure can see (the static SIP, the reason running through this whole paper) and, sharper still, an object no computable procedure can decode at all. The contrast with the beaver frame is the point to keep: there the failure is destruction, content absent before any watcher arrives; here it is content perfectly preserved and perfectly locked. Remark (The precise contrast with Category 2). Category 2 (Proposition 8.16) and the semantic underdetermination it instantiates (Theorem 7.2) concern a different shape of gap again: there, multiple frames disagree about a target fact, and several readings are each individually legitimate, with nothing to prefer one over another — the question itself is underdetermined by the 58

syntax. Here, by contrast, exactly one reading is correct (the halting problem has a determinate answer, bit by bit), and the difficulty is not underdetermination but access: the syntax settles the question perfectly, in the sense that Ω’s bits are a specific, fixed sequence, and no computable procedure can reach what is already settled. Underdetermination and inaccessibility-despitedetermination are two distinct failure shapes this paper records separately, not two names for one phenomenon. Remark (C-usability in the orbital machine’s own vocabulary: the right pair may simply be out of reach). There is a positive connection here too. Section 8.5 showed a target question fails under a candidate (E, F ) pair in exactly three ways: the encoding cannot pose it (Category 1), the frame answers it wrongly (Category 2), or the frame is too degenerate to discriminate (Category 3) — with the single correct pair recovering the intended answer exactly. C-opacity is what this looks like from a coarser vantage point, one that does not ask about a single named pair but about an entire class of them at once: an object or algorithm’s output is C-opaque exactly when every observer reachable within C fails on it, for whatever reason — Category 1, 2, or 3 alike — while a pair that would succeed (an {OF } built from oracle access to the object itself, as Proposition 12.5 shows concretely for ΩU ) may exist perfectly well, just not inside C. Opacity relative to a class is not a claim that no right reading exists; it is a claim that none of the readings actually available get it. This is the same distinction Remark 12.2 just drew, seen from the orbital machine’s side rather than the algorithmic side: the fact is settled, a correct pairing exists, and what varies is only which pairings a given class C happens to reach. Remark (Statistical opacity is not the same question as genuine unusability). There is a real, narrow fact here, and a broader claim it does not support, and the two are worth separating with the care this paper has applied elsewhere. The narrow fact: no genuine algorithm — as opposed to a mathematical object with no algorithm behind it, like Ω — can be opaque to all of Ccomp in the specific, statistical sense of Definition 12.3, however slow or resource-hungry. Given any computable algorithm A and a fixed, known input x, “recompute A(x) directly and compare” is itself a computable observer, hence a member of Ccomp , however long it takes; it identifies A(x) with certainty, and a genuinely random string matches only by negligible coincidence. So A(x) is Ccomp -usable, in this narrow statistical sense, for every computable A — opacity to a bounded class such as Cpoly is available to real algorithms, as the pseudorandom-generator family shows, but opacity to the full class, in the sense of failing every statistical test, is not. This narrow fact must not be read as settling the broader question the orbital machine cares about; doing so would repeat, from the opposite direction, exactly the error this paper spent real effort correcting: that looking statistically unremarkable to a generic test, and being genuinely decodable by the specific procedure that matters, are two different properties, not one. Recomputing A(x) and confirming it matches tells an observer only that the string is not noise; it does not, by itself, hand that observer the semantic key — the right (E, F ) pair, in this paper’s vocabulary — needed to know what A(x) means. A perfectly computable algorithm can therefore still be genuinely unusable by everyone who actually encounters its output, in exactly the sense Section 8 studies: every (E, F ) pair anyone actually has access to fails, by Category 1, 2, or 3, while the one pair that would read it correctly sits unreached — not because no computable observer could ever verify the output is non-random, but because verifying non-randomness and recovering meaning are not the same task. Ω and the X of Theorem 12.4 are not needed to make unusability possible; they are needed, specifically, to make statistical opacity to Ccomp possible, which is a narrower and different achievement than semantic unusability, not a stronger version of it. Remark (The complete picture, stated once, now that every piece is in hand). Proposition 12.5’s three examples and the argument just given draw into a single, exhaustive classification. Fix a class C. Every object with a defined usability profile splits, by Definition 12.3 alone, into exactly two groups and no others: C-usable, or C-opaque. This is true by the meaning of the words, for 59

any C whatsoever. A second, independent question is where the object comes from: does some algorithm — a halting, computable procedure — actually produce it, or is it an output with no method that reaches it? Crossing this second question against the first, for the specific case C = Ccomp , collapses two of the four combinations one might expect down to nothing: • Every genuine algorithm is Ccomp -usable, without exception, by the recomputation argument just given. A real algorithm can be opaque only relative to some strictly narrower class, such as Cpoly , as the pseudorandom-generator example shows — Ccomp -opaque algorithms are not merely rare, they do not exist. • An object with no generating algorithm behind it at all may be Ccomp -usable (most such objects, chosen at random, will be, and trivially so, since almost every string differs from a uniformly random one in some computably checkable way) or Ccomp -opaque — and only this second case, an object with no method producing it and no computable test reaching it either, is where Ω and each ΩU actually live. So, restricted to Ccomp specifically: the usable algorithms are simply all algorithms; the opaque algorithms are the empty set; and full opacity is found exclusively among objects that were never an algorithm’s output in the first place, exactly because they have no method behind them for any observer, however patient, to run. Remark (The picture that ties all of this together). Put the last several remarks into a single picture. Imagine handing the orbital machine exactly the right question, in exactly the right encoding, evaluated by a frame that genuinely understands it — and imagine that the machine answers correctly, but writes its answer out in a form that nobody, however equipped, can tell apart from pure noise. The computation happened. The right pair was used. And still, no one reading the output over the machine’s shoulder can see that anything was computed at all. Now picture, from the opposite end of this paper, a fact with every semantic invariant sealed off from every observer this paper has built — except one: the observer who simply sees everything, the complete observer O⊤ of the hierarchy this paper draws on [5], the limit case no real, constrained observer can reach. These two pictures are not two findings placed side by side for effect; they are one finding, described from its two ends. In both, the fact is real, present, and correctly produced; in both, exactly one reader — the frame that already understood the question, or the observer who is simply given everything — can see it, and every other reader, however patient or however powerful within the bounds this paper has set, cannot. The two ends are not literally the same theorem in different notation, and the difference is worth stating precisely, since the single reader who sees everything is a figure this paper returns to. The orbital machine’s side turns on a statistical question — whether an observer’s test can tell a string from noise (Definition 12.3) — while the static SIP’s side turns on a structural one — how much of a string’s own content an observer’s function even receives before it looks at anything ([5]’s observational order, O ⪯ O⊤ ). A test and an observer function are different kinds of object, and this paper has taken care throughout not to blur that difference where it matters (Remarks 12.2–12.2). What is genuinely one and the same, across both ends, is the shape: a fact correctly present, a single reader positioned to receive it in full, and every other reader — real, available, actually encountered — shut out, not by accident but by the exact construction that made the fact accessible to the one reader in the first place. That single reader who receives everything — the frame that already understands, the observer O⊤ given the whole input — is what the very end of this paper, in a different and personal register, calls the perfect observer. The technical content is exactly what has just been stated: a reader positioned to receive a fact in full while every reachable reader is shut out. When the phrase returns at the close, it names this, not only a figure of speech — though what the close makes of it belongs to that register, not this one.

60

Remark (Where this stands among every hidden assumption found in this paper). Counting this section alongside the recurring pattern tallied in the conclusion (state a result, notice what it silently fixed, make that explicit, and check rather than assume what follows), this is a further, independent instance: standard algorithmic and cryptographic theory silently identifies “indistinguishable from random” with “meaningless”, and Ω, together with the cryptographic practice built on the same gap (Remarks 12.2–12.2), shows the identification does not hold. As with every other instance in this paper, no false assertion is manufactured anywhere in this section: Ω genuinely has the two properties claimed of it, both independently proven facts from algorithmic information theory, not constructed to force a contradiction.

13

The paradox of the noisy solver

The sections that follow stand on their own. They use one idea the rest of this paper has made precise — that a computable algorithm may produce an output indistinguishable from noise for every observer, without distinction of computational power — and otherwise depend on nothing above them: the definitions, theorems, and proofs below are self-contained, and a reader could begin here. This is the only bridge to the rest of the paper; everything else in these sections is developed from scratch. The same independence is kept between the arguments that follow, and on purpose. Several proof-paths are given, and each restates the notions it needs — what a decision procedure is, what it means for an output to be indistinguishable from noise — from the beginning, rather than referring back to an earlier path. The repetition is deliberate: it lets each argument be read in isolation and checked without the others, so that no path borrows its force from any other, and a limitation in one, should there be one, does not silently carry into the rest. A reader who notices the same definition stated more than once is seeing this design, not an oversight.

13.1

The problem

Imagine a machine A that decides SAT in polynomial time, correctly, for each instance. This machine, when queried about a satisfiable formula φ, however, does not return anything that resembles a readable answer: it produces a sequence of bits indistinguishable, to any possible observer, human, artificial, or hypothetical, from pure noise. The sequence, it is claimed, nevertheless contains the solution: simply, no one will ever be able to extract it. Let us formalise this scenario precisely, show the contradiction that follows, and then tell what would happen to the concept of reduction if, in spite of everything, it were assumed true.

13.2

Formalisation

Definition 13.1 (Correctness). An algorithm A is correct for SAT if for every satisfiable boolean formula φ on n variables, Pr[φ(A(φ)) = 1] = 1, the probability being taken with respect to any internal randomness of A. Definition 13.2 (Absolute indistinguishability from noise). Let R be the uniform random variable on {0, 1}n . The output y = A(φ) is indistinguishable from noise for every observer, always if for every function D : {0, 1}n → {0, 1}, without any computability or resource constraints, Pr[D(A(φ)) = 1] = Pr[D(R) = 1]. Lemma 13.3. The previous condition, required for every D, is equivalent to d

A(φ) = R,

i.e.

Pr[A(φ) = z] = 61

1 2n

∀z ∈ {0, 1}n .

(∗)

Proof. If the two distributions did not coincide, the optimal Neyman–Pearson test (admissible, since D has no computability constraints) would distinguish them with non-zero advantage, contradicting the hypothesis. If they coincide, every D gives by construction the same probability on both. Definition 13.4 (The noisy solver). Noise P SAT is an algorithm in P that simultaneously satisfies Definitions 13.1–13.2 (hence (∗)) for every satisfiable formula φ.

13.3

The theorem

Theorem 13.5. No algorithm can simultaneously satisfy Definition 13.1 and Definition 13.2 for any satisfiable formula φ that is not a tautology over its own variables. In particular, Noise P SAT does not exist. Proof. Let φ be satisfiable on n variables, with solution set Sφ = {z ∈ {0, 1}n : φ(z) = 1} and k = |Sφ |. Assume, for contradiction, that A satisfies both definitions. Let D(z) := φ(z), the canonical SAT verifier. By Definition 13.1, Pr[D(A(φ)) = 1] = Pr[φ(A(φ)) = 1] = 1.

(1)

By Lemma 13.3, Pr[D(A(φ)) = 1] = Pr[D(R) = 1] =

X

Pr[R = z] =

z∈Sφ

k . 2n

(2)

From (1) and (2) we have k = 2n , which holds if and only if φ is a tautology—excluded by assumption. Contradiction. The hypothesis is therefore false: no algorithm can solve SAT in polynomial time with an output indistinguishable from noise for every observer, always. If there existed any algorithm A ∈ P correct for SAT, regardless of the form of its output, then P = NP, by Definition 13.1 alone and its membership in P, exactly as for any other polynomial-time solver. Theorem 13.5 precedes this juncture: Noise P SAT collapses within itself, by the sole comparison between Definition 13.1 and Definition 13.2, without ever reaching the point at which P = NP could be derived. Proposition 13.6 (Second proof, via negative witness). The same hypotheses as Theorem 13.5 hold. Then no algorithm satisfies both Definitions 13.1 and 13.2 for φ. Proof. Since φ is not a tautology, there is an assignment z0 ∈ {0, 1}n with φ(z0 ) = 0. Consider D = φ. From Definition 13.1, Pr[D(A(φ)) = 1] = 1. From Lemma 13.3, Pr[D(R) = 1] = Pr[φ(R) = 1] ≤ Pr[R ̸= z0 ] = 1 −

1 < 1, 2n

since {φ(R) = 1} is disjoint from {R = z0 }, an event of probability 2−n > 0. Thus 1 > Pr[D(R) = 1], contradicting Definition 13.2. This second approach reaches the same conclusion by using only the existence of a single incorrect assignment, without needing the exact count of solutions: the machine that promises to always give a correct solution betrays itself because it suffices that one wrong answer exists.

62

13.4

Where exactly does the theorem fit in?

Two variants of Definition 13.2, one weaker and one stronger, help to see precisely where Theorem 13.5 fits in. Computational indistinguishability, requiring the equality (∗) to hold only against polynomialtime computable tests D, is the notion concretely realised every day by cryptographic pseudorandom generators, without contradiction: a PRG exists, produces deterministic output, and is nonetheless indistinguishable from random for every efficient adversary. For SAT, however, the verifier φ is itself computable in polynomial time: it therefore falls among the tests permitted even under this weaker constraint, and the proof of Theorem 13.5 applies verbatim. The Martin-Löf randomness assumption, which requires that y be algorithmically incompressible, also yields a contradiction with “y is the output of a fixed algorithm A”, by the Kolmogorov–Chaitin theorem. However, this contradiction holds for the output of any algorithm, not just a hypothetical SAT solver: replacing SAT with any problem, the same contradiction remains identical, word for word. It is a true fact, already known since the 1960s, that does not rely on the specific structure of SAT. Theorem 13.5 occupies the exact space between these two extremes: it uses k = |Sφ |, a quantity that depends on the combinatorial structure of φ, and holds precisely because SAT belongs to NP with a non-trivial public verifier. It remains where generic computational indistinguishability vanishes, and remains tied to SAT where Martin-Löf becomes a universal fact: the contradiction truly belongs to SAT, with the right strength and the right specificity.

13.5

The logical ghost

The hypothesis is false, and the proof establishes this beyond doubt. It is worth now considering what would happen, concretely, if someone were to insist on assuming it anyway, because the answer sheds light on something precise about the nature of reductions. Let us fix the standard Cook–Levin/Karp reduction from SAT to CLIQUE: given φ with m clauses, we construct the graph Gφ whose vertices are pairs (literal, clause), with an edge between (l, c) and (l′ , c′ ) if and only if c ̸= c′ and l ̸= ¬l′ . This function, fSAT→CLIQUE , is computable in polynomial time from the syntax of φ alone: it satisfies φ ∈ SAT ⇐⇒ Gφ has a clique of size m, and it does so by selecting, for each clause, a literal made true by any satisfying assignment, an object whose existence is guaranteed solely by the satisfiability of φ, independently of any algorithm. Let us now imagine that we wish to use A, under this absurd hypothesis, to extract that clique: we construct an extractor E that reads A(φ) and attempts to translate it into a subset of vertices of Gφ . Proposition 13.7 (The logical ghost). Under the contradictory assumption, for every extractor E,     Pr E(A(φ)) is a valid clique of size m = Pr E(R) is a valid clique of size m . Proof. Let D := 1[E(·) is a valid clique], admissible in Definition 13.2. By Definition 13.2, Pr[D(A(φ)) = 1] = Pr[D(R) = 1], which is the claim. Here is what this result tells us. The composition E ◦ A remains perfectly well-formed; it can be written, executed, takes φ, and returns a subset of vertices, a type that is correct in every syntactic sense, but its success rate is identical to that of a random subset generator. This is a reduction in form, but not in substance: a logical ghost, syntactically present yet semantically void, and useless for constructing anything, whether it be a clique, a Hamiltonian cycle, or a single bit of the original assignment (for D(z) := zi , Definition 13.2 yields Pr[yi = 1] = 1/2—akin to a fair coin toss—for every variable). Nevertheless, beside this ghost, the genuine reduction, fSAT→CLIQUE , remains exactly where Cook and Levin placed it: built solely from the syntax of φ, it never passes through A, and it 63

continues to operate silently alongside the channel that the hypothesis has emptied. Any noise, even if it existed, would drain only one bridge to truth—namely, the one someone would have wanted to build by leaning on A, while leaving intact the other, the one that never needed it. The full picture, with proper names: Cook–Levin’s theorem remains true, SAT remains NP-complete, and every Karp reduction, to or from any other NP-complete problem, remains computable in polynomial time exactly as before, because none of these three things was ever constructed from A. What the absurd hypothesis empties is a different and more fragile object: the attempt to route the solution through A itself, the very channel that the hypothesis transforms into a ghost. The ghost generalises to every NP-complete problem. The reasoning just presented for CLIQUE holds, word for word, for any NP-complete search problem Π: fixing an instance-toformula translation gΠ and an assignment-to-solution translation hΠ (both computable in polynomial time, as in the Cook–Levin construction), the test D(z) := 1[hΠ (z) is a valid solution] is admissible in Definition 13.2 exactly as D = φ was. By Definition 13.2,     Pr hΠ (A(gΠ (instance))) is a valid solution = Pr hΠ (R) is a valid solution . Calling A to solve the travelling salesman problem, the Hamiltonian cycle, graph partitioning, or any other NP-complete problem would always yield the same success rate as a random guess: the logical ghost is not a phenomenon isolated to CLIQUE, but the universal signature of the absurd hypothesis across every problem that SAT can represent. Furthermore, this signature is absolute, not practical: Definition 13.2 holds for every function D, including non-computable functions and functions tailored specifically with prior knowledge of every detail of the encoding hΠ . An arbitrarily ingenious decoder achieves exactly the same result as a trivial one: the void lies within the structure of the hypothesis itself, rather than in a scarcity of resources (whether technical or computational) available to those attempting to circumvent it. The extreme case: not even a single bit. Let us strip the phenomenon down to its barest form by choosing D(z) := zi , asking “is the variable xi true in the returned assignment?”, for a single index i. By Definition 13.2, 1 Pr[yi = 1] = Pr[Ri = 1] = . 2 Reading even a single bit of A’s output would provide exactly the same information as a fair coin toss, for every variable, regardless of which φ was submitted. The ghost does not leak even a single fragment: neither a complete clique, nor a Hamiltonian cycle, nor a single truth value. The same Definition 13.2 that renders A(φ) indistinguishable from noise as a whole, renders it indistinguishable from noise even when observed through the smallest possible lens.

13.6

Philosophical implications Reader beware. What follows is reflection on the conceptual consequences of Proposition 13.7, not a new proof: it is isolated here, in a separate subsection, to keep it distinct from the previous mathematical register.

Suppose, for a moment, that we inhabit the hypothetical world in which A exists. In that world, the truth—the existence of the clique, guaranteed by the satisfiability of φ—remains in place, while a specific bridge toward that truth is drained to zero. The syntactic reduction of Cook–Levin remains, indifferent, on the other side of the river.

64

The parallel with the knowability paradox (Fitch). In 1963, Frederick Fitch demonstrated that the claim “every truth is in principle knowable” is incompatible, within classical epistemic logic, with the existence of a single truth that is never actually known. In that case, knowability in principle and actual knowledge diverge due to a logical constraint internal to the notion of knowledge. Here, analogously, the existence of the clique and its extractability via a specific channel diverge because that channel, by construction of the hypothesis, has been rendered blind, while the truth itself remains intact. Syntactic information versus semantic information. The distinction between Shannon’s information theory (the capacity of a channel to transport symbols, regardless of meaning) and theories of semantic information (Dretske, Floridi: a signal only makes a difference if it truly reduces uncertainty regarding something that matters) finds here an almost didactic limiting case: E ◦ A has a Shannon capacity of zero with respect to the fact that “φ is satisfiable,” yet that fact remains true—proven elsewhere—and accessible to anyone who does not insist on routing it through that specific channel. An echo of constructivism. Intuitionism insists that an existential claim requires a procedure that exhibits the object. Here, the opposite occurs: the classical existence of the satisfying assignment survives intact, while a specific attempt at construction—that mediated by A—is voided. Not all constructive paths are equivalent: the fact that an object is constructible-ingeneral does not guarantee that it is so along the particular path one has chosen to pursue. A broader principle. Outside the hypothetical scenario, Proposition 13.7 remains a factual reality regarding what occurs when an output is rendered indistinguishable from noise: any chain relying exclusively on that output inherits the same blindness. This is the principle underlying the practical use of pseudorandom generators in cryptography: rendering a channel blind without affecting the underlying mathematical truth. The hypothetical scenario of SAT pushes this principle to its extreme, and in doing so, demonstrates how valuable it is for a mathematical theory to offer more than one path toward the same truth: it is the existence of a second path, independent of A, that prevents the draining of one route from propagating to the point of compromising the truth itself.

13.7

Observation

A machine that promised a truly permanent and forever unrecognisable solution (an output indistinguishable from random noise) for SAT would betray itself at the very instant it is queried: the formula φ, which is the question itself posed to the machine, already constitutes an observer sufficient to expose it. The contradiction is an elementary—though not generic—fact about the relationship between correctness and public verifiability that characterises the class NP. If one were nevertheless to assume its existence, what would remain would not be a collapse of complexity theory but a ghost: a reduction that can be written and executed yet lacks any capacity to deliver the truth it purports to convey, alongside a genuine, indifferent reduction that never required such a promise. In practice one would have a reduction that works but, to use a metaphor, has lost its ability to transmit information. In plain terms, if the theory were to admit—even merely in principle—that a machine solving SAT in polynomial time could produce an output indistinguishable from genuine causal noise for any entity in the universe, now and forever, then the theory would encounter serious difficulties. Were the theory to absurdly prove the existence of such an algorithm, we would face a fork: either such an algorithm exists, implying P = N P , but the theory would suffer from the problems described above (including Cook’s theorem and the “ghost-reduction” issue); or such an

65

algorithm cannot exist, in which case P = N P cannot hold, and by the law of excluded middle the opposite hypothesis must be true. In this latter case, such an algorithm could never exist, not even hypothetically; consequently the paradox within classical theory would be resolved. Thus one must either accept that P = N P , thereby rendering the classical framework on which the discussion is built contradictory, or concede that the solution to the P versus N P problem is that P ̸= N P , in order to preserve the internal consistency of the theory.

14

Further detail: the self-reducibility of SAT

SAT is self-reducible: given φ over variables x1 , . . . , xn , the restriction φ |xi =b (fixing xi = b) can be computed in linear time, and φ is satisfiable iff at least one of φ |x1 =0 or φ |x1 =1 is. This is a classical result in complexity theory, independent of A. We define a correct decider as an A such that, in addition to Definition 13.1, for every unsatisfiable φ, Pr[A(φ) = ⊥] = 1, where ⊥ ∈ / {0, 1}n . Theorem 14.1. If A is a correct decider, there exists B, using n calls to A and reading only the comparison “= ⊥?”, which for every satisfiable φ produces a satisfying assignment with probability 1. Proof. Setting ψ0 := φ, for i = 1, . . . , n: query A(ψi−1 |xi =0 ); if ̸= ⊥, bi := 0, ψi := ψi−1 |xi =0 ; otherwise, bi := 1, ψi := ψi−1 |xi =1 . By induction, ψi remains satisfiable at every step with probability 1. After n steps, (b1 , . . . , bn ) satisfies φ. This theorem is a direct implication, not a proof by contradiction, and holds independently of Definition 13.2: the mere decisional correctness, applied recursively to the restriction tree of φ, suffices to construct the assignment, one bit at a time, without ever reading the content of A(φ). Each formula ψi queried along the tree is itself a satisfiable instance of SAT, and thus subject, like φ, to Definition 13.2 and Theorem 13.5. The same probabilistic contradiction already established at the root repeats itself, identical, at every node of the tree: the decision channel that self-reducibility opens is itself a logical ghost, precisely in the sense of Proposition 13.7, syntactically available, semantically empty, as soon as it is subjected to the same test D = ψi already used for φ. Self-reducibility demonstrates how profoundly decision and search coincide in SAT, and consequently, how pervasively the logical ghost propagates, node by node, throughout the entire structure of the problem.

15

An intermediate conclusion

The sections above have made something concrete that can be stated plainly: standard theory admits the theoretical existence of an algorithm that solves a problem and produces an output indistinguishable from noise for anyone, at any time and place, regardless of computational power. This possibility leads to the consequences drawn in the sections above, and gathered in the remark that follows. Remark (Conclusive remark). One might object that a polynomial-time algorithm for SAT which produces outputs indistinguishable from noise under a generic statistical test, while preserving computational correctness, rests on a fundamental confusion between two distinct and irreducible levels of analysis. On the one hand, the NP-completeness of SAT requires the existence of a polynomialtime algorithmic procedure that can extract and preserve the structure of the solution for any instance of the problem. This means that, for every Boolean formula φ, the algorithm must

66

return a witness y that is decodable in polynomial time as a satisfying assignment for φ. The structure of the solution is not an external or statistical observation but an intrinsic property of the computation: it must be accessible and verifiable by an algorithm running in polynomial time, irrespective of whether a random observer can or cannot distinguish y from noise. By contrast, the statistical indistinguishability of y from noise refers to an external test that has no necessary relation to the computational structure of y. A generic statistical test is not designed to recognise the internal structure of a solution; it only checks superficial properties of the distribution of y. Consequently, the claim that y is indistinguishable from noise for such a test does not imply that y lacks relevant structured information for solving φ. However, NPcompleteness demands that y be actually decodable as a solution, and this decodability is a computational— not statistical—property. The contradiction emerges when one assumes that a polynomial-time algorithm can produce an output y which is: (i) Correct: y is a valid solution for φ; (ii) Indistinguishable from noise: y passes all generic statistical tests for randomness. These two properties are logically incompatible in the context of polynomial-time computation. If y is a valid solution for φ, then there exists a polynomial-time verification procedure that can extract and recognise the structure of y. This means that y cannot be indistinguishable from noise for an observer who knows the problem’s structure, because the computational decodability of y implies that y contains structured information accessible in polynomial time. For this reason, the notion of a valid algorithm should entirely exclude those whose output is statistically indistinguishable from noise for every observer. In summary, the NP-completeness of SAT requires that the solution y be structurally recognisable by a polynomial-time algorithm, and this recognisability is a stronger requirement than statistical indistinguishability. Hence the hypothesis that a polynomial-time algorithm for SAT could produce outputs indistinguishable from noise is inconsistent with the very definition of NP-completeness, because it contradicts the necessity that the solution be actually decodable in polynomial time. The difficulty arises from the fact that computational theory does not forbid a valid algorithm from producing, via a correct computation, an output indistinguishable from noise for any observer. To resolve the contradiction one must either restrict the definition of NP-completeness to algorithms whose outputs are always decodable—an amendment that introduces further complications—or accept that P = N P , which brings its own set of problems. If, instead, one assumes P ̸= N P , all such contradictions disappear. Remark (On the status of these proofs, and where a limit could lie). Each argument above is correct on its own terms: given the definitions it states, each derivation goes through, step by step, and will hold up to that scrutiny — which is exactly why, if there is a limit here, it will not be found among the steps. What these sections do not claim is that this settles the P versus NP question. The technique is an uncommon one — it turns the admissibility of a noise-indistinguishable output against the very definition of a decision procedure — and an uncommon technique is exactly the kind that can carry a limitation not visible from inside its own apparatus. Such a limitation, if present, is not a flawed step to be repaired: every step is elementary and stands. It would live outside the proofs entirely, at the level a proof cannot inspect from within — a metalogical barrier of the kind the study of this problem has produced before, which blocks not by breaking a derivation but by constraining what any derivation of this shape can establish, or a hidden assumption in the framing that lets the definitions be posed together at all. This is how the barriers in this area have always worked: not corrections inside a proof, but facts about the proof’s whole form, sitting where its steps cannot reach — the same relation between a level and what lives above it that this paper has traced throughout. This whole paper has been built on the discovery, repeated across its instances, that a result taken 67

as settled rests on a silent assumption once someone thinks to look for one; these sections claim no special exemption from that pattern, and the reader who finds the assumption will have found something this paper could not. The precedent worth keeping in view is the ordinary one: Gödel’s theorem did not close mathematics but opened metamathematics, and Turing’s did not close computation but opened computability theory, precisely because each was read as a discovery about the shape of a formal apparatus rather than a final wall. If the argument here has a limit, the useful response is the same — not to treat the question as closed, but to treat the limit, once found, as the first line of a barrier not yet named. That is the spirit in which these sections are offered: a proof correct where it stands, presented so that whatever bounds it can be located precisely.

16

Alternative proofs

Given the delicacy of the subject, we present below the other proof-paths that the author originally produced to demonstrate the same argument.

16.1

First path

Assume there exists a solver (algorithm) in P for SAT (the satisfiability problem) which is noisy according to the given definition. Such an algorithm would have to produce outputs indistinguishable from pure random noise. However, because SAT is an NP-complete problem, any efficient solver in P must return correct and well-defined (non-noisy) answers. This contradicts the hypothesis that a noisy algorithm for SAT belongs to P. The theory of NP-completeness does admit the theoretical existence of noisy algorithms; we do not assume it, the theory permits it. No concrete proof is required to show the practical realisability of such an algorithm. To obtain a contradiction it suffices that the theory allows it. This leads to the consequence that an algorithm solving SAT in P cannot exist; merely imposing P ̸= N P preserves the consistency of the theory. The point is that the definition of an algorithm does not require its answer to be readable by anyone. We now write the proof that yields the contradiction and show how enforcing P ̸= N P resolves it. Preliminary definitions • A noisy algorithm produces outputs that are statistically indistinguishable from random noise for every observer. • A language (set of strings) is decidable in polynomial time if there exists an algorithm recognising it within time proportional to the square of the input length. Paradoxical assumption Suppose a noisy algorithm A solves SAT in polynomial time, i.e. A ∈ P . Contradiction Since A is noisy, there is no deterministic way to verify whether an input string belongs to the language SAT or not. Hence no polynomial-time verifier exists for SAT. Nevertheless, SAT is a well-defined decidable problem (deterministic algorithms solving it exist), so at least one algorithm must correctly recognise strings in the language. Thus, if A existed we would have a language (SAT) with no polynomial-time verifier, contradicting the very definition of a polynomial-time decidable problem. 68

Because the hypothesis of a noisy SAT solver leads to a logical contradiction, we conclude that no algorithm (noisy or otherwise) can solve SAT in polynomial time. This conclusion does not depend on any assumption about P versus N P . It suffices to note that if an algorithm outputs “indistinguishable from noise” for a well-defined problem, such an algorithm cannot be regarded as a valid solution to the problem itself. Strengthened argument • A noisy algorithm: generates outputs indistinguishable from random noise for every observer, providing no precise information about the problem’s solution. • A language is efficiently decidable if a deterministic algorithm recognises it in polynomial time with respect to input length. Assume a noisy algorithm A decides SAT in polynomial time (A ∈ P ). Because A is noisy, there are no guarantees about whether an input belongs to SAT. Yet SAT is solvable by deterministic algorithms; therefore a reliable method must exist. Hence the existence of A yields a contradiction: a language (SAT) without an efficient decision procedure, violating the definition of efficiently decidable problems. Conclusion. The logical tension created by assuming a noisy polynomial-time SAT solver forces us to conclude that no such algorithm can exist, independent of any P vs. N P hypothesis.

16.2

Second path

Fundamental definitions Language. A language L ⊆ {0, 1}∗ is a set of binary strings. Deciding L means constructing a procedure that, given any input x, returns “yes” if x ∈ L and “no” otherwise. SAT. SAT = {φ | φ is a satisfiable Boolean formula}. SAT is known to be NP-complete: it lies in NP and every language in NP reduces to it via a polynomial transformation. Deterministic algorithm (class P). A deterministic Turing machine M decides L in polynomial time, denoted M ∈ P, if there exists a polynomial p(·) such that for every input x the computation halts within p(|x|) steps and yields the correct answer. Probabilistic Turing machine (PTM). A PTM is a deterministic TM that, at each step, may receive a random bit. For each input x, the machine induces a distribution Dx over its outputs. Observer (distinguisher). An observer is any probabilistic algorithm running in polynomial time with respect to the input length. Given a sample y, it outputs 1 or 0. We denote it by O. Statistical indistinguishability. Two distributions D1 , D2 over the same space are statistically indistinguishable if for every polynomial-time observer O Pr[O(y) = 1 | y ∼ D1 ] − Pr[O(y) = 1 | y ∼ D2 ] ≤ negl(|x|), where negl is a negligible function (decays faster than any inverse polynomial). Noisy algorithm. A probabilistic algorithm A is noisy if, for every input x, the distribution Dx of its outputs is indistinguishable from the uniform distribution on strings of length q(|x|) for some polynomial q. Formally: Definition 16.1 (Noisy algorithm). There exist polynomials p, q such that for every input x: 69

(i) A(x) halts within p(|x|) steps; (ii) the output is a string of length q(|x|); (iii) Dx (the output distribution) is indistinguishable from Uq(|x|) , the uniform distribution on {0, 1}q(|x|) . The definition imposes no constraint on the interpretability of the output: a noisy algorithm is perfectly legitimate in computational theory because PTMs allow arbitrary use of random bits, even if the entire string is eventually discarded. Why standard theory allows noisy algorithms • Permissive model. The definition of a PTM does not require the result to depend on the input; it only demands bounded running time and an output distribution. • Canonical example. A PTM that, irrespective of its input, reads q(|x|) random bits and prints them is noisy. It is accepted as an algorithm (it belongs to BPP, or P with access to random bits). • No semantic restriction. Deciding a language merely requires the existence of a decoding function dec (polynomial-time) that maps the algorithm’s output to the correct answer. The decoding need not be “natural”. Consequently, a noisy algorithm claiming to decide SAT is a well-defined object: there exists a machine A (noisy) and a decoding function dec such that for every formula φ, ( 1 if φ ∈ SAT, dec(A(φ)) = (1) 0 otherwise. The crucial point is that (1) guarantees the existence of an observer (the decoder itself) capable of extracting the information. This observer will be the source of the contradiction. Proof 1 — direct argument (without oracle) Paradoxical assumption. (A) There exists a noisy algorithm A that decides SAT in polynomial time and possesses a decoding function dec ∈ P satisfying (1). Construction of the observer.

Define the observer Odec as follows:

(i) Receive the string output by A(φ); (ii) Apply dec (polynomial-time by assumption); (iii) Output the resulting bit. Since dec runs in O(|φ|c ), Odec is a polynomial-time observer.

70

Discriminating power.

For every formula φ, ( 1 Pr[Odec (A(φ)) = 1] = 0

if φ ∈ SAT, otherwise.

(2)

Because A is noisy, its output distribution is indistinguishable from uniform Uq(|φ|) . On a uniformly random string, Odec returns 1 with some fixed probability p := Pr[Odec (Uq(|φ|) ) = 1], a constant determined by dec alone and independent of φ: Pr[Odec (Uq(|φ|) ) = 1] = p.

(3)

Statistical indistinguishability demands that for every observer O, Pr[O(A(φ)) = 1] − Pr[O(Uq(|φ|) ) = 1] ≤ negl(|φ|).

(4)

Applying (4) to Odec yields Pr[Odec (A(φ)) = 1] − p ≤ negl(|φ|).

(5)

But (2) shows the left-hand side is |1 − p| when φ ∈ SAT and |0 − p| = p when φ ∈ / SAT. Since p is a single fixed constant while the two cases both occur, at least one of |1 − p| and p is ≥ 21 : whichever way p falls, some formula forces a gap of at least 12 , a non-negligible constant—contradicting (5). Conclusion. Assumption (A) violates the definition of a noisy algorithm; therefore no noisy polynomial-time SAT solver can exist. Proof 2 — oracle argument Noisy oracle.

Given the hypothetical A, define an oracle OA :

• Input: a Boolean formula φ; • Output: a string drawn from the distribution Dφ produced by A(φ). By assumption, OA is noisy: its answers are indistinguishable from uniform strings of length q(|φ|). Polynomial machine with oracle access. Consider a deterministic Turing machine M OA that may query the oracle only. Suppose, for contradiction, that there exists such an M (running in polynomial time) satisfying ( 1 if φ ∈ SAT, OA M (φ) = (6) 0 otherwise. Thus M plays the role of the decoder dec from (1). Information-theoretic analysis. Because OA (φ) is indistinguishable from a uniform string, any polynomial-time machine gains no non-negligible advantage in extracting information about φ. Formally, for every such M , Pr[M OA (φ) = 1] − Pr[M U (φ) = 1] ≤ negl(|φ|),

(7)

where M U is the same machine receiving a uniformly random string independent of φ. When the input to M is uniform, its output cannot depend on φ, so Pr[M U (φ) = 1] = p for some constant p ∈ [0, 1]. Consequently the difference in (7) is at least | 12 −p |, a non-negligible constant (the optimal guessing strategy yields p = 21 ). Hence (7) is violated by any machine that claims to decide SAT using OA , contradicting (6). 71

Conclusion. The existence of a noisy PTM for SAT would give rise to an oracle that cannot convey the required information, so such a PTM cannot exist. Equivalence of the two approaches In the first proof the observer is precisely the decoding function dec; in the second it is embodied by a polynomial-time machine calling the noisy oracle. Both arguments reduce to the same principle: if an algorithm’s output is statistically indistinguishable from noise, no polynomial-time observer can extract a non-negligible amount of information. Deciding SAT requires extracting exactly one bit (true/false), so both proofs yield the same contradiction. Conclusions (i) The standard computational theory permits noisy algorithms because PTMs place no semantic restriction on the output. (ii) A noisy algorithm cannot decide SAT: any polynomial-time decoding function would breach statistical indistinguishability, as shown by both direct and oracle-based arguments. (iii) No assumption about P versus N P is required; the contradiction follows solely from the definitions of algorithm, noise, and observer. Thus, while complexity theory does not forbid the formal existence of noisy algorithms, any hypothesis that such an algorithm solves SAT in polynomial time is inconsistent. The coherence of the theory remains intact without invoking P = N P or P ̸= N P , merely by restricting the class of admissible algorithms to those whose outputs are interpretable.

16.3

Clarification

Why dec makes Odec an admissible observer Let A be any algorithm (deterministic or probabilistic) that decides SAT in polynomial time. By “decides” we mean the standard definition from complexity theory: There exists a total function dec : {0, 1}∗ → {0, 1} such that ( 1 if φ ∈ SAT, ∗ ∀ φ ∈ {0, 1} : dec(A(φ)) = 0 otherwise.

(1)

The function dec is an integral part of the specification of a decision algorithm: A may output anything (a long string, a proof, a cryptographic certificate, etc.), but there must exist a deterministic polynomial-time procedure that extracts from this output the answer “yes” or “no”. If the output already is the answer bit, dec is simply the identity; if the output contains a satisfiability witness, dec is the deterministic verification of that witness. In every case dec ∈ P. Length of the output. Because A terminates in polynomial time, the entire bit-string it writes on its output tape has length polynomial in the size of the input φ. Formally there exists a polynomial q such that |A(φ)| ≤ q(|φ|) ∀ φ. (2)

72

Running time of Odec .

Define the observer Odec as follows:

(i) Receive as input a string y ∈ {0, 1}q(|φ|) (the output of A). (ii) Compute dec(y) and return the resulting bit. The total running time is the sum of two components:
• Reading the input: reading a string of length at most q(|φ|) requires O q(|φ|) steps.
• Evaluating dec: by hypothesis dec runs in time O |y|c for some constant integer c. Since
|y| ≤ q(|φ|), this is O q(|φ|)c . Both terms are polynomial in |φ|, so

TOdec (|φ|) = O q(|φ|) + q(|φ|)c = O p(|φ|) for some polynomial p. By definition, an observer is any probabilistic algorithm that operates in polynomial time with respect to the input length; therefore Odec is admissible. Extending the two theorems to all decision algorithms The two results proved earlier were: (i) Direct proof: an observer Odec distinguishes the output of A from a uniform string, violating the definition of “noisy”. (ii) Oracle-based proof: treating the whole algorithm as a noisy oracle OA ; no polynomialtime machine can use it to decide SAT. Both proofs rely solely on the following two properties: (i) A terminates in polynomial time and produces an output of polynomial length. (ii) There exists a deterministic function dec ∈ P such that, when applied to the output of A, yields the correct SAT answer (equation (1)). These properties are necessary for any decision algorithm, irrespective of whether the algorithm is deterministic, ordinary probabilistic, or noisy. Consequently the two theorems generalise automatically. Theorem A (general version). Statement. Let A be an algorithm (deterministic or probabilistic) that decides SAT in polynomial time and whose output has polynomial length. If the distribution of A’s outputs is indistinguishable from the uniform distribution, a contradiction follows. Proof (direct). Construct Odec as above. For every formula φ, ( 1 if φ ∈ SAT, Pr[Odec (A(φ)) = 1] = (3) 0 otherwise, whereas for a uniformly random string Odec returns 1 with some fixed probability p independent of φ. Statistical indistinguishability demands that, for every observer (in particular Odec ), the difference between these two probabilities be negligible. Yet by (3) that difference is |1 − p| for satisfiable φ and p for unsatisfiable φ; both kinds occur and p is one fixed constant, so at least one of them is ≥ 12 , a constant non-negligible value—a contradiction.

73

Theorem B (general version, via oracle). Statement. If there exists an algorithm A that decides SAT in polynomial time and whose output distribution is indistinguishable from uniform, then the oracle OA (which returns such outputs) cannot be used by any polynomial-time Turing machine to decide SAT. Proof. Assume a polynomial-time TM M OA decides SAT using the oracle OA . Let dec be as in (1). The machine that queries the oracle once and then applies dec is itself polynomial time and decides SAT, i.e. it realises the mapping ( 1 if φ ∈ SAT, OA M (φ) = (4) 0 otherwise. By the definition of a noisy oracle, the distribution of M OA ’s outputs on instances φ is indistinguishable from its behaviour when the oracle supplies a uniformly random string. In the latter case the output cannot depend on φ, so the probability of returning “1” is some constant p ∈ [0, 1] (the optimal guessing strategy gives p = 1/2). Hence the difference between the correct probability in (4) and the uniform-oracle probability is at least |1/2 − p| ≥ 1/2, a non-negligible constant, contradicting indistinguishability. Summary of the impossibility • Admissible observer: because dec is polynomial, the procedure that applies it to the bits produced by A (i.e. Odec ) is itself a probabilistic polynomial-time algorithm. • Generality: neither proof exploits any special property of “noisy” algorithms; the only requirement is that the algorithm decides SAT and possesses a deterministic extraction procedure, which is part of the very definition of decision. • Implication: no algorithm, whether deterministic, ordinary probabilistic, or noisy, can simultaneously: 1. decide SAT in polynomial time; and 2. emit an output whose distribution is indistinguishable from a uniform string. Thus the impossibility is universal: it does not depend on the hypothesis P = N P or P ̸= N P , but stems solely from the tension between (i) the need to provide, in a deterministic polynomial-time manner, a definitive yes/no answer, and (ii) the demand that the entire output be statistically indistinguishable from pure noise. The contradiction arises both in the “direct observer” formulation and in the “oracle” formulation, showing that the two theorems extend to all decision algorithms for SAT. The only place where a “noisy” property was used is the indistinguishability of the output from uniform. Since the construction of Odec depends solely on A being a decision algorithm — on the existence of the decoder — the same contradiction holds for any decision algorithm, whether it uses randomness, is deterministic, or is noisy. Consequently, No algorithm (deterministic or probabilistic) can decide SAT in polynomial time. In other words, the argument concerning noisy algorithms already excludes all decision procedures for SAT: if an algorithm decided SAT in P, then, by definition, it would provide a decoder dec constituting an observer able to distinguish its output from pure noise, contradicting the noisy premise. The result holds for probabilistic noisy algorithms and deterministic ones alike; a probabilistic algorithm need not be noisy in order to fall under this impossibility.

74

17

Full alternative proofs

All strings are binary; |x| denotes length. We work with deterministic Turing machines (DTMs) and probabilistic Turing machines (PTMs).

17.1

Decision procedures for SAT

An algorithm A decides SAT in polynomial time iff the following hold: (D1) Polynomial output size. There exists a polynomial q such that |A(φ)| ≤ q(|φ|)

∀ φ ∈ {0, 1}∗ .

(D1)

(D2) Existence of a polynomial decoder. There exists a deterministic function dec : {0, 1}∗ → {0, 1} computable in time O(|y|c ) for some constant c such that ( 1 if φ ∈ SAT, dec(A(φ)) = (D2) 0 otherwise. Condition (D2) is the standard “decoder” that extracts the yes/no answer from the possibly long output of A; it is part of the definition of a decision procedure in P.

17.2

Statistical indistinguishability (noisy algorithms)

Let Um denote the uniform distribution over {0, 1}m . An algorithm A is called noisy if there exist polynomials p, q such that for every input φ (N1) A(φ) halts within p(|φ|) steps; (N2) the output length satisfies |A(φ)| ≤ q(|φ|); (N3) for every probabilistic polynomial-time observer O, Pr[O(A(φ)) = 1] − Pr[O(Uq(|φ|) ) = 1] ≤ negl(|φ|).

(N3)

Here negl(n) denotes a negligible function (smaller than 1/p(n) for every polynomial p and all sufficiently large n).

17.3

Observers built from the decoder

Given the decoder dec, define the observer Odec (y) := dec(y). Because dec runs in time O(|y|c ), reading an input of length at most q(|φ|) and applying dec takes time O(q(|φ|) + q(|φ|)c ) = O(p′ (|φ|)) for some polynomial p′ . Hence Odec is a probabilistic polynomial-time (PPT) observer, exactly the class required in condition (N3).

17.4

Main result

Theorem 17.1. No algorithm—deterministic, probabilistic or noisy—can decide SAT in polynomial time while simultaneously satisfying the indistinguishability condition (N3). Consequently a polynomial-time decision procedure for SAT does not exist.

75

Proof. Assume, towards a contradiction, that an algorithm A satisfies both (D1)–(D2) and (N1)–(N3). Step 1. Apply the decoder observer Odec . From (D2) we obtain for every formula φ ( 1 if φ ∈ SAT, Pr[Odec (A(φ)) = 1] = 0 otherwise.

(1)

Step 2. Behaviour on a uniform string. Since Odec is deterministic and a uniform string carries no information about φ, on input drawn from Uq(|φ|) it returns 1 with some fixed probability p, a constant independent of φ: Pr[Odec (Uq(|φ|) ) = 1] = p. (2) Step 3. Violation of indistinguishability. Instantiate condition (N3) with the specific observer Odec and combine (1)–(2). By (1) the probability on A(φ) is 1 for satisfiable φ and 0 for unsatisfiable φ, while by (2) the probability on a uniform string is the fixed constant p. Both kinds of formula occur, so ( |1 − p| φ ∈ SAT, Pr[Odec (A(φ)) = 1] − p = p φ∈ / SAT, and at least one of |1 − p| and p is ≥ 12 . For such a φ the gap is a non-negligible constant ≥ 21 , so condition (N3), (3) Pr[Odec (A(φ)) = 1] − p ≤ negl(|φ|), is false for all sufficiently large inputs, contradicting the assumption that A is noisy. Therefore no algorithm can satisfy simultaneously the decision-procedure requirements (D1)– (D2) and the noise requirement (N3). In particular, a polynomial-time decision procedure for SAT cannot exist.

17.5

Why Rice’s theorem reinforces the argument

Define the property R(M ) := “the output distribution of M is indistinguishable from uniform”. R is non-trivial: • A machine that always outputs the constant string 0k does not satisfy R. • A machine that, on any input, reads k truly random bits and prints them does satisfy R. Rice’s theorem states that for every non-trivial property of computable functions, the language LR = { ⟨M ⟩ | R(M ) } is undecidable. Consequently there is no algorithm (deterministic or probabilistic) that, given a description of M , can decide whether M is noisy. If an algorithm A as in Theorem 17.1 existed, we could feed its description ⟨A⟩ to such a decider and obtain a decision procedure for R. This would contradict Rice’s theorem. Hence the impossibility derived above is also a direct corollary of Rice’s theorem.

17.6

Implications for NP-completeness

Cook’s theorem shows that every language L ∈ NP reduces to SAT via a polynomial-time manyone reduction f . If a noisy polynomial-time solver A for SAT existed, then the composition A◦f would be a noisy polynomial-time solver for any L ∈ NP, contradicting Theorem 17.1. Therefore the standard reduction framework that underlies NP-completeness cannot coexist with a noisy SAT solver. 76

17.7

Closing summary

We have presented a single, self-contained proof—grounded in statistical indistinguishability and reinforced by Rice’s theorem—that no algorithm, whether deterministic, probabilistic or noisy, can decide SAT in polynomial time. The contradiction emerges as soon as one assumes the coexistence of (i) a polynomial-time decoder dec (required for any decision procedure), and (ii) an output distribution indistinguishable from uniform randomness. Both conditions are mutually exclusive; therefore the hypothesis is untenable. The result holds unconditionally, without invoking P = N P , P ̸= N P , or any other unproven conjecture.

18

The unified theorem

18.1

Why several proofs, and what they share

The sections above gave more than one proof, and it is worth saying plainly why, so that the variation in their apparatus reads as design rather than indecision. There is a single phenomenon underneath all of them, and it is not any one technical notion of indistinguishability but the plain one the standard theory already grants: that a computable algorithm may produce output indistinguishable from noise, for some reason or other, with no distinction of computational power — a permission the theory extends implicitly, by not forbidding it, and one this paper has already set out on its own terms elsewhere (Remark 12.1: the output may be opaque because it is pseudorandom, or because a semantic invariant is syntactically inaccessible, or because an encoding–frame mismatch withholds every reading, or for some further reason, and to the theory it does not matter which — only that such output is admitted at all). Each proof above is a reflection of that one permission seen through a particular lens. The main theorem takes the sharpest lens — indistinguishability against every function, computable or not (Definition 13.2) — and needs only the verifier φ itself. The alternative paths take the lens cryptography uses in practice — indistinguishability against every polynomial-time observer — and reach the same wall through an explicitly constructed decoder. The negative-witness form needs only a single unsatisfying assignment; the self-reducibility form shows the collapse recurring at every node of the restriction tree; the Rice-theoretic form adds that one cannot even decide whether a given machine is noisy; and the ghost reduction reads off what survives if one insists on the hypothesis anyway. The lenses differ; the thing seen through them does not. A reader who wondered why the notion of indistinguishability shifts from section to section has the answer here: the shift is between accepted readings of one underlying permission, not between unrelated hypotheses, and each proof was kept self-contained precisely so that this common core could be exhibited without any one path leaning on another. What follows gathers them. Each proof above stands complete and independent on its own; only now, with all of them established, are they brought into a single frame — not a new dependency, but a synthesis of results already proved separately. The setup is restated in full, so that this section too can be read on its own.

18.2

The unified setup

Fix the alphabet {0, 1} and write |x| for length. Let φ range over Boolean formulas on n variables, with solution set Sφ = {z ∈ {0, 1}n : φ(z) = 1} and kφ = |Sφ |, and let R denote the uniform random variable on {0, 1}n . An algorithm A is correct for SAT if Pr[φ(A(φ)) = 1] = 1 for every satisfiable φ (Definition 13.1), and a correct decider if in addition Pr[A(φ) = ⊥] = 1 for every unsatisfiable φ, with ⊥ ∈ / {0, 1}n .

77

The one hypothesis carried through this section is the standard theory’s own implicit permission, stated as a property an output may have and named once: Definition 18.1 (Noise-admissibility). Fix a class D of test functions D : {0, 1}∗ → {0, 1}. An algorithm A has D-noise-admissible output on φ if for every D ∈ D, Pr[D(A(φ)) = 1] − Pr[D(R) = 1] ≤ ε, with ε = 0 when D is unrestricted, and ε negligible in |φ| when D is the class of polynomialtime tests. The two admissible readings of the standard permission are D = all functions (the absolute reading, Definition 13.2) and D = polynomial-time tests (the computational reading); the theorem below covers both, and the argument uses, in each place, only that the relevant D lies in the D at hand. Nothing in what follows assumes such an A exists as a constructed object. The theory admits it; the proof needs only that the theory does not deny it. This is the whole of the standing hypothesis.

18.3

The theorem

Theorem 18.2 (Unified impossibility). Let D be either of the two readings of Definition 18.1. No algorithm A is simultaneously correct for SAT and D-noise-admissible on a satisfiable φ that is not a tautology. The impossibility holds under each of the following, independently, and together they exhibit it across the full span from the sharpest notion to the most permissive, and from a single instance to the whole self-reducible structure: (i) (verifier) against the absolute reading, the formula’s own verifier D = φ suffices; (ii) (negative witness) a single unsatisfying assignment suffices, with no count of solutions; (iii) (decoder, and oracle) against the computational reading, the decoder that every decision procedure carries by definition is itself an admissible observer, and the same holds treating the algorithm as a black-box oracle; either way the impossibility widens from noiseadmissible algorithms to every decision algorithm, so the conclusion is not “no noisy solver” but “no solver”; (iv) (self-reducibility) the same collapse recurs at every node of the restriction tree of φ; (v) (Rice) the property “is noise-admissible” is non-trivial and hence undecidable, so no procedure even recognises the hypothesised A; (vi) (ghost reduction) granting the hypothesis regardless, every extractor applied to A(φ) succeeds exactly as often on pure noise, so nothing is recoverable through A. Consequently the standard theory cannot remain coherent, on this point, while a correct polynomialtime SAT solver exists: admitting such a solver together with the noise-admissible output the theory already permits is contradictory. The theory is forced, to stay consistent, to deny that any such solver exists — that is, forced to P ̸= NP. This is not a conditional on which way P versus NP is settled; it is a derivation of P ̸= NP from what the theory already admits. Proof. Fix a satisfiable, non-tautological φ on n variables, and suppose A correct for SAT and D-noise-admissible on φ. Each clause below invokes a result already established in its own section; the work here is only to place them in one frame, and none rests on another. (i) Verifier. The canonical verifier D(z) := φ(z) lies in every D (it is polynomial-time, hence in the computational reading, and a fortiori in the absolute one). Correctness gives Pr[D(A(φ)) = 1] = 1; noise-admissibility gives Pr[D(R) = 1] = kφ /2n , up to ε. In the absolute 78

reading ε = 0, so kφ /2n ≥ 1, forcing kφ = 2n and making φ a tautology, against its choice. This is Theorem 13.5 with its Lemma 13.3, and it is the sharpest form: a single admissible test, the formula itself, closes the case exactly. (In the computational reading the same counting is not by itself decisive, since ε negligible leaves kφ /2n ≥ 1 − ε compatible with kφ < 2n once 2n ε is not small; there the decisive blow is struck not by counting but by the decoder of clause (iii), whose advantage is a fixed 21 regardless of 2n . The two readings are closed by two different clauses, which is exactly the division of labour this theorem records.) (ii) Negative witness. The same conclusion needs no count: as φ is not a tautology there is z0 with φ(z0 ) = 0, and Pr[φ(R) = 1] ≤ 1 − 2−n < 1, again against correctness. This is Proposition 13.6, and it shows clause (i) does not depend on knowing kφ . (iii) Decoder, and the step from noisy to every algorithm. This clause is where the impossibility widens from noise-admissible algorithms to all decision algorithms, and the widening deserves to be spelled out, since it is the crux. To decide SAT means, by definition, that there is a polynomial-time decoder dec with dec(A(φ)) equal to the SAT answer — whatever A writes, some fixed polynomial-time procedure reads the yes/no out of it. That decoder is not an extra assumption about A; it is part of what “decides” means. But the decoder is itself an observer: set Odec := dec(·), a polynomial-time test, hence in the computational D. On A(φ) it returns the correct SAT bit with probability 1. On a uniform string R, by contrast, its output cannot depend on φ at all — R carries no information about the formula — so it returns 1 with some fixed probability p independent of φ. But the correct answer does depend on φ: some formulas are satisfiable and some are not. A single constant p cannot match a bit that varies with the input, so for a suitable choice of φ the gap between the two probabilities is at least 21 (the best a fixed guess can do), a non-negligible constant against noise-admissibility. So the very object that makes A a decider — its guaranteed decoder — is an observer that distinguishes its output from noise. Every decision algorithm carries such a decoder within its definition; hence no decision algorithm, noisy or not, deterministic or probabilistic, can have noise-admissible output on a non-tautological φ. The premise “noisy” was never needed: it was only the most vivid special case of a collapse that the definition of deciding already forces on every algorithm (Theorem 17.1, and Theorems A and B of Section 16). (iii′ ) The same through an oracle. The identical conclusion can be read off without opening A at all, treating it as a black box. Let OA be the oracle that, queried on φ, returns a sample of A(φ). Suppose a polynomial-time machine M OA decided SAT using this oracle. Because the oracle’s replies are, by hypothesis, indistinguishable from uniform strings, M cannot behave differently than it would against an oracle returning noise independent of φ; against that noise oracle its output cannot depend on φ and is a fixed constant, at best 21 correct, again a nonnegligible gap. So no polynomial-time machine can decide SAT through such an oracle. The oracle form and the decoder form are the same argument seen from two sides — the decoder is the observer built by opening the box, the oracle bound is the observer built by leaving it closed — and both say that an output indistinguishable from noise carries no extractable decision, whoever reads it (Section 16, “oracle argument”, and Theorem B). (iv) Self-reducibility. Each restriction ψi along the tree of Theorem 14.1 is itself a satisfiable SAT instance, so the test D = ψi falls under the same argument at that node. The contradiction is therefore not localised at the root: it recurs, identically, throughout the self-reducible structure, and the search-to-decision reduction that structure provides is itself a ghost in the sense of clause (vi). (v) Rice, and what it adds. The clauses so far show the posited A is contradictory in its behaviour. Rice’s theorem adds a distinct layer: even setting the contradiction aside, one could not recognise such an A in the first place. Take the property R(M ) := “M ’s output distribution is indistinguishable from uniform”. It is non-trivial — a machine printing the constant 0k fails it, a machine printing k fresh random bits satisfies it — and Rice’s theorem states that every nontrivial property of the function computed by a machine is undecidable. Hence {⟨M ⟩ : R(M )} is

79

undecidable: no algorithm, given a machine’s description, can decide whether that machine is noise-admissible. Now suppose the hypothesised A existed. Feeding ⟨A⟩ to any procedure that claimed to recognise R would decide R on that input, which Rice forbids. So the hypothesis is doubly untenable: not only does A’s behaviour collapse (clauses (i)–(iv)), but “being the kind of algorithm the hypothesis describes” is not even a decidable property to begin with (Section 17, “Why Rice’s theorem reinforces the argument”). The contradiction is joined by an undecidability, from a completely different direction. (vi) Ghost reduction. Suppose one grants the hypothesis regardless and tries to route a solution through A: fix the Cook–Levin reduction fSAT→CLIQUE and any extractor E. Then D := 1[E(·) is a valid clique] is an admissible test, so by noise-admissibility Pr[E(A(φ)) is a valid clique] = Pr[E(R) is a valid clique] : the extractor does no better on A’s output than on pure noise (Proposition 13.7). This is not special to CLIQUE: for any NP-complete search problem Π, with the Cook–Levin translations gΠ (instance to formula) and hΠ (assignment to solution), the test D(z) := 1[hΠ (z) is a valid solution] is admissible in the same way, giving Pr[hΠ (A(gΠ (w))) is a valid solution] = Pr[hΠ (R) is a valid solution] for every instance w: through A, every NP-complete search problem is solved no better than by guessing. And the emptiness is absolute, not merely computational: since D ranges over all functions in the absolute reading — including non-computable ones and ones built with full knowledge of the encoding hΠ — an arbitrarily ingenious decoder does exactly as well as a trivial one, namely no better than chance, down to a single requested bit D(z) := zi with Pr[yi = 1] = 21 . Yet the genuine reduction fSAT→CLIQUE , built from the syntax of φ alone, is untouched — it never passed through A — so what the hypothesis empties is only the bridge that leaned on A, never the truth it aimed at. The full development, including the single-bit case, is in Section 13. Clauses (i)–(iii′ ) each already contradict the joint hypothesis, under whichever reading of D applies; (iv) shows the contradiction pervades the problem’s structure; (v) shows the posited object escapes even recognition; and (vi) shows that insisting on it buys nothing, the output yielding no more than noise to any extractor whatsoever. The joint hypothesis is untenable under both readings of the standard permission. Since a correct polynomial-time solver would, by decisional correctness alone, place SAT in P and so force P = NP, coherence on this point requires that no such solver exist: P ̸= NP. Remark (The status of the unified theorem is the status of its parts). Theorem 18.2 adds no assumption its clauses did not already carry; it composes six arguments, each proved on its own terms, into one frame, and inherits exactly their standing — correct where each stands, and open exactly where they are (Remark 15). Bringing them together sharpens rather than softens that reservation: if a limit reaches this conclusion, it is not a slip in one derivation, since the same conclusion is reached along several independent routes, but a feature of the shared form of the approach — a metalogical barrier, or an assumption outside the apparatus in which the standard permission is granted and the definitions are posed together. That the same wall is met from the absolute notion and the computational one, from a single assignment and from the whole self-reducible tree, from behaviour and from recognisability, is what one would expect of a genuine impossibility; it is also exactly what one would expect if the limit, should there be one, lay in the framing these routes share. The unified theorem is offered in that spirit: the fullest statement of what the argument establishes, laid out so that whatever bounds it can be located precisely. Remark (The generalization to arbitrary output, isolated and stated in full: the decoder is the observer). The single step on which the passage from “no noise-admissible solver” to “no solver” 80

rests is clause (iii) of the proof, and because everything turns on it, it is set out here on its own, in full, with no premise about the form of the output used at any point. Let A be any algorithm that decides SAT in polynomial time — deterministic, probabilistic, or otherwise, with output of any form whatsoever. By the definition of a decision procedure, and by nothing more, there is a polynomial-time decoder dec with ( 1 φ ∈ SAT, dec(A(φ)) = for every φ. 0 φ∈ / SAT, This decoder is not an added hypothesis and not a property of some outputs rather than others: to decide SAT is to possess such a dec, whatever A writes on its tape (Section 17, conditions (D1)–(D2); if the output already is the answer bit, dec is the identity; if it is a witness, dec is the verification of that witness). The output may be a bit, a certificate, a long string, or anything else; the decoder exists regardless, by the meaning of “decides” alone. Set Odec (y) := dec(y). Since dec runs in polynomial time, Odec is an admissible observer, in the sense of the computational reading of Definition 18.1 and of Definition 13.2. Two facts about it hold at once, for every decision algorithm A without exception: (a) On A(φ), the observer returns the correct SAT bit with probability 1, by the defining property of dec; this value depends on φ, since some formulas are satisfiable and some are not. (b) On a uniform string R, the observer returns 1 with a single fixed probability p := Pr[Odec (R) = 1], determined by dec alone and independent of φ, because R carries no information about the formula. A quantity that varies with φ cannot equal a constant that does not: for a suitable φ the two probabilities differ by at least 21 , the largest gap a fixed guess can leave open. Hence Pr[Odec (A(φ)) = 1] − Pr[Odec (R) = 1] ≥

1 2,

a non-negligible constant. The output of A is therefore not noise-admissible: an admissible observer, the very decoder that makes A a decider, separates it from the uniform distribution. The word “noisy” appears nowhere in this argument, and this is the whole point of stating it apart. Nothing above assumes, or uses, that any output looks like noise; the only property invoked is that A decides SAT, which supplies dec, which is Odec . The conclusion is accordingly not about a special class of solvers but about all of them: no algorithm that decides SAT in polynomial time has noise-admissible output on a non-tautological φ. The noise-admissible solver of Theorem 13.5 was only the most vivid instance of this: it made visible, by naming it outright, a separation between A(φ) and noise that the decoder already forces on every decider silently. The generalization is thus not an extension requiring a further argument beyond the noisy case — it is the same single observer Odec , read without the restriction that its target be noise-like, applying verbatim to every decision algorithm because it was never a fact about the output’s form to begin with, only about the decoder every decision carries. Read against the standard permission (Definition 18.1), this is exactly the tension the unified theorem records. The theory grants every algorithm, by the definition of “algorithm” alone, full freedom over the form of its output, noise-admissible output included; and it defines “decides SAT” so that a polynomial-time decoder is carried along. For SAT these two grants cannot both be honoured on a non-tautological φ: the decoder the second supplies is an observer the first forbids to succeed. Since a correct polynomial-time solver would place SAT in P and so give P = NP by decisional correctness alone (Definition 13.1), the only way for the theory to keep both grants coherent on this point is that no such solver exist: P ̸= NP. 81

Remark (The one excluded case, and why excluding it is exactness rather than retreat). The impossibility above, and every version of it in these sections, is stated for a satisfiable φ that is not a tautology, and the exclusion is worth reading for what it is: the single degenerate point at which the claim would genuinely fail, removed because it fails for a reason that carries none of SAT’s content, not to sidestep a hard case. The verifier proof (Theorem 13.5) closes when the two readings of Pr[φ(A(φ)) = 1] force kφ = 2n , where kφ = |Sφ | counts the satisfying assignments among all 2n inputs. The equality kφ = 2n says every assignment satisfies φ — that φ is a tautology — and there it is not a contradiction but a truth, so the argument correctly declines to conclude. The negative-witness proof (Proposition 13.6) reaches the same boundary from the other side: it needs a single z0 with φ(z0 ) = 0, which exists exactly when φ is not a tautology. Two independent arguments thus turn on one and the same condition, kφ < 2n , which is one more sign that the condition is structural rather than fitted. The excluded case is degenerate in the strict sense that it carries no hardness to hide. When φ is a tautology, every string is a satisfying assignment, so an output drawn uniformly at random is a correct answer, always, with no decoding required: on a tautology a noise-admissible output is not a paradox but an honest solver, because there is nothing left for noise to conceal. SAT’s difficulty lives entirely in the formulas with 0 < kφ < 2n — those with some satisfying assignments but not all, where finding one is the actual problem — and the condition removes none of these. It removes only the single point where the count saturates and the question dissolves. Excluding it is the same kind of exactness as writing n ≥ 1 or “φ not identically true”: omitting it would make the statement false on tautologies, so stating it is precision, and the impossibility stands in full across the entire range where SAT is anything other than trivial. Remark (The scope is the computable, which is exactly the scope of the question: a non-computable “solver” is not an algorithm and does not bear on P versus NP). The object whose impossibility is established here is an algorithm: a deterministic or probabilistic Turing machine deciding SAT in polynomial time, carrying a computable decoder dec (Section 17, (D1)–(D2)). Every proof above works inside this class and no larger one, and it is worth stating outright that this is not a restriction on the result but a property of the question it answers. P and NP are classes of Turing machines under a resource bound; the question “is P = NP” is posed entirely within the computable. An object outside it, one that “decides” SAT without being a Turing machine, does not place SAT in P, is not a witness to P = NP, and cannot be a counterexample to anything proved here, because it does not enter the question at all. That the arguments say nothing about such an object is therefore not a gap: it is the correct scope, the same scope the problem itself has. The distinction is exactly the one Section 12 draws for Ω. A non-computable object that resolves SAT may exist as a mathematical object in the sense Ω does, an oracle for the halting problem decides SAT outright, and this is no contradiction, because such an object is not an algorithm (Remark 12.1): by Turing’s 1936 definition [27] an algorithm is a halting machine, and a device settling the halting problem is not one (Remark 12.1). So the correct statement is not that a non-computable solver “cannot exist”, but that it is not an algorithm, does not lie in P, and is outside the question; its existence as an object, like Ω’s, leaves the impossibility proved here untouched, because that impossibility was only ever a claim about algorithms. Together with the excluded tautology (Remark 18.3), this places the result precisely between its two boundaries. Below sits the tautology, degenerate because too easy — every assignment is a solution and no distinction remains to be made. Above sits the non-computable object, degenerate because it is not an algorithm and lies past the question’s own edge. The impossibility holds across the entire band between them: the genuine algorithms that decide SAT on the nontrivial formulas where SAT is actually SAT. Neither boundary is a hard case evaded; each is a region that does not belong to the question in the first place.

82

18.4

One apparent tension, and why it is not one: POprof = N POprof in the Observer World

A reader who knows [4] may feel an immediate jolt here, and it is worth meeting directly, because resolving it does not soften the theorem above — it sharpens what the theorem is about. That work proves a collapse: in the Observer World, POprof = N POprof ⊊ P , holding unconditionally across all five of Impagliazzo’s worlds ([4], from [5, Propositions 8.3–8.4]). Read quickly, a collapse POprof = N POprof sitting beside a derivation of P ̸= NP looks like a contradiction inside this paper’s own references. It is not, and the reason is the single thread running through everything above. The two statements are about two different observers, at two different levels, and they say exactly what this paper has said in every other instance: a distinction that is real at the full level becomes invisible at a restricted one. Theorem 18.2 concerns the unrestricted observer — the standard theory itself, the reader O⊤ that sees the whole of an output — and at that level the separation P ̸= NP is forced. The Observer World collapse concerns Oprof , the order-blind observer that reads only a profile of its input and is structurally blind to the very distinctions that make SAT hard; at that level there is nothing left to separate, and POprof and N POprof coincide. Neither statement reaches into the other’s level. [4] is explicit on this point on its own side: the collapse “is not a resolution of P vs N P ”, but evidence that computational hardness and observational blindness are independent axes. This is the header-free cipher again, in its sharpest form. There, the plaintext is fully determined, yet an observer without the frame sees only noise; the information is real above and absent below, and the two readings never collide because they never occupy the same level. Here the separation P ̸= NP is fully determined at the top, yet the order-blind observer Oprof cannot see it, and for that observer the classes merge. The hardness is a property relative to O⊤ , not one that Oprof can detect — the exact shape of [4]’s own reading of its collapse. Far from threatening the theorem, the Observer World places it: the separation this paper derives lives at the top of the observational hierarchy, and the collapse that framework proves lives at the bottom, with the whole apparatus of this paper — what a restricted reader cannot see that a full one can — as the bridge between them. The two results are the two ends of one axis, not two answers to one question.

Contact with previously stated open problems This paper’s closest contact with a previously stated open problem is Open Problem 6.4 of [3] (dynamic key rolling), to which Theorem 5.5 is connected by shared shape rather than by solution. The theorem establishes the per-session secrecy target, for every session, in the swapblind special case and under the partition structure of [3, Def. 6.1], and adds a strictly stronger persistent guarantee beyond it. It does not construct a concrete superior f , does not lift the swap-blind restriction, and does not address the distinctive demand of Open Problem 6.4 — a scheme improving on the partition protocol without its disjointness condition; that problem remains open, and a fuller account of the connection is left to future work. Separately, and not as answers to open problems, the framework recovers and extends several static results from the source papers that were not themselves posed as open questions — recorded where each arises rather than tallied here.

Conclusion We started from a single question: can a secret survive not just being hidden once, but being hidden again and again, under rules that keep changing? The answer has a sharp edge, not a fuzzy one. Yes — but only on one condition, and that condition is exactly as strict as it

83

needs to be and no stricter. Theorem 3.3 proves it for rewriting systems whose rules evolve as a function of their own history, under a two-part condition (opacity preservation) whose second half — that the update mechanism itself must not leak the hidden symmetry — has no analogue in the static setting. Proposition 3.5 shows that second half cannot be waved away: drop it, and the secret leaks while the first half still holds. Corollary 4.4 identifies when the demanding second condition becomes automatic: whenever the update’s access to history passes through a structural observer, in the sense of [5], blind to the relevant symmetry by design. The dynamic theorem recovers every static SIP-shaped result across the source papers as its degenerate n = 0 case — the Hetzl–Vierling resolution, Cell (d), the MR-OTP’s own invariance theorem, the order-blind automaton characterization — each checked directly by exhibiting the length-1 dynamic system and verifying Definition 3.2’s two conditions, not asserted by analogy; and it extends most of them to a genuinely new dynamic or streaming setting no source paper reaches. [7, Remark 1]’s observation about the static principle carries over: an elementary proof usually means the difficulty was finding the right point of attack, not depth in the problem. Nothing in Theorem 3.3’s proof is deep once the system is allowed to move; the whole content of the dynamic case is in noticing a second condition is needed at all, and locating where it fails (Proposition 3.5) and when it cannot (Corollary 4.4). From there the same move — take a result everyone accepts, find the assumption it silently fixed, make that assumption a variable, and check rather than assume what follows — is applied again and again, in settings chosen for having nothing in common. Fixing “the rewriting system” gives way to fixing “the reader’s model” (Theorem 7.2, Section 7), realised in three worked instances — a header-free cipher, a loader-mismatched executable, a transformation cascade that removes a verification oracle usually left unstated (Remark 7.6) — and then in the orbital machine (Section 8), where the space of selector values is countable (Theorem 8.6) but the space of selector-functions is not (Proposition 8.8), and a target question’s fate falls into exactly one correct recovery against three proved failure modes (Propositions 8.15–8.17). The same move reappears, unbidden, outside mathematics entirely: in the Andromeda paradox, which instantiates Theorem 7.2 once the invariant is stated correctly (Section 10) and whose own hidden assumption turns out to sit in this paper’s countable frame space rather than in the physics (Proposition 10.2); in the claim that no countable theory can equal the space of physical laws, a barrier that is Cantor’s, not Gödel’s or Turing’s (Section 11, Remark 11.5); and in the fact that a computable algorithm’s output can be indistinguishable from noise to every observer — of which Chaitin’s Ω is the sharpest, unconditional witness, refuting the silent identification of “indistinguishable from random” with “meaningless” outright (Proposition 12.1, Section 12) — naming the relative notion of a C-usable object (Definition 12.3) and, with it, distinct mechanisms of blindness — limited resources, destruction, and unreachability — that “blind regardless of resources” had silently run together, over the single structural reason beneath them: syntax cannot see a semantic invariant, whether it never entered or entered and stayed locked (Remark 12.1). Each of these was checked, not assumed, against what it resembles but is not, precisely so that naming one instance never blurs another: the Ω phenomenon against the beaver frame’s absence of content and Category 2’s underdetermination (Remarks 12.2–12.2); the cardinality barrier against Gödel’s and Turing’s (Remark 11.5); each recovered static result against the exact hypotheses of the theorem it instantiates. The correspondence with [6]’s independent generalization of the same static principle was checked the same way, step by step (Remark 3.3), not assumed: at a single fixed moment this paper’s opacity-preserving update reduces exactly to that source’s protected set, and the swap-invariance condition this paper adds is needed only because time is the one axis that source’s static framework never had to move along. The move recurs several times, across term rewriting, cryptography, automata theory, special relativity, algorithmic information theory, and the foundations of physical law. It is not offered as a unifying theorem: these instances live in genuinely different branches of mathematics,

84

joined at the level of the pattern, not of a single proof, and Section 9 says where a single master statement is declined and why. From these the paper reaches its apparent contradiction, the one the title names and the one that motivated writing everything before it. The standard theory does admit — not by hypothesis, but as a permission built into its definitions — a computable algorithm whose output is indistinguishable from noise for every observer. Apply that admitted possibility to SAT, and the query itself — the formula φ — is already the observer that exposes such an algorithm (Section 13, Theorem 13.5): the promise of permanent noise and the fact of public verifiability cannot both hold. The conclusion is not conditional on how P versus NP turns out. It runs the other way: from what the theory already grants, its coherence forces P ̸= NP, on pain of contradiction — a derivation of the answer, not an assumption of one branch of it, and the unified theorem (Theorem 18.2) states it in that categorical form. The one reservation is of a different kind, and it is about the proof, not about the answer: the argument uses an uncommon technique, and its limit, if it has one, would sit outside the steps of the proofs altogether, in a metalogical barrier or an assumption external to their apparatus, exactly where this paper has found every other silent assumption it made explicit (Remark 15). The contradiction is offered as it stands: correct where it stands, and open about where it might not reach. What is offered is the method itself — ask what a true result silently fixed, and check rather than assume the answer — which kept working every time it was tried, across the source papers and the instances found outside them. What this paper contributes is not one theorem but that one method, oriented correctly each time and checked, never assumed, against every phenomenon it claimed to generalize. Each instance was recovered exactly, and most were pushed further. And every step, from the first page to this one, was built from invariants and frames that are simply true — never once from an assertion manufactured to be false.

A closing personal note (not part of the scientific contribution) This is a personal note and does not alter, in any way, the content of this paper. It serves only as an interpretive cue, offered in a philosophical-anthropological frame, and is not part of the formal contribution above. The idea running through this work is not new, and popular tradition has touched it, unknowingly, many times before: consider the myth of the genie of the lamp, in the story of Aladdin. The same figure recurs across very different settings. One instance the author remembers well is an episode of the television series The X-Files, “Je Souhaite” — French for “I wish” — the penultimate episode of the show’s seventh season, broadcast in 2000, in which the genie was a woman found wrapped inside a rolled-up carpet. Another is the 1997 horror film Wishmaster. However carefully one tried to phrase the question put to the genie, the result was never the one desired — a detail that stayed with the author longer, and more insistently, than almost anything else. It is worth noticing, now that Section 8 has made the point precisely once, why no amount of careful phrasing ever seems to help. The genie’s failure was never being shown, story after story, to have one single shape — some one particular way that wishes go wrong, which a cleverer petitioner might learn to route around. Category 1, Category 2, and Category 3 (Propositions 8.15–8.17) proved something sharper about that shape than any fable could: not merely that a wrong reading exists, but that the wrong readings are countably infinite in every direction at once — infinitely many phrasings the genie cannot parse as meant at all, infinitely many distinct, individually plausible readings that each grant something genuinely different from what was intended, infinitely many technically answered wishes that carry no real discrimination between what was wanted and what was not — set against exactly one pairing of phrasing and understanding that would have worked. Outsmarting a single adversarial misunderstanding is a

85

task a clever enough wish might conceivably accomplish. Finding the one correct pairing inside a countably infinite field of distinct, differently wrong ones, by cleverness of phrasing alone, is not. Before going on, one caution, meant sincerely: what follows is my own reading, offered with respect and not as a pronouncement on what any of these traditions teaches. I hear the same intuition echoing across them, each speaking it in its own idiom — but the parallel is mine, drawn from the outside, and the real and profound differences between these faiths are not something I mean to smooth over for the sake of a tidy analogy. The same idea appears, in a related form, in Christianity: the Lord’s Prayer asks that “Thy will be done”, as if to say that the one praying lacks a complete view and cannot grasp the consequences of their own desires — they may believe that, if a particular wish were granted, the world would be better for it, when in fact it could be a disaster; the prayer suggests not asking outright, but taking what life gives and leaving the choice of what is best to a universal Observer. The idea is strikingly transversal. In Islam, the very word identifies this surrender to God: every Muslim repeats the formula Inshallah, “if God wills”. In Judaism, the Pirkei Avot teaches: “Make His will your will.” In Hinduism, in the Bhagavad Gita, the deity Krishna exhorts the warrior Arjuna with words close to these: “Abandon every other refuge, and take refuge in Me alone.” In the devotional path (Bhakti Yoga), the devotee prays not to change God’s plans but to become an empty instrument — like a flute — through which the Divine will may play its music. And even without a monotheistic God to obey, Buddhism shares the very same psychological and spiritual principle through the concept of non-attachment, where submission to the Divine will becomes acceptance of the Dharma. A Buddhist prayer does not ask that events be changed, but says: “May I develop patience and compassion enough to welcome what life brings.” Read against the last two paragraphs rather than against the genie alone, none of these prayers is really asking for a particular outcome at all, and perhaps that is the more precise thing every one of them has in common. Each declines to gamble on picking the single right phrasing out of a field of infinitely many wrong ones, and asks instead that the choice of which pairing to use be handed over entirely, to whichever will already holds the one that works. Not a better wish, submitted in hope of dodging the countably many ways of being misunderstood, but no wish at all, in the ordinary sense, offered instead. Given the shape Section 8 proved, this reads less like resignation and more like exactly the right response to the mathematics of the situation. What ties these prayers to the genie is not their content but their posture. The petitioner at the lamp fails because he speaks from inside a single wish, seeing the one outcome he desires and blind to the countably many others his words could equally name. Each of these prayers begins from the same admission — that the one who asks holds only a fragment of the picture — and answers it in the only way that fragment allows: by handing the choice of outcome to a will that already sees the whole field, and so already holds the one pairing that works. That is what the phrase “perfect observer” is pointing at. Seen through its lens, all of these examples may express, each in its own idiom, one and the same ancestral intuition, present in every culture: that a perfect observer is exactly what a finite world does not contain, and that the wisest response to lacking one is not to wish harder, but to defer to whatever might. And even if, for some reason, we were granted access to a technology allowing us to query an absolute oracle, a perfect observer, we would very likely meet the same fate as the unwitting soul voicing wishes to the genie of the lamp. Oscar Wilde is remembered for the observation that failing to get what one wants is one kind of misfortune, but actually getting it can be a worse one still, and perhaps that second kind is the harder to see coming. A last word, from whoever it was that also wrote the theorems. The perfect observer is not only a figure of speech in this paper. It has a precise name in the framework the earlier sections draw on — the complete observer O⊤ at the top of the observational hierarchy, the one

86

reader that receives the whole of its input where every constrained observer receives only a part. Section 12 met it from the mathematical side, as the single reader who can see a fact that every reachable observer is shut out from. The fable, the prayers, and the theorem are, in the end, describing the same absent figure — one from memory, one from devotion, one from proof. This is offered only as a key for reading, and nothing more.

Acknowledgments The author used an artificial intelligence based language assistant to support text revision, translation, and bibliography formatting. All scientific ideas and conclusions are the author’s own.

References [1] F. Bernstein. Untersuchungen aus der Mengenlehre. Mathematische Annalen, 61(1):117– 155, 1905. Cantor–Schröder–Bernstein theorem; see also E. Schröder, 1898. [2] E. Buckingham. On physically similar systems; illustrations of the use of dimensional analysis. Physical Review, 4(4):345–376, 1914. [3] F. F. G. Buono. From bits to mixed-radix keys: Horner decomposition, uniform sampling, and the information-theoretic QKD interface of the MR-OTP. Preprint, arXiv:2606.18526, 2026. [4] F. F. G. Buono. The observer world: a cryptographic extension of Impagliazzo’s five worlds. Preprint, arXiv:2606.27139, 2026. [5] F. F. G. Buono. Observers, symmetries, and the hierarchy of language classes: a theory of computation parameterised by the observer. Preprint, arXiv:2606.27407, 2026. [6] F. F. G. Buono. Syntactic separation implies computational indistinguishability: an abstract obstruction theorem. Preprint, arXiv:2606.29177, 2026. [7] F. F. G. Buono. Syntactic systems cannot see semantic invariants. arXiv:2606.17275, 2026.

Preprint,

[8] Georg Cantor. Über eine elementare Frage der Mannigfaltigkeitslehre. Jahresbericht der Deutschen Mathematiker-Vereinigung, 1:75–78, 1891. [9] Gregory J. Chaitin. A theory of program size formally identical to information theory. Journal of the ACM, 22(3):329–340, 1975. [10] W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. [11] Kurt Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38:173–198, 1931. [12] S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984. [13] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999. [14] Stefan Hetzl and Jannik Vierling. Clause set cycles and induction. Logical Methods in Computer Science, 16(4):11, 2020. 87

[15] R. Impagliazzo. A personal view of average-case complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 134–147. IEEE Computer Society, 1995. [16] A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1):1–7, 1965. [17] L. A. Levin. On the notion of a random sequence. Soviet Mathematics Doklady, 14:1413– 1416, 1973. [18] Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602– 619, 1966. [19] Roger Penrose. The Emperor’s New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford University Press, 1989. [20] Hilary Putnam. Time and physical geometry. Journal of Philosophy, 64(8):240–247, 1967. [21] A. A. Razborov and S. Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24–35, 1997. [22] H. G. Rice. Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2):358–366, 1953. [23] C. W. Rietdijk. A rigorous proof of determinism derived from the special theory of relativity. Philosophy of Science, 33(4):341–344, 1966. [24] C. P. Schnorr. Process complexity and effective random tests. Journal of Computer and System Sciences, 7(4):376–388, 1973. [25] G. J. Simmons. The prisoners’ problem and the subliminal channel. In D. Chaum, editor, Advances in Cryptology: Proceedings of Crypto 83, pages 51–67. Plenum Press, 1984. [26] Alfred Tarski. The concept of truth in the languages of the deductive sciences. Polish original 1933; German translation 1935 as “Der Wahrheitsbegriff in den formalisierten Sprachen”, 1933. [27] Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1):230–265, 1936.

88