Computation, Condensation, and the Incompleteness Between Them: A Coupled Foundation of Intelligence

Xin Li

cs.LGMar 7, 2023

Computation, Condensation, and the Incompleteness Between Them: A Coupled Foundation of Intelligence

Authors: Xin Li

Abstract

The theory of computation was built to answer Turing's question: what is effectively calculable by an unbounded, immortal, disembodied agent following rules? Intelligence answers a different question (nature's): what can a \emph{finite}, mortal, energy-limited agent do quickly enough to survive in a non-stationary world? We argue that a complete answer requires two operators: \emph{computation} and \emph{memorizaion}. Computation, $\dpar$ , transforms structure toward closure; memorization, $\kap$ , condenses a validated closed cycle into a reusable token. Turing formalized $\dpar$ and abstracted $\kap$ away, because his agent had infinite time and never needed to amortize. The new insight of our position paper is that the coupling of the two is not optional but \emph{forced}, and forced by a precise mathematical fact: \textbf{neither operator alone can be complete}. We prove that symbolic computation confined to a discrete sector suffers Gödel's diagonalization incompleteness, that geometric descent confined to a continuous sector suffers a Morse forced-saddle incompleteness, and that these two are not analogies but the parity-conjugate faces of a single obstruction on a coherent complex with $\dpar^2=0$ - the even face realized by diagonalization, the odd by the topologically forced saddle, and no resolution confined to one parity able to come full circle. Intelligence must therefore couple both modes. We then locate the price of the coupling: its hinge operation, context-identification (the recognize-versus-discover decision), is exactly where the two incompletenesses coincide, hence undecidable and carrying an irreducible error floor. Finally we argue that the coupling is a universal law, realized, in the emergent sense of Anderson's ``more is different,'' at every scale from genes to thoughts to cultures, and give its falsifiable core and honest scope.

Explore similar work

Apr 21, 2026cs.IT

Watts-per-Intelligence Part II: Algorithmic Catalysis

We develop a thermodynamic theory of algorithmic catalysis within the watts per intelligence framework, identifying reusable computational structures that reduce irreversible operations for a task class while satisfying bounded restoration and structural selectivity constraints. We prove that any class specific speed-up is upper-bounded by the algorithmic mutual information between the substrate and the class descriptor, and that encoding this information incurs a minimum thermodynamic cost via Landauer erasure. Combining these results yields a coupling theorem that lower-bounds the deployment horizon required for an algorithmic catalyst to be energetically favourable. The framework is illustrated on an affine SAT class and situates contemporary learned systems within an information thermodynamic constraint on intelligent computation.

Elija Perrier

Thermodynamics Information-Theoretic Limits Computable Heterogeneous Catalysis General Intelligence Computational Cost+1

Ask PDF

May 4, 2026cs.AI

Intervention Complexity as a Canonical Reward and a Measure of Intelligence

The Legg--Hutter universal intelligence measure provides a rigorous scalar assessment of general intelligence as expected reward across all computable environments, weighted by simplicity. However, the measure presupposes an externally specified reward function, raising the question of whether the reward primitive is inherently arbitrary or whether a canonical choice exists. We propose a new measure, called intervention complexity, that has five natural properties: environment-derivedness, universality, minimality, sensitivity, and achievement preference. Given a resource function rho encoding an inductive bias (such as program length, execution time, or energy), rho-intervention complexity is a universal reward. The result yields a family of canonical rewards indexed by resource bias, providing a principled completion of the Legg--Hutter framework that does not require external normative input. We further propose a two-dimensional characterisation of intelligence: agent competence (how well the agent performs relative to the oracle optimum) and learning efficiency (how quickly this competence improves with experience). A separation theorem establishes that the choice of resource bias determines the computability of the resulting measure: action-count IC is computable in polynomial time, while program-length IC without oracle access is uncomputable, with the gap between oracle and bare IC precisely quantifying the information-theoretic content of learning. We discuss implications for superintelligence and for pre-training universal agents.

Brendan McCane

General Intelligence Computable Rationality Causal Intervention Inductive Bias Measures

Ask PDF

Jul 20, 2026cs.LG

Intelligence from Learnable Novelty

Intelligence appears under different names in different fields: as data compression in statistics and machine learning, as universal computation in dynamical systems, and as adaptive behavior in agents. Each field carries its own objective, and the two most influential drives often fail in mirror image: novelty search, which seeks surprise, is transfixed by a noisy television screen, while the free-energy principle, which avoids surprise, is most content in a dark room. Both failures have a single cause: each objective treats as one quantity the surprise a learner can convert into knowledge and the surprise it never can. Here we show that the learnable part of that information, which we call learnable novelty, yields the seemingly disparate projections of intelligence, and we give a closed-form estimator of it built on a cheap and differentiable reservoir computer. Used as a measure, with no supervision of any kind, the estimator recovers decades of complexity classification, ranking the Turing-complete rule110 highest among the elementary cellular automata. Used as an objective, its gradient carries a neural cellular automaton from simple dynamics into a regime of solitons, the traveling, colliding structures by which rule110 computes, as well as organizes the representation of an image encoder around the ten digit classes of MNIST, fully unsupervised: no label ever enters training. Handed to a reinforcement-learning agent as an intrinsic reward, it supplies the exploration that task rewards lack, improving on the task baseline in nine of ten environments and collapsing in none. Complexity generation, abstraction, and exploration, ordinarily pursued with unrelated objectives in separate fields, thus emerge from ascent on one differentiable quantity, and the projections of intelligence gain a common quantitative footing.

Yanbo Zhang, Michael Levin

Neural Cellular Automata Intrinsic Rewards

Ask PDF