Inexpressibility Traps in Formal Systems形式系统中的表达性陷阱

The following content is generated by LLMs and may contain inaccuracies.

Context

This idea sits at the intersection of proof theory, algorithmic information theory, and the sociology of scientific paradigms. It distinguishes two properties of a formal system that are usually conflated: deductive power (which theorems are provable) and expressive economy (how cheaply a given truth can be stated and reached). Two systems can be extensionally identical — proving exactly the same theorems — yet differ radically in the discovery cost of any particular result. The claim is that this asymmetry “is not about power, only about what is cheap to say,” and that it can be made precise via description complexity with a resource bound, i.e. a Kolmogorov-style measure where cost is explicitly bounded rather than idealized to the incomputable limit. The framing then models frame-switching as a decision under cost: a community adopts an alternative representation only when the gain exceeds the switching cost. The pathology to explain: a community can know it occupies the inferior frame and still, in expectation, never move — and worse, a frame can render its superior alternative literally unstateable, making the switching cost not merely high but undefined.

Key Insights

• Provable equivalence vs. speed-up is a real theorem, not a metaphor. Gödel’s speed-up phenomenon shows that adding an axiom (or moving to a stronger system) can shorten proofs of statements provable in both systems by a non-elementary amount — the shortest proof in the weaker system can be astronomically longer. This is the rigorous core of “same theorems, different discovery cost.” See Gödel’s 1936 note “Über die Länge von Beweisen” and its modern treatment in proof complexity (Buss, Handbook of Proof Theory). The asymmetry is genuinely about representation, not provability.

• The resource-bounded framing is the right one. Plain Kolmogorov complexity is uncomputable, so an unbounded “cost of saying” would be undefined for the wrong reason. Time-bounded Kolmogorov complexity ($K^t$) and Levin’s notion of complexity ($Kt = K + \log t$) build the resource bound in directly, which matches the note’s insistence that “the whole point is that cost is bounded.” See Li & Vitányi, An Introduction to Kolmogorov Complexity and Levin’s Universal search (1973). This is the natural home for pricing “what is cheap to say” in a frame.

• The exponential-lock-in dynamic has an economic analogue. The claim that “even after the alternative frame has genuinely become better, if the switching cost dwarfs the gain, the expected time to switch grows exponentially” mirrors path dependence and technological lock-in: QWERTY, VHS, and network-effect standards persist despite known superior alternatives. See W. Brian Arthur, “Competing Technologies, Increasing Returns, and Lock-In by Historical Events” (Economic Journal, 1989) and David’s QWERTY study. A community “knowing it’s in the worse frame and still never moving” is exactly a coordination equilibrium that is Pareto-dominated but individually stable.

• This generalizes Kuhn without requiring incommensurability of truth. Kuhn’s paradigms differ in what problems are even seen; here the twist is sharper — the frames prove the same theorems, so there is no truth-level disagreement, only a cost-level one. This is closer to Kuhn’s “On the essential tension” between tradition and innovation than to full incommensurability. See Thomas Kuhn, The Structure of Scientific Revolutions (1962).

• The punchline is the genuinely new move: undefined, not high, switching cost. If frame A cannot even express the object that names frame B’s advantage, then the gain term in the switch-decision is not a large number — it has no value in A’s vocabulary. “You can’t price a move you can’t describe.” This is a self-referential inexpressibility, adjacent to Tarski’s undefinability of truth (a language cannot express its own truth predicate) — Tarski, The Concept of Truth in Formalized Languages. The relevant deficit is not deductive incompleteness (Gödel) but expressive incompleteness: some concepts require an extension of the language before they can be reasoned about at all.

• Search under undefined objectives is the operational crux. The closing question — “how do you find a better frame if a better frame is undefined?” — is the same structural problem faced in open-ended search and novelty-driven exploration, where the target cannot be specified in advance. Lehman & Stanley’s “Abandoning Objectives: Evolution Through the Search for Novelty Alone” (Evolutionary Computation, 2011) argues that when the objective is deceptive or unstateable, objective-driven search fails and only novelty/diversity pressure discovers stepping stones. This suggests the escape route is not optimization within the frame but exploratory expansion of the frame’s vocabulary.

Open Questions

• If a frame’s advantage is unstateable from inside the current frame, is the only reliable discovery mechanism a blind expansion of expressive vocabulary (analogous to novelty search or conservative axiom extension) — and can we characterize which vocabulary extensions are “safe” enough that a community would tolerate the switching cost before the payoff is visible?

• Can the transition from “high but finite” to “undefined” switching cost be formalized as a phase boundary — e.g., in terms of whether the superior frame is a conservative extension (payoff pricable) versus a non-conservative reframing (payoff requires the new language to even be named)?