Paper deep dive
Watts-per-Intelligence Part II: Algorithmic Catalysis
Elija Perrier
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/26/2026, 4:41:49 PM
Summary
The paper develops a thermodynamic theory of 'algorithmic catalysis' within the Watts-per-Intelligence (WPI) framework. It defines an algorithmic catalyst as a reusable computational structure that reduces the irreversible operations (energy cost) required for a specific task class by exploiting the algorithmic mutual information between the substrate and the task class descriptor. The authors prove a 'Structural Selectivity Theorem,' stating that the class-specific speed-up is upper-bounded by the algorithmic mutual information. The framework includes a physical-erasure lemma based on Landauer's principle and a coupling theorem that establishes a deployment horizon for energetic favorability. The theory is illustrated using an affine-SAT class and connects to existing models of catalytic computation and the thermodynamics of intelligence.
Entities (7)
Relation Signals (4)
Structural Selectivity Theorem → bounds → Class-specific speed-up
confidence 100% · the class-specific speed-up is upper-bounded by the algorithmic mutual information between the substrate and the class descriptor
Landauer Erasure → determinescostof → Information installation
confidence 100% · installing this information incurs a minimum thermodynamic cost via Landauer erasure
Affine-SAT → illustrates → Watts-per-Intelligence (WPI) framework
confidence 100% · The framework is illustrated on an affine-SAT class
Algorithmic Catalyst → ispartof → Watts-per-Intelligence (WPI) framework
confidence 100% · We develop a thermodynamic theory of algorithmic catalysis within the watts-per-intelligence framework
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 installing 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 a catalyst to be energetically favourable. The framework is illustrated on an affine SAT class and situates contemporary learned systems within a unified information-thermodynamic constraint on intelligent computation.
Tags
Links
- Source: https://arxiv.org/abs/2604.20897v1
- Canonical: https://arxiv.org/abs/2604.20897v1
Trouble viewing inline? Open PDF directly →
Full Text
57,920 characters extracted from source content.
Expand or collapse full text
11institutetext: Centre for Quantum Software and Information, University of Technology Sydney, Australia. 11email: elija.perrier@gmail.com Watts-per-Intelligence Part I: Algorithmic Catalysis Elija Perrier Abstract 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 installing 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 a catalyst to be energetically favourable. The framework is illustrated on an affine-SAT class and situates contemporary learned systems within a unified information–thermodynamic constraint on intelligent computation.111Under review 1 Introduction Catalysts are central to the chemical processes that drive organic life by permitting chemical reactions to occur that would otherwise be thermodynamically unfavourable or impossible [23]. By doing so, catalysts have enabled the emergence of complex organic life and evolution of intelligence. These structures, which include enzymes, ribozymes, metal centres and mineral surfaces, make reaction pathways available that would otherwise be unusable on biological timescales. A transformation may be thermodynamically permitted, in the narrow sense that its products are not forbidden by equilibrium free energy, yet still remain practically inaccessible because the relevant transition state is too unlikely. Catalytic structure lowers activation free energy, stabilises transition-state structure, pre-organises substrates, couples unfavourable steps to energetic cofactors and suppresses competing routes [36, 2, 14]. Recent work on machine intelligence [11, 29, 12] has shown how thermodynamics constrains algorithmic forms of intelligence. It is therefore natural to ask whether there exist algorithmic analogues of catalysts which may help overcome such constraints: reusable computational structures that render feasible certain algorithmically intelligent activities that would otherwise be thermodynamically prohibitive. In this paper, we answer this question in the affirmative by extending and developing algorithmic analogues of catalytic structure characterised by three properties: (a) affording a lower-energy pathway through a structured family of transitions; (b) remaining persistent so as to not be consumed by the reactions they enable; and (c) imposing a structural selection mechanism that facilitates algorithmic computation by virtue of their structure, rather than merely accelerating. To do so, we draw upon and synthesise elements of two primary existing bodies of work: (i) that of catalytic computation [7] in which a small working machine is given access to auxiliary memory whose contents must be restored exactly at termination; and (i) the thermodynamics of intelligence, specifically the watts-per-intelligence framework [29]. Our novel contribution involves the introduction of a thermodynamic basis for the catalytic effects of computation in a way that connects to emerging work on the thermodynamics of machine intelligence. Specifically, we contribute the following: 1. A selectivity theorem such that in a universal-search cost model the logarithmic class-specific speed-up achievable by a substrate is bounded above by the algorithmic mutual information between the substrate description and a canonical descriptor of the task class. 2. A physical-erasure lemma, obtained from the Zurek–Bennett correspondence between algorithmic complexity and thermodynamic entropy [38, 4], which sets out a lower bound on the number of irreversible bit-operations any physical adaptation process must perform on the adaptation substrate to install the information. 3. A coupling theorem which proposes a lower bound on the energetic break-even horizon below which no putative catalyst can be thermodynamically favourable on its class of algorithms; 4. A composition theorem for chains of catalysts which establishes that catalytic gains multiply in rate while combining sub-additively in information, matching the chemical intuition that enzymes along metabolic pathways compound their rate enhancements without compounding their selectivity. We demonstrate the application of these results using a worked affine-SAT example and show how the catalytic-computation model of Buhrman et al. is recovered using our formalism. First, we recapitulate the WPI framework for thermodynamic constraints on intelligence. 2 Background and Related Work 2.1 Watts-per-intelligence The watts-per-intelligence framework sets out a basis for estimating thermodynamic bounds on certain algorithmic computation associated with intelligent tasks [29]. A computational system is represented as a triple Σ=(,ℋexec,ℋadapt) =(A,H_exec,H_adapt), where A is the algorithm, ℋexecH_exec is the substrate on which deployment occurs, and ℋadaptH_adapt is the substrate on which training, compilation, restoration or repair occurs. The two substrates may coincide when adaptation and deployment are performed on the same physical device. The distinction is informative because substrate overhead factors and energy accounting may differ substantially between the two phases. Let kBk_B be Boltzmann’s constant, let T be the ambient temperature of the computation, and let c:=kBTln2c:=k_BT 2 denote the Landauer cost per erased bit. Let N(Σ,)N( ,T) count the irreversible bit-operations performed on ℋexecH_exec during a benchmark pass of horizon τ on task T. Reconfiguration erasures on ℋadaptH_adapt are accounted separately. Each substrate carries an overhead factor F(ℋ)≥1F(H)≥ 1 relative to the Landauer benchmark [29, 13, 1]. The substrate-floor hypothesis, which follows from the second law applied to irreversible operations on the relevant substrate, is E(Σ,)≥F(ℋexec)N(Σ,)c.E( ,T)\;≥\;F(H_exec)\,N( ,T)\,c. (1) A task-weighted intelligence score I(Σ,)=∑iwipi(Σ)I( ,T)= _iw_ip_i( ) with wi≥0w_i≥ 0 and pi∈[0,1]p_i∈[0,1] is fixed, corresponding to a finite-task restriction of Legg–Hutter universal intelligence [24, 19]. The watts-per-intelligence ratio and its Landauer floor are then Φ(Σ,)=E(Σ,)/τI(Σ,),Φ↓(Σ,)=F(ℋexec)N(Σ,)cτI(Σ,), ( ,T)= E( ,T)/τI( ,T), ( ,T)= F(H_exec)N( ,T)cτ I( ,T), (2) with Φ↓≤Φ ≤ . Equation (1) provides the basis for calculating the thermodynamic costs against which our proposed catalytic structures are compared. 2.2 Catalytic computation In catalytic computation literature, a catalytic Turing machine in the sense of Buhrman et al. [7] is a logspace machine equipped with an additional read-write auxiliary tape of length polynomial in the input size, whose initial contents are arbitrary and whose final contents must coincide bit-exactly with the initial contents at termination. The class CL is defined as the set of languages decidable by such a machine in polynomial time with logarithmic clean space. The central structural result from [7, 22] of interest to us is that log-space uniform 1 TC^1 is contained in CL and that CL is in turn contained in ZPP, with subsequent refinements in the randomised, non-deterministic and derandomised settings [8, 15, 30] and a tree-evaluation algorithm in space O(logn⋅loglogn)O( n· n) [9, 10, 16]. The catalytic computation model shows that a very limited machine (with only log-space memory) can solve much richer problems if it is allowed to use a large auxiliary workspace, provided that workspace is returned exactly to its original state at the end. This use without consumption is what makes the model mathematically clean: the auxiliary tape can start in any configuration, so the computation must work uniformly without relying on hidden structure. However, the model is purely asymptotic and does not account for the physical cost of restoring that workspace. This is precisely the gap addressed by our generalised algorithmic catalysis framework in Section 3. 2.3 Related work While several literatures address parts of this problem, none address the question of thermodynamically-based algorithmic catalysis per se. Amortised inference in probabilistic modelling [35, 20, 31] replaces repeated expensive inference with a learned procedure that is cheap to apply at deployment, which motivates the adaptation/deployment split but does not track the underlying thermodynamic cost. Algorithmic thermodynamics, beginning with Zurek [38] and Bennett [4, 5] and extended in stochastic thermodynamics [28, 37], links algorithmic complexity to physical entropy and provides the basis for bounding erasures in terms of information, as used in Section 5. Minimum description length and related learning bounds [32, 18, 27] quantify how much information a model captures about a data-generating process, which parallels the structural selectivity condition here, albeit phrased in terms of distributions rather than class descriptors. Finally, work on the thermodynamics of learning [34, 17] connects training-time dissipation to mutual information between learner and data in concrete physical models, providing a coarse-grained analogue of the adaptation-cost lemma in Section 5. 3 Formal Framework We now set up our formal framework. Let U denote a universal prefix Turing machine. For any string or structure x admitting a canonical encoding, KU(x)K_U(x) denotes prefix Kolmogorov complexity on U and KU(x∣y)K_U(x y) denotes its conditional counterpart. The algorithmic mutual information between x and y is given by: Ialg(x:y):=KU(x)−KU(x∣y),I_alg(x:y):=K_U(x)-K_U(x y), (3) which is symmetric up to a small additive O(logK)O( K) term [26, 21, 33, 25]. For a substrate ℋH, desc(ℋ)desc(H) denotes a fixed, self-delimiting encoding of ℋH on the universal machine U, i.e. a canonical description that fully specifies the substrate independently of the task or its operational history. For an algorithm A, idle()idle(A) denotes a fixed reference (idle) state to which the system is required to return after each cycle. Fixing it in advance prevents arbitrary final states from being retroactively declared idle and thereby trivialising the bounded-restoration condition. For a task class C, σ()σ(C) denotes a canonical descriptor of the generative or structural regularities of C: the shortest description of the information that makes new instances recognisably members of the same class, such as symmetries, grammars, constraints, conservation laws, dependency structures or recurrence relations. Using the concepts above, we can now define the algorithmic counterparts of the three properties that characterise chemical catalysts: pathway opening, non-consumption, and selectivity. Pathway opening corresponds to a reduction in irreversible bit-operations at matched intelligence, measured via (1). Non-consumption requires that the substrate returns close to a fixed reference state after each cycle, with the associated restoration energy accounted for explicitly. Selectivity becomes a condition on conditional Kolmogorov complexity: the substrate must encode non-trivial information about the task class, together with a transfer requirement that rules out finite-instance memorisation. We formalise these in Definition 2 below. Definition 1(Algorithmic speed-up and barrier) For systems Σ0 _0 and Σ1 _1 on a task T at matched intelligence I(Σ1,)=I(Σ0,)I( _1,T)=I( _0,T), the class-specific speed-up factor Γ() (T) and the logarithmic operation barrier ℬ(Σ,)B( ,T) are Γ():=N(Σ0,)N(Σ1,),ℬ(Σ,):=log2N(Σ,). (T):= N( _0,T)N( _1,T), ( ,T):= _2N( ,T). (4) Definition 1 introduces two complementary quantities: Γ measures how much less work one system requires than another at the same task (hence matched intelligence), while ℬ=log2NB= _2N expresses this cost on a logarithmic scale, so that reductions in ℬB capture multiplicative improvements as the opening of lower-cost computational pathways. With this notion of barrier in place, we can define the algorithmic analogue of catalysis: a reusable computational structure that lowers the effective computational barrier across a task class, thereby opening pathways that would otherwise be infeasible under the same resource constraints, while remaining available for repeated use. Definition 2(Algorithmic catalyst) Let Σ0=(0,ℋexec,0,ℋadapt,0) _0=(A_0,H_exec,0,H_adapt,0) be a reference system for a task class C, with irreversible operation count N0N_0 and intelligence score I0I_0. A system Σcat=(cat,ℋexec,cat,ℋadapt,cat) _cat=(A_cat,H_exec,cat,H_adapt,cat) is an algorithmic catalyst for Σ0 _0 on C if the following three conditions hold on every ⊆T . 1. Pathway opening. At matched intelligence I(Σcat,)=I0I( _cat,T)=I_0, deployment irreversibility is strictly reduced, N(Σcat,)<N(Σ0,)N( _cat,T)<N( _0,T), where deployment work excludes training, adaptation and restoration erasures, which are accounted separately. 2. Bounded reconfiguration. There exists ΔKcycle∈ℤ≥0 _K^cycle _≥ 0 such that after each benchmark cycle the execution substrate lies within ΔKcycle _K^cycle bits of the idle description idle(cat)idle(A_cat) in prefix description length, and the per-cycle restoration energy accounted on ℋadapt,catH_adapt,cat satisfies Erestorecycle≥F(ℋadapt,cat)ΔKcyclec.E_restore^cycle\;≥\;F(H_adapt,cat)\, _K^cycle\,c. (5) 3. Structural selectivity. There exist δ>0δ>0 and η>0η>0 such that the speed-up transfers across unbounded class augmentations, lim inf|′|→∞,′⊆Γ(′)≥ 1+δ, _|T |→∞,\,T (T )\;≥\;1+δ, (6) and the substrate description conditionally compresses the class descriptor by at least η bits, KU(σ()∣desc(ℋexec,cat))≤KU(σ())−η.K_U\! (σ(C) (H_exec,cat) )\;≤\;K_U(σ(C))-η. (7) The quantity η is the structural information carried by the substrate about the task class. The pathway-opening condition is written in irreversible-bit units so that reductions in N directly correspond to reductions in physical cost via (1); at matched execution-substrate overhead Φ↓(Σcat)Φ↓(Σ0)=1Γ ( _cat) ( _0)= 1 . A catalytic system is therefore one that makes previously costly computational routes usable at lower energy, in the same sense that a chemical catalyst makes an otherwise inaccessible reaction pathway available. The bounded-reconfiguration condition ensures that this advantage is reusable rather than one-off: as in chemistry, the catalyst may change during the process but must return close to a fixed reference state after each cycle, with the work required to restore that state explicitly accounted for rather than ignored. The structural-selectivity condition captures the analogue of active-site specificity: the substrate must encode information about the structure of the task class itself, so that the reduction in cost persists on new instances drawn from that class, rather than being limited to a finite set of memorised inputs. A useful consequence of the framework is a natural notion of refinement between substrates, which we leverage when considering how algorithmic catalysts may be composed (Section 6). Intuitively, a substrate ℋ′H refines ℋH if it contains all of the structural information that ℋH provides about the task class, possibly together with additional structure. This is captured by the condition KU(desc(ℋ)∣desc(ℋ′))=O(1)K_U(desc(H) (H ))=O(1) meaning that ℋH can be reconstructed from ℋ′H up to a constant description-length overhead and is formalised in the following lemma: Lemma 1(Substrate monotonicity) If ℋ′H refines ℋH, then Ialg(desc(ℋ′):σ())≥Ialg(desc(ℋ):σ())−cUI_alg(desc(H ):σ(C))≥ I_alg(desc(H):σ(C))-c_U, and in particular η′≥η−cUη ≥η-c_U. Proof Conditioning on desc(ℋ′)desc(H ) allows reconstruction of desc(ℋ)desc(H) with O(1)O(1) overhead by the refinement hypothesis, so KU(σ()∣desc(ℋ′))≤KU(σ()∣desc(ℋ))+cUK_U(σ(C) (H ))≤ K_U(σ(C) (H))+c_U by the standard coding argument for conditional prefix complexity. Subtracting both sides from KU(σ())K_U(σ(C)) yields the mutual-information inequality, and the η-inequality follows from (7). Monotonicity is of use because it allows catalytic improvements to accumulate in a controlled way: once a substrate has encoded useful structure, any refinement inherits that structure and can build on it, rather than having to recover it from scratch. We now turn to the central result of the framework, which formalises how much improvement such structure can support in terms of the information it encodes about the task class. 4 The Structural Selectivity Theorem A substrate cannot exploit structure it does not contain. In the same way that a chemical catalyst can only accelerate reactions whose transition states are stabilised by its geometry, a computational substrate can only reduce cost for those aspects of a task class that are reflected in its own structure. Any transferable, class-specific speed-up must therefore arise from information about that class, whether embodied in program text, trained weights, circuit layout, memory organisation or control dynamics. We formalise these conditions via the structural selectivity theorem below, which isolates the class-specific component of speed-up in a universal-search model and separates it from generic implementation improvements. Definition 3(Universal-search cost model) A universal-search cost model for a task class C is a cost function on algorithms that, given access to a substrate description S as conditional input, assigns to each prefix program p a solver cost on instances of size n proportional to 2|p|⋅poly(n)2^|p|·poly(n), and declares p admissible on C when p, conditioned on S, reconstructs enough of σ()σ(C) to select a polynomial-time solver for every ⊆T . Under this definition, generic implementation improvements that do not depend on σ()σ(C) are absorbed into the reference baseline, so that Γ() (T) of Definition 1 measures only the class-specific component. Universal-search models of this kind originate with Levin [25] and provide the natural setting in which the shortest program reconstructing the class structure dominates search cost, with the substrate already encoding part of the structure of σ()σ(C) (supplementary information), so that less additional information is required to specify it (i.e. in the sense of conditional Kolmogorov complexity [33, 26]). Theorem 4.1(Structural selectivity) Let Σcat _cat be an algorithmic catalyst for Σ0 _0 on C and let S:=desc(ℋexec,cat)S:=desc(H_exec,cat). In any universal-search cost model satisfying Definition 3, the class-specific barrier reduction ℬ(Σ0,)−ℬ(Σcat,)=log2Γ()B( _0,T)-B( _cat,T)= _2 (T) from Definition 1 satisfies log2Γ()≤Ialg(desc(ℋexec,cat):σ())+cU=KU(σ())−KU(σ()∣S)+cU. _2 (T)\;≤\;I_alg(desc(H_exec,cat):σ(C))+c_U\;=\;K_U(σ(C))-K_U(σ(C) S)+c_U. (8) Proof Let p∗p^* denote the shortest prefix program that reconstructs σ()σ(C) to the accuracy required by Definition 3 without supplementary information, so that |p∗|=KU(σ())+O(1)|p^*|=K_U(σ(C))+O(1), and let pS∗p^*_S denote the shortest prefix program reconstructing σ()σ(C) with S as conditional input, so that |pS∗|=KU(σ()∣S)+O(1)|p^*_S|=K_U(σ(C) S)+O(1). By the definition of the cost model, any admissible solver selection reduces to emitting such a program, whose dominant multiplicative factor is 2|p∗|2^|p^*| in the absence of side information and 2|pS∗|2^|p^*_S| when S is available. The ratio of the two upper-bounds the class-specific speed-up attributable to S: Γ()≤ 2|p∗|−|pS∗|+O(1)= 2KU(σ())−KU(σ()∣S)+O(1). (T)\;≤\;2^\,|p^*|-|p^*_S|+O(1)\;=\;2^\,K_U(σ(C))-K_U(σ(C) S)+O(1). (9) Taking logarithms and absorbing the O(1)O(1) term into the universal machine constant cUc_U gives (8). Improvements that do not depend on the structure of the task class are treated as part of the baseline, so that Γ measures only the reduction coming from exploiting σ()σ(C) itself. The transfer condition (6) then rules out systems that merely memorise a finite set of instances: such a system may reduce work on a fixed benchmark, but as the class is enlarged it provides no information about how new instances are generated. In that case the substrate does not shorten the description of σ()σ(C), so KU(σ()∣S)=KU(σ())+O(1)K_U(σ(C) S)=K_U(σ(C))+O(1), and the apparent speed-up disappears in the limit. Two immediate consequences of Theorem 4.1 clarify what limits catalytic improvement. Let μ:=Ialg(desc(ℋexec,cat):σ())μ:=I_alg(desc(H_exec,cat):σ(C)) denote how much information the substrate actually carries about the structure of the task class. The structural-information parameter η of Definition 2 cannot exceed this quantity, η≤μη≤μ, so the achievable speed-up is directly constrained by how much of the class structure is already encoded in the substrate. In the regime where solving the class is essentially equivalent to recovering σ()σ(C), this bound is tight up to the universal constant cUc_U. This interpretation makes clear why simple lookup mechanisms fail to qualify as catalysts. As the corollary below shows, a cache (i.e. a finite table storing precomputed input/output pairs) can reduce cost on the stored instances, but it does not encode the underlying structure of the task class. As the class is enlarged, its advantage does not transfer, because it provides no information about how new instances should be solved. By contrast, a genuine catalyst embodies class-level structure and continues to reduce cost across new instances drawn from the same class, just as a chemical catalyst selectively accelerates an entire family of reactions rather than a finite list of outcomes. Corollary 1(Cache non-example) A finite lookup table ℋcacheH_cache storing fixed input-output pairs on a bounded set stored⊆T_stored satisfies lim inf|′|→∞Γ(′)=1 _|T |→∞ (T )=1, and therefore cannot be an algorithmic catalyst for Σ0 _0 on C in the sense of Definition 2. Proof On any ′T with |′∖stored|→∞|T _stored|→∞, the proportion of instances covered by the cache vanishes, so the overall work approaches that of Σ0 _0, giving Γ(′)→1 (T )→ 1. From the information perspective, the description of ℋcacheH_cache encodes only finitely many instance-level answers rather than the class structure σ()σ(C), so KU(σ()∣desc(ℋcache))=KU(σ())−O(1),K_U(σ(C) (H_cache))=K_U(σ(C))-O(1), and hence the mutual information with the class is bounded. By Theorem 4.1, this prevents any unbounded class-level speed-up. 5 Thermodynamic–Informational Coupling Theorem 4.1 is an information-theoretic statement: it limits how much speed-up can be obtained from the structure a catalyst encodes, but does not yet relate this to physical cost. The link to energy comes from the fact that any such structure must have been established in the substrate during adaptation, and writing information into a physical system requires irreversible operations unless that information is already supplied as input. This is the content of the Zurek–Bennett correspondence between algorithmic and thermodynamic entropy [38, 4, 5]: information present in the system reflects work that was done to put it there. To make this precise, let D denote the adaptation input, understood broadly to include training data, design specifications, source code, physical parameters, or any other information available to the adaptation process without additional irreversible work on ℋadapt,catH_adapt,cat. Let S0S_0 denote the initial state of the execution substrate before adaptation, chosen so that KU(σ()∣S0)=KU(σ())+O(1),K_U(σ(C) S_0)=K_U(σ(C))+O(1), so that S0S_0 contains no useful information about the class structure. This ensures that any structural information present after adaptation must have been introduced during the adaptation process itself. Finally, let HeraseH_erase denote the number of logical erasures performed on ℋadapt,catH_adapt,cat during adaptation. The remaining question is how much physical work is required to establish this structure during adaptation. Any information present in the execution substrate after adaptation must come either from the input D or from irreversible operations performed during the process. The following lemma makes this constraint explicit. Lemma 2(Physical erasures lower-bound installed information) Any physical adaptation process on ℋadapt,catH_adapt,cat that takes the pair (S0,)(S_0,D) to a state in which the execution-substrate component has algorithmic mutual information μ with σ()σ(C) satisfies Herase≥μ−Ialg(:σ())−cU.H_erase\;≥\;μ\,-\,I_alg(D:σ(C))\,-\,c_U. (10) Proof Any physical computation with HeraseH_erase logical erasures admits, by Bennett’s reversible simulation theorem [3, 6], a reversible simulation using HeraseH_erase additional bits of advice, i.e. an auxiliary string that records the information lost in those erasures. Let ~ A denote such a reversible simulation of the adaptation process, taking the augmented input (S0,,adv)(S_0,D,adv) with |adv|≤Herase+O(1)|adv|≤ H_erase+O(1) to the augmented output (S,′,hist)(S,D ,hist), where S is the post-adaptation execution-substrate state and histhist records the evolution. Because ~ A is reversible and has constant-size description, the data-processing inequality for algorithmic mutual information [26, 19] gives Ialg(S:σ())≤Ialg((S0,,adv):σ())+O(log),I_alg(S:σ(C))\;≤\;I_alg ((S_0,D,adv):σ(C) )+O( ), (11) since any program computing σ()σ(C) from S can be composed with the inverse of ~ A applied to the full output tuple at a cost of O(1)O(1) program bits. Applying the Kolmogorov chain rule for algorithmic mutual information [26] to the triple on the right: Ialg((S0,,adv):σ()) I_alg ((S_0,D,adv):σ(C) )\; ≤Ialg(S0:σ()) ≤\;I_alg(S_0:σ(C)) +Ialg(:σ()∣S0)+Ialg(adv:σ()∣S0,)+O(log). +I_alg(D:σ(C) S_0)+I_alg(adv:σ(C) S_0,D)+O( ). (12) The first term is O(1)O(1) by the choice of S0S_0; since conditioning on a string carrying only O(1)O(1) information about the target changes mutual information by at most O(log)O( ), the second term satisfies Ialg(:σ()∣S0)≤Ialg(:σ())+O(log)I_alg(D:σ(C) S_0)≤ I_alg(D:σ(C))+O( ); and the third term is bounded above by |adv|+O(1)≤Herase+O(1)|adv|+O(1)≤ H_erase+O(1) because algorithmic mutual information is bounded above by the length of either argument. Collecting logarithmic additive terms into cUc_U, μ=Ialg(S:σ())≤Ialg(:σ())+Herase+cU,μ\;=\;I_alg(S:σ(C))\;≤\;I_alg(D:σ(C))+H_erase+c_U, (13) which rearranges to (10). Lemma 2 provides the link between information and physical cost. It says that if the execution substrate ends up encoding μ bits of information about the task class, that information must have come from somewhere: either it was already present in the adaptation input D, or it was created during adaptation through irreversible operations. In the latter case, the information must be recorded — via the advice bits in the reversible simulation — and each such bit corresponds to at least one logical erasure. Since erasures have a minimum energy cost of c per bit on the adaptation substrate, this places a direct lower bound on the physical work required to install structural information. The following Theorem 5.1 makes this explicit by translating the erasure bound into an energy bound: only the information not already supplied by D must be paid for thermodynamically, and the cost scales linearly with that residual information. Theorem 5.1(Thermodynamic cost of structural information) The adaptation energy on ℋadapt,catH_adapt,cat of any system Σcat _cat with post-adaptation substrate mutual information μ and adaptation input D satisfies Eadapt≥F(ℋadapt,cat)c[μ−Ialg(:σ())−cU]+,E_adapt\;≥\;F(H_adapt,cat)\,c\, [μ\,-\,I_alg(D:σ(C))\,-\,c_U ]_+, (14) where [x]+:=max(x,0)[x]_+:= (x,0). Proof Combine Lemma 2, which shows that at least HeraseH_erase logical erasures are required to install the necessary structural information, with the energy lower bound (1) applied to ℋadapt,catH_adapt,cat, which implies that each such erasure incurs a minimum cost of F(ℋadapt,cat)cF(H_adapt,cat)c. This yields the stated lower bound on EadaptE_adapt. The [⋅]+[·]_+ bracket enforces non-negativity: if the adaptation input D already provides as much (or more) structural information as the catalyst ultimately contains, then no additional work is required to install it. Theorem 5.1 supplies the thermodynamic half of the coupling. The informational half is Theorem 4.1, which relates μ to the logarithmic speed-up. Combining the two yields the central quantitative result. Theorem 5.2(Thermodynamic–informational coupling) Let Σcat _cat be an algorithmic catalyst for Σ0 _0 on C, with class-specific speed-up Γ , per-cycle restoration energy ErestorecycleE_restore^cycle, adaptation input D and adaptation energy EadaptE_adapt on ℋadapt,catH_adapt,cat. Let E0→1E_0→ 1 denote the baseline per-query deployment energy of Σ0 _0 and assume a matched execution-substrate overhead, so that the catalytic per-query deployment energy is E0→1/ΓE_0→ 1/ . Then Eadapt≥F(ℋadapt,cat)c[log2Γ−Ialg(:σ())− 2cU]+,E_adapt\;≥\;F(H_adapt,cat)\,c\, [ _2 \,-\,I_alg(D:σ(C))\,-\,2c_U ]_+, (15) and the deployment break-even count satisfies Ninf∗≥F(ℋadapt,cat)c[log2Γ−Ialg(:σ())−2cU]+E0→1(1−1/Γ)−Erestorecycle,N_inf^*\;≥\; F(H_adapt,cat)\,c\, [ _2 -I_alg(D:σ(C))-2c_U ]_+E_0→ 1(1-1/ )-E_restore^cycle, (16) provided the denominator in (16) is positive; otherwise no break-even horizon exists. Proof Theorem 4.1 gives log2Γ≤μ+cU _2 ≤μ+c_U, so μ≥log2Γ−cUμ≥ _2 -c_U. Substituting this lower bound into (14) of Theorem 5.1 and absorbing the two constants into 2cU2c_U yields (15). The break-even count is obtained by setting the amortised catalytic per-query energy E0→1/Γ+Erestorecycle+Eadapt/NinfE_0→ 1/ +E_restore^cycle+E_adapt/N_inf equal to the baseline per-query energy E0→1E_0→ 1, solving for NinfN_inf, and substituting the lower bound (15) for EadaptE_adapt; the denominator positivity condition expresses that no positive deployment count can amortise a fixed upfront cost when deployment itself does not save energy. Theorem 5.2 makes explicit the central constraint of the watts-per-intelligence framework: the speed-up delivered by a catalyst and the cost of constructing it are tied by the same underlying structure. Theorem 4.1 bounds how much speed-up is possible from the information the substrate carries about the task class, while Theorem 5.1 bounds the physical work required to install that information. Taken together, they show that achieving a logarithmic speed-up log2Γ _2 requires introducing a comparable amount of structural information into the system, unless that information is already supplied by the adaptation input. In physical terms, this information must be written into the substrate, and that process has a minimum energy cost which must be amortised over deployment. A catalyst that promises a speed-up Γ without access to sufficient class-level information in D cannot avoid a proportional adaptation cost, and therefore cannot improve watts-per-intelligence on short deployment horizons. 6 Composition Our algorithmic catalysis framework is intended to explore the construction of complex systems from simpler catalytic components. In chemistry, catalytic pathways are composed by chaining reactions: rate improvements multiply, while the underlying structural constraints interact through shared transition states and intermediates. Our algorithmic analogue follows the same pattern. Catalytic improvements combine across stages, but not independently: each stage inherits and extends the structure encoded by the previous ones, and the total cost must account for both accumulated structure and repeated restoration. The following theorem formalises how such catalytic systems compose within the watts-per-intelligence framework. This suggests that catalytic improvements should combine in a structured way: successive stages can build on previously installed structure, leading to multiplicative gains in efficiency and controlled accumulation of class-specific information. Theorem 6.1(Composition of catalysts) Let Σ0→Σ1→Σ2 _0→ _1→ _2 be a chain of algorithmic catalysts on a common task class C, with stagewise class-specific speed-ups Γ1,Γ2 _1, _2 and structural-information parameters η1,η2 _1, _2, and assume that desc(ℋexec,2)desc(H_exec,2) refines desc(ℋexec,1)desc(H_exec,1) in the sense of Lemma 1. Then the composite system Σ0→Σ2 _0→ _2 satisfies Γ1∘2≥Γ1⋅Γ2,η1∘2≥maxη1,η2−cU, _1 2\;≥\; _1· _2, _1 2\;≥\; \ _1, _2\-c_U, (17) with the stronger additive bound η1∘2≥η1+η2−cU _1 2≥ _1+ _2-c_U holding when the two stages encode algorithmically independent aspects of σ()σ(C), in the sense that Ialg(desc(ℋexec,1):desc(ℋexec,2)∣σ())=O(1)I_alg(desc(H_exec,1):desc(H_exec,2) σ(C))=O(1). The adaptation energy lower bound for the composite is Eadapt1∘2≥F(ℋadapt,2)c[η1∘2−Ialg(tot:σ())−cU]+E_adapt^1 2≥ F(H_adapt,2)c[ _1 2-I_alg(D_tot:σ(C))-c_U]_+, where totD_tot is the concatenated adaptation input of the two stages. Proof Multiplicativity of Γ follows from the definitional identity N(Σ0,)/N(Σ2,)=(N(Σ0,)/N(Σ1,))⋅(N(Σ1,)/N(Σ2,))≥Γ1Γ2N( _0,T)/N( _2,T)=(N( _0,T)/N( _1,T))·(N( _1,T)/N( _2,T))≥ _1 _2 at matched intelligence. The refinement hypothesis and Lemma 1 yield η1∘2≥η1−cU _1 2≥ _1-c_U and η1∘2≥η2−cU _1 2≥ _2-c_U, hence η1∘2≥maxη1,η2−cU _1 2≥ \ _1, _2\-c_U. For the independent case, algorithmic independence of desc(ℋexec,1)desc(H_exec,1) and desc(ℋexec,2)desc(H_exec,2) conditional on σ()σ(C) implies, up to cUc_U, that Ialg(desc(ℋexec,2):σ())≥Ialg(desc(ℋexec,1):σ())+Ialg(desc(ℋexec,2):σ()∣desc(ℋexec,1))I_alg(desc(H_exec,2):σ(C))≥ I_alg(desc(H_exec,1):σ(C))+I_alg(desc(H_exec,2):σ(C) (H_exec,1)) by the algorithmic chain rule, and each term on the right lower-bounds the corresponding ηi _i up to cUc_U. The adaptation-energy bound follows from Theorem 5.1 applied to the composite. The theorem shows that successive catalytic stages can combine to produce a large overall reduction in the effective barrier: each stage builds on the structure established by earlier ones, so that overlapping structure need not be reintroduced. In this case, the gain is multiplicative but the accumulated structural information is limited to what is not already shared across stages. By contrast, when two stages encode different, non-overlapping aspects of the task class, their contributions accumulate additively. This mirrors the chemical case in which distinct enzymes act on different parts of a pathway, each contributing its own selectivity without necessarily interfering with the others. 7 Examples 7.1 Algorithmic catalysis on an affine-SAT class All three conditions of Definition 2 and the coupling bound of Theorem 5.2 can be verified in closed form on a parametrised family of Boolean satisfiability problems. This example is useful because it isolates the role of structure: the task class is defined not by a finite list of instances, but by a shared algebraic constraint that determines all solutions. Let V⊆0,1nV \0,1\^n be an affine subspace of dimension d, and let n,dC_n,d be the class of 33-SAT formulas φ on n variables whose satisfying assignments are exactly the points of V. Equivalently, each instance in the class encodes a different presentation of the same underlying solution structure, namely the subspace V. The canonical class descriptor σ(n,d)σ(C_n,d) therefore captures this shared structure by specifying V as an affine subspace. Concretely, this can be achieved by giving a basis of d vectors in 0,1n\0,1\^n together with a constant offset vector, from which all satisfying assignments can be generated. This representation makes explicit that the class is defined by linear constraints rather than by individual assignments, and yields KU(σ(n,d))=nd+n+O(logn)K_U(σ(C_n,d))=nd+n+O( n) bits up to standard encoding overhead. A reference solver Σ0 _0 for n,dC_n,d performs exhaustive search over 0,1n\0,1\^n, testing all possible assignments, and therefore requires N0=Θ(2n⋅n)N_0= (2^n· n) irreversible operations per instance. This cost arises from treating each instance independently, without exploiting the shared subspace structure encoded by σ(n,d)σ(C_n,d). A catalyst-substrate ℋexec,catH_exec,cat that encodes the basis and offset of V makes this structure explicit. Instead of searching the full space 0,1n\0,1\^n, the solver can enumerate only the points in V, reducing the search to a space of size 2d2^d. This yields Ncat=Θ(2d⋅n)N_cat= (2^d· n) operations per instance and a class-specific speed-up log2Γ=n−d−O(logn). _2 \;=\;n-d-O( n). (18) The reduction reflects the fact that knowing σ(n,d)σ(C_n,d) eliminates the need to explore directions orthogonal to V. Pathway opening follows directly from the strict reduction in N for d<nd<n; matched intelligence holds because both solvers return the same satisfying-assignment set with probability one. Bounded reconfiguration follows because the catalytic substrate is used without modification during deployment: it is only read, not updated, so it remains close to its reference state across cycles. As a result, ΔKcycle=O(1) _K^cycle=O(1) and the associated restoration cost satisfies Erestorecycle=O(c)E_restore^cycle=O(c). Structural selectivity can be verified explicitly in this setting. The substrate description desc(ℋexec,cat)desc(H_exec,cat) contains the basis and offset of V, and therefore already encodes essentially all of the structure captured by σ(n,d)σ(C_n,d). As a result, KU(σ(n,d)∣desc(ℋexec,cat))=O(logn),K_U(σ(C_n,d) (H_exec,cat))=O( n), since only a small amount of additional information is needed to reconstruct the full class descriptor from the substrate. This implies that the mutual information is μ=nd+n−O(logn),μ=nd+n-O( n), and hence the structural-information parameter satisfies η=nd+n−O(logn)η=nd+n-O( n). The transfer condition holds because the speed-up arises from the shared subspace structure: for every ′⊆n,dT _n,d, the solver continues to operate on V, giving Γ(′)=2n−d−O(logn)>1. (T )=2^n-d-O( n)>1. In other words, the advantage does not depend on particular instances but on the underlying structure of the class. Substituting into Theorem 4.1, log2Γ=n−d−O(logn)≤μ+cU=nd+n−O(logn), _2 \;=\;n-d-O( n)\;≤\;μ+c_U\;=\;nd+n-O( n), (19) so the selectivity bound holds with substantial slack whenever d≥1d≥ 1. Intuitively, the substrate contains more information about the subspace V than is strictly needed to achieve the observed speed-up, since eliminating the search directions orthogonal to V requires only n−dn-d bits, whereas the full description of V requires nd+nnd+n bits. The adaptation cost on this class makes the content of Theorem 5.1 explicit. An adaptation input consisting of m uniformly random satisfying assignments from V can be viewed as revealing partial information about the underlying subspace: each additional assignment constrains the space further. The resulting algorithmic mutual information Ialg(:σ(n,d))I_alg(D:σ(C_n,d)) grows approximately linearly in m for m≤d+1m≤ d+1 and saturates at nd+n−O(logn)nd+n-O( n) bits once m≥d+1m≥ d+1, since d+1d+1 generic affine points determine V uniquely. In other words, the training data progressively uncovers the structure of V, until it becomes fully determined. The adaptation-energy lower bound from Theorem 5.1 is therefore Eadapt≥F(ℋadapt,cat)c[nd+n−Ialg(:σ(n,d))−cU]+,E_adapt\;≥\;F(H_adapt,cat)\,c\, [\,nd+n-I_alg(D:σ(C_n,d))-c_U\, ]_+, (20) which vanishes once m≳d+1m d+1, consistent with the physical fact that no additional work is required once the training data fully specifies the structure of the class. For m<d+1m<d+1 training assignments, the adaptation input carries only a partial description of σ(n,d)σ(C_n,d), and the remaining structure must be supplied through irreversible operations on ℋadapt,catH_adapt,cat: a training set of m=d/2m=d/2 random assignments at n=100,d=10n=100,d=10 leaves a residual of approximately n(d−m+1)+n−O(logn)≈700n(d-m+1)+n-O( n)≈ 700 bits, giving Eadapt≳700F(ℋadapt,cat)cE_adapt 700\,F(H_adapt,cat)c. Putting some indicative thermodynamic figures around this, at room temperature c≈2.87×10−21Jc≈ 2.87× 10^-21\,J, and with a contemporary overhead F≈109F≈ 10^9 characteristic of CMOS at the transistor level, the adaptation energy must satisfy Eadapt≳2×10−9JE_adapt 2× 10^-9\,J. The baseline per-query cost of exhaustive search is E0→1∼2n⋅F⋅c≈3.6×1018JE_0→ 1 2^n· F· c≈ 3.6× 10^18\,J at the same overhead, reflecting the need to explore the entire space 0,1n\0,1\^n without structural guidance. This is far beyond any physically realistic energy budget, and illustrates why a catalyst is required to make the class computationally accessible at all. The catalytic per-query cost is E0→1/Γ∼2d⋅F⋅c≈3×10−9JE_0→ 1/ 2^d· F· c≈ 3× 10^-9\,J, roughly matching the adaptation cost, and the break-even horizon of Theorem 5.2 is well below a single deployment query. 7.2 Catalytic computation as a limit Finally, we show how the Buhrman–Cleve–Koucký–Loff–Speelman model of catalytic computation is recovered in a precise limit. Proposition 1(Zero-reconfiguration, structure-free limit) In the regime ΔKcycle=0 _K^cycle=0, η=0η=0, ℋadapt,cat=ℋexec,catH_adapt,cat=H_exec,cat, and σ()σ(C) taken as a constant-length descriptor, Definition 2 reduces to a decision-problem instance of the catalytic computation model: reusable auxiliary state with exact restoration, no structural assumption on its contents, and no thermodynamic cost beyond the Landauer floor. In this regime Theorem 5.2 degenerates to the trivial bound Ninf∗≥0N_inf^*≥ 0. Proof The result follows by inspecting each condition in Definition 2 under the stated limits. Setting ΔKcycle=0 _K^cycle=0 enforces exact restoration, so the execution substrate must return to its initial state after each cycle, recovering the catalytic-tape condition of Buhrman et al. [7]. Setting η=0η=0 removes any requirement that the substrate encode structure of the task class, so the auxiliary state may be arbitrary. Taking σ()σ(C) to have constant length ensures that both KU(σ())K_U(σ(C)) and KU(σ()∣S)K_U(σ(C) S) are O(1)O(1), so the selectivity bound (8) yields log2Γ≤cU _2 ≤ c_U, which does not constrain the speed-up at the level of asymptotic complexity. Applying the universal-search cost model of Definition 3 under these parameter choices recovers the standard catalytic-computation setting with speed-up not constrained by selectivity. Under these conditions, Definition 2 reduces to the standard catalytic computation model: reusable auxiliary state with exact restoration and no structural assumptions. Substituting into Theorem 5.2 then gives Eadapt≥0E_adapt≥ 0, reflecting that, in the absence of structural requirements, the adaptation-cost bound of Theorem 5.2 imposes no non-trivial thermodynamic lower bound. 8 Conclusion In this paper, we have presented a framework for algorithmic catalysis, synthesising catalytic computation with thermodynamic approaches to algorithmic intelligence. Motivated by the role of catalysis in chemistry — where structure renders otherwise inaccessible reaction pathways feasible — and the need for more thermodynamically-efficient algorithmic models of intelligence, we have shown that algorithmic analogues of catalysts arise as reusable computational structures characterised by pathway opening, bounded reconfiguration and structural selectivity. Within this framework, the speed-up a substrate can achieve is limited by how much of the task class structure it captures, and acquiring that structure requires physical work unless it is already provided as input. Taken together, this means that making a class of computations thermodynamically accessible requires first encoding that structure through irreversible operations, and that the cost of doing so must be amortised over deployment. These results contribute to ongoing work on the theoretical and applied thermodynamics of machine intelligence. Future work may examine how effective forms of algorithmic catalysis arise within frontier reasoning models, and the extent to which explicitly designing such structures can improve the thermodynamic efficiency of intelligent algorithms. References [1] W. C. Athas, L. J. Svensson, J. G. Koller, N. Tzartzanis, and E. Y-C. Chou (1994) Low-power digital systems based on adiabatic-switching principles. IEEE Transactions on VLSI Systems 2 (4), p. 398–407. Cited by: §2.1. [2] S. J. Benkovic and S. Hammes-Schiffer (2003) A perspective on enzyme catalysis. Science 301 (5637), p. 1196–1202. Cited by: §1. [3] C. H. Bennett (1973) Logical reversibility of computation. IBM Journal of Research and Development 17 (6), p. 525–532. Cited by: §5. [4] C. H. Bennett (1982) The thermodynamics of computation—a review. International Journal of Theoretical Physics 21 (12), p. 905–940. Cited by: item 2, §2.3, §5. [5] C. H. Bennett (1988) Notes on the history of reversible computation. IBM Journal of Research and Development 32 (1), p. 16–23. Cited by: §2.3, §5. [6] C. H. Bennett (1989) Time/space trade-offs for reversible computation. SIAM Journal on Computing 18 (4), p. 766–776. Cited by: §5. [7] H. Buhrman, R. Cleve, M. Koucký, B. Loff, and F. Speelman (2014) Computing with a full memory: catalytic space. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), p. 857–866. Cited by: §1, §2.2, §7.2. [8] H. Buhrman, M. Koucký, B. Loff, and F. Speelman (2018) Catalytic space: non-determinism and hierarchy. Theory of Computing Systems 62 (1), p. 116–135. Cited by: §2.2. [9] J. Cook and I. Mertz (2024) Tree evaluation is in space O(logn⋅loglogn)O( n· n). In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), p. 1268–1278. Cited by: §2.2. [10] J. Cook and I. Mertz (2025) Tree evaluation is in space O(logn⋅loglogn)O( n· n). SIAM Journal on Computing. Note: Journal version of STOC 2024 Cited by: §2.2. [11] A. Ebtekar and M. Hutter (2025) Foundations of algorithmic thermodynamics. Physical Review E 111 (1), p. 014118. Cited by: §1. [12] A. Ebtekar (2021) Information dynamics and the arrow of time. arXiv:2109.09709. Cited by: §1. [13] M. P. Frank (2005) Introduction to reversible computing: motivation, progress, and challenges. In Proceedings of the 2nd ACM Conference on Computing Frontiers, p. 385–390. Cited by: §2.1. [14] M. Garcia-Viloca, J. Gao, M. Karplus, and D. G. Truhlar (2004) How enzymes work: analysis by modern rate theory and computer simulations. Science 303 (5655), p. 186–195. Cited by: §1. [15] V. Girard, M. Koucký, and P. McKenzie (2015) Nonuniform catalytic space and the direct sum for space. Technical report Technical Report TR15-138, Electronic Colloquium on Computational Complexity (ECCC). External Links: Link Cited by: §2.2. [16] O. Goldreich (2024) Solving tree evaluation in o(logn⋅loglogn)o( n· n) space. Technical report Technical Report TR24-124, Electronic Colloquium on Computational Complexity (ECCC). External Links: Link Cited by: §2.2. [17] S. Goldt and U. Seifert (2017) Stochastic thermodynamics of learning. Physical Review Letters 118 (1), p. 010601. Cited by: §2.3. [18] P. D. Grünwald (2007) The minimum description length principle. MIT Press, Cambridge, MA. Cited by: §2.3. [19] M. Hutter (2004) Universal artificial intelligence: sequential decisions based on algorithmic probability. Springer, Berlin. Cited by: §2.1, §5. [20] D. P. Kingma and M. Welling (2014) Auto-encoding variational Bayes. In Proceedings of the 2nd International Conference on Learning Representations (ICLR 2014), External Links: 1312.6114 Cited by: §2.3. [21] A. N. Kolmogorov (1965) Three approaches to the quantitative definition of information. Problems of Information Transmission 1 (1), p. 1–7. Cited by: §3. [22] M. Koucký (2016) Catalytic computation. Bulletin of the EATCS (118). Cited by: §2.2. [23] K. J. Laidler (1987) Chemical kinetics. 3 edition, Harper and Row, New York. Cited by: §1. [24] S. Legg and M. Hutter (2007) Universal intelligence: a definition of machine intelligence. Minds and Machines 17 (4), p. 391–444. Cited by: §2.1. [25] L. A. Levin (1984) Randomness conservation inequalities; information and independence in mathematical theories. Information and Control 61 (1), p. 15–37. Cited by: §3, §4. [26] M. Li and P. M. B. Vitányi (2019) An introduction to Kolmogorov complexity and its applications. 4th edition, Springer. Cited by: §3, §4, §5, §5. [27] D. A. McAllester (1999) PAC-Bayesian model averaging. Machine Learning 37, p. 355–363. Cited by: §2.3. [28] J. M. R. Parrondo, J. M. Horowitz, and T. Sagawa (2015) Thermodynamics of information. Nature Physics 11 (2), p. 131–139. Cited by: §2.3. [29] E. Perrier (2025) Watts-per-intelligence: Part I (energy efficiency). In International Conference on Artificial General Intelligence, Lecture Notes in Computer Science, Vol. 16058, p. 46–57. Cited by: §1, §1, §2.1, §2.1. [30] E. Pyne (2024) Derandomizing logspace with a small shared hard drive. In Proceedings of the 39th Computational Complexity Conference (C 2024), LIPIcs, Vol. 300, p. 4:1–4:20. Note: Preliminary version: ECCC TR23-168 (2023) Cited by: §2.2. [31] D. J. Rezende, S. Mohamed, and D. Wierstra (2014) Stochastic backpropagation and approximate inference in deep generative models. In Proceedings of the 31st International Conference on Machine Learning (ICML 2014), p. 1278–1286. Cited by: §2.3. [32] J. Rissanen (1978) Modeling by shortest data description. Automatica 14 (5), p. 465–471. Cited by: §2.3. [33] R. J. Solomonoff (1964) A formal theory of inductive inference. Information and Control 7 (1–2), p. 1–22, 224–254. Cited by: §3, §4. [34] S. Still, D. A. Sivak, A. J. Bell, and G. E. Crooks (2012) Thermodynamics of prediction. Physical Review Letters 109 (12), p. 120604. Cited by: §2.3. [35] A. Stuhlmüller, J. Taylor, and N. D. Goodman (2013) Learning stochastic inverses. In Advances in Neural Information Processing Systems 26 (NeurIPS 2013), p. 3048–3056. Cited by: §2.3. [36] R. Wolfenden and M. J. Snider (2001) The depth of chemical time and the power of enzymes as catalysts. Accounts of Chemical Research 34 (12), p. 938–945. Cited by: §1. [37] D. H. Wolpert (2019) The stochastic thermodynamics of computation. Journal of Physics A: Mathematical and Theoretical 52 (19), p. 193001. Cited by: §2.3. [38] W. H. Zurek (1989) Algorithmic randomness and physical entropy. Physical Review A 40 (8), p. 4731–4751. Cited by: item 2, §2.3, §5.