What is a pattern in statistical mechanics? Formalizing structure and patterns in one-dimensional spin lattice models with computational mechanics

What is a pattern in statistical mechanics? Formalizing structure and patterns in one-dimensional spin lattice models with computational mechanics Omar Aguilar∗ Physics Department, University of California, Santa Cruz, CA (Dated: October 15, 2025) This work formalizes the notions of structure and pattern for three distinct one-dimensional spin-lattice models (finite-range Ising, solid-on-solid and three-body), using informationand computation-theoretic methods. We begin by presenting a novel derivation of the Boltzmann distribution for finite one-dimensional spin configurations embedded in infinite ones. We next recast this distribution as a stochastic process, which lets us analyze each spin-lattice model with the theory of computational mechanics. In this framework, the process’ structure is quantified by excess entropy E(predictable information) and statistical complexity Cµ(stored information), and the process’ structure-generating mechanism is specified by its ϵ-machine. To assess compatibility with statistical mechanics, we compare the configurations jointly determined by the information measures and ϵ-machines to typical configurations drawn from the Boltzmann distribution, and we find agreement. We also include a self-contained primer on computational mechanics and provide code implementing the information measures and spin-model distributions. I. INTRODUCTION When observing a natural system, we intuitively explain it by describing the way its components are arranged. We might say that the system displays order or randomness. We might describe systems that exhibit a blending of order and randomness as complex or structured1[1]. Moreover, we might also regard as structured those ordered systems that have no randomness but exhibit a repetition of more than one component (a period greater than 1) [2]. Altogether, we might regard a structured system simply as one that exhibits patterns [3]. In light of this depiction, a physicist may feel compelled to bring clarity and definiteness to the notions of randomness, structure and pattern by formalizing them. Although statistical mechanics readily concretizes randomness through measures like entropy [4, 5], it falls short when quantifying structure and pattern and formalizing its supporting mechanism. For instance, while magnetization is commonly treated as an indicator of structure, materials with distinct magnetic behaviors, such as paramagnets and antiferromagnets, have the same magnetization in the absence of a magnetic field: zero [2]. Faced with these limitations, the physicist may make their endeavor more concrete by posing two key questions: 1. What’s a simple system in statistical mechanics that manifests structure and patterns? ∗[email protected] 1This paper uses two notions of structure. One refers to a system’s general type of arrangement, which we call generic structure. The other captures a more specific type of arrangement—one that exhibits patterns—which we call intrinsic structure. Throughout the paper, the intended notion will be clear from context. 2. How could one extend statistical mechanics to formalize structure and patterns within such a system? One-dimensional (1D) spin lattice models [6] (p. 67) are suitable candidates for addressing these challenges, as they compactly represent interacting magnets as spins in an evenly spaced grid, embodying both simplicity [7] and structure/patterns [8]. The simplicity stems from the spins taking discrete values (often binary) and the spin models being amenable to both analytical and numerical treatment [9, 10]. The structure and patterns are evident in the model’s possible spin configurations, which exhibit regularity, randomness and structure. For example, the 1D nearest-neighbor Ising model may have configurations rich in regularity, randomness and structure such as: ↑↓↑↓↑↓,↑↓↑↓↓↓↑ and ↓↑↑↓↑↑, respectively. These configurations contain repeating sequences of spins that we refer to as configuration patterns. Mathematically, a spin model is expressed as a Hamiltonian that characterizes the energy of the spin system [6] (p. 67). Given the Hamiltonian, the usual goal is to determine the partition function and from it compute various properties of interest [11]. Among these, the Boltzmann distribution as a function of spin configurations is the least frequently computed2, yet it stands out as the sole one directly addressing spin configurations, serving as a window for analyzing their structure and patterns. However, to clearly see through this window, we need to carefully consider how the distribution is formalized. Typically, the Boltzmann distribution is defined so that each configuration, either implicitly or explicitly, 2When the Boltzmann distribution is calculated, it is typically expressed as a function of energy [12, 13] or other macroscopic properties [14–16], rather than directly in terms of configurations of fixed length 2 represents an event of a single random variable, as indicated in Refs. [17] (p. 552) and [18]. Nonetheless, this approach is not conducive to examining how individual spins make up spin configurations. Instead, we can regard them as realizations of a partially ordered chain of random variables—a stochastic process [2]. In this process, which we call the spin process, each spin corresponds to an event of a single random variable. Given this perspective, we can now quantify the randomness, regularity, and structure of the spin process, and formalize the mechanism that generates its structure. Since randomness, regularity, and structure are ways in which a process elicits surprise, we quantify them as information—a measure of “quantifiable surprise” [19] (p. 64) or a “difference that makes a difference” [20]. In information theory, the theory of quantifiable surprise, a stochastic process’ intrinsic randomness or average randomness per symbol is quantified by its Shannon entropy rate hµ(Ref. [21], pp. 74-76). The process’s regularity, as the counterpart of its randomness, can be understood as the total correlation within the process. Thus, regularity is quantified as the amount of information that is shared within the process—that is, the process’ mutual information or excess entropy E[22–25]. Because a stochastic process’s structure is effectively captured by its patterns, we quantify the process’s structure by measuring the amount of information stored in those patterns. This quantity is known as the stored information, or statistical complexity Cµ[26, 27], and is defined as the Shannon entropy of those patterns. Calculating Cµtherefore requires identifying these patterns—an inference task that effectively uncovers the process’s underlying structure-generating mechanism. We define these patterns next. Since patterns are sought for their predictive utility, we define a pattern in the spin process setup from a prediction-based viewpoint. To do so, we split3each realization of the spin process into a left half (past) and a right half (future). Then, we define a pattern as the set of pasts that lead to the same futures4[28]. By “lead to” we mean that the conditional distribution over futures, when conditioned on any past in the set, is identical across all those pasts. This condition is known as the causal equivalence principle5[27–29], which recasts these patterns as causal states. Why the term “state”? Because this conception of pattern is consistent with theory of computation’s definition of state as a system’s entity that “remembers a relevant portion of the system’s his3Without loss of generality 4It should be highlighted that for 1D spin lattice models, the conventional time index is taken to be site location index and there is no time dependence. 5This principle formalizes the implicit definition of a state commonly used in theoretical computer science when constructing machines. In this context, a state represents the information that must be retained to predict the system’s future behavior (see Appendix A). tory” [30] (pp. 2-3). This connection points us toward the mechanism that underpins the process’s structure. Given that a system’s structure is measured in units of information, formalizing its supporting mechanism is tantamount to unraveling how the system processes and stores information—essentially, how it computes [31]. This leads to a refined question: what is the minimal6 abstract machine7that performs the computation inherent to the spin process? Leveraging concepts from TOC, computational mechanics provides a compelling response: the set of causal states and their transitions, that is a ϵ-machine or Probabilistic Deterministic Finite State Machine (PDFM). Here, “probabilistic” means that state transitions include probabilities, while “deterministic” implies that when we have knowledge of a state and its associated outgoing symbol, we have complete certainty about the next state we will transition to. Several methods have been developed for inferring ϵ-machines [32– 38]. Among these, Feldman and Crutchfield’s approach stands out as the only one that is both analytical and applicable to statistical mechanics [2]. In particular, Feldman and Crutchfield used this method to examine the structure of the nearest-neighbor and next-nearest neighbor Ising models. Subsequent research further developed their information-theoretic analysis of spin systems by calculating hµand Efor the two-dimensional nearest neighbor Ising model [39], as well as decomposing the nn Ising model’s Shannon entropy rate into more refined information components [40]. Moreover, quantum ϵ-machine formulations revealed striking memory advantages—ranging from extreme compression when simulating long-range Ising spin chains [41] to clarifying how simplicity differs in quantum versus classical descriptions [42]. Now, the aim of this paper is to develop information measures and ϵ-machines for three varied one-dimensional spinlattice models—finite-range Ising, solid-on-solid, and three-body—and to assess the consistency of these results with statistical mechanics. These developments are timely because they broaden the rapidly evolving landscape of abstract machines used to analyze computation in physical processes in two key ways. First, they encourage the application of abstract machines—which have most often been used to study thermodynamic [43–46] and quantum [47–50] processes—to statistical mechanical processes, potentially supporting more efficient information processing in materials. Second, these developments foster the use of abstract machines that are systematically inferred from 6To avoid accounting for computation not inherent to our system 7In the 21st century, “computation” often evokes laptops, which perform useful computation—that is, computation carried out for some external task. In contrast, we focus on intrinsic computation, the computation a system performs by itself. To analyze this, we use abstract machines [30]—mathematical models that consist of states and transitions and laid the groundwork for theory of computation. 3 data, rather than being designed in an ad hoc manner, as has more typically been the case. To achieve the aim of this paper, we provide a pedagogical explanation of computational mechanics’ application to the nn and nnn Ising models, along with the necessary background from statistical mechanics, measure theory, stochastic processes, and information theory. We then apply these techniques to a wider range of spin models such as finite range Ising models, solid-on-solid models, and three-body models. In parallel, we find that the typical patterns observed in these spin models at various parameter values match those predicted by information measures and ϵ-machines. This allows us to present an account of spin patterns clearly consistent with statistical mechanics and information/computation theory. II. BACKGROUND A. Spin measurements: Boltzmann distribution of finite chain embedded in infinite chain The Boltzmann distribution serves as an entry point for probing the structure of spin models; however, defining it for both finite and infinite configurations introduces significant difficulties. For finite configurations, the Boltzmann distribution lacks generality and often relies on numerical simulations for approximation [51–53]. For infinite configurations, a different issue arises: their probability is zero [54] (pp. 94-97). This defies our expectation of them occurring and results in an unnormalized total probability—a sum that is zero instead of one. To balance the constructiveness of finite configurations with the generality of infinite ones, we examine a hybrid configuration: a finite spin configuration embedded in an infinite one [55]. Figure 1 illustrates the finite configuration embedded within the infinite one. The key equations leading to the embedded distribution are presented below, with detailed derivations provided in Appendices F, G, H and I. Fig. 1. Depiction of a finite spin configuration embedded within an infinite spin configuration with periodic boundary conditions Consider a configuration consisting of Nspins, where each spin can take one of two values (↑or ↓) and interacts only with its nearest neighbors. For convenience, the configuration is subject to periodic boundary conditions: s0. . . sN−1where s0=sN(1) The system is governed by a translationally-invariant Hamiltonian, that is, a Hamiltonian whose form remains the same across spin sites. It is defined as: E(si, si+1) = −Jsisi+1 −B 2(si+si+1) (2) Next, the corresponding transfer matrix, with components V(si, si+1) = e−βE(sisi+1), is expressed as [6] (p. 68): V=e−βE(↑,↑)e−βE(↓,↑) e−βE(↑,↓)e−βE(↓,↓)(3) Then, the probability distribution for this spin configuration in the thermodynamic limit N→ ∞ is obtained in terms of the transfer matrix components and the transfer matrix’s principal eigenvalue λ[6] (pp. 68-69): Pr(s0,...sN−1) = N−1 Q i=0 V(si, si+1) λN(4) Now, consider a specific finite configuration of length Lembedded in an infinite one −→ s=s0. . . sL−1where L<N (5) Although the principal eigenvectors of the transfer matrix are seldom calculated in studies of spin models, they play a crucial role in defining the embedded distribution. Therefore, we obtain the normalized principal left and right eigenvectors of the transfer matrix, as provided in Ref. [6] (pp. 72-73). For conciseness, these are expressed in terms of the magnetization m, as shown below: uL=r1 + m 2r1−m 2and uR=    r1 + m 2 r1−m 2     (6) Notice that for the nn Ising model, the left and right eigenvectors are identical. Hence, in all subsequent subsections of this section, we omit the left and right superscripts. Lastly, the probability distribution for the embedded configuration [55] is given by Pr(−→ s) = uL s0uR sL−1 L−2 Q i=0 V(si, si+1) λL−1(7) Here, we provide the physical interpretation for each part of the equation: •In the denominator, λis raised to L−1 as each embedded configuration has Lspins and its boundaries are not periodic. •In the numerator, the product of transfer matrix components consists of L−1 factors. This reflects the fact that only the spins within the bulk have neighboring spins to interact with on both their left and right sides. 4 •Also in the numerator, we include two extra terms: uL s0and uR sL−1, which are the normalized principal eigenvector components associated with the boundary spins s0and sL−1. Since the embedded configuration does not have periodic boundaries, these extra terms ensure that the boundary spins contribute to the system’s magnetization as much as the bulk spins. Moreover, these terms are key for normalizing the joint probabilities. To facilitate later discussion, it will be useful to denote the component associated with spins ↑or ↓as u↑, and u↓, respectively. The values of these components correspond to either uL s0or uR sL−1, depending on whether the orientations of the spins s0and s−1are up or down. For example, in a spin configuration like ↓↑↑↑, the component for the first spin s0is uL s0=u↓=q1−m 2, while the component for the last spin s3is uR s3=u↑=q1+m 2. Alternatively, equation (7) can be interpreted as the probability measure of a coarse-grained configuration. The nature of this coarse-graining and its implementation, which relies on measure theory, will be discussed in the following section. B. Coarse-graining via measure theory In this section, we view finite configurations embedded within infinite ones as coarse-grained versions of infinite spin configurations. Here, “coarse-grained” means a simplified representation that retains essential features while reducing detail [56]. The procedure for arriving at these representations—that is, coarse-graining—is up to the scientist’s discretion [57]. However, when treating the spin model as a stochastic process, the conventional approach is to reduce the degrees of freedom such that only contiguous ones remain [58–60]. This coarse-graining is physically motivated by the observer’s inability to record infinite measurements or degrees of freedom. To define the set of coarse-grained configurations mathematically, we begin with the full set of possible configurations. Consider the set of all possible infinite spin configurations Ω. An individual configuration in this set is represented as σ∈Ω. The degree of freedom at lattice site i within a configuration σis denoted by σi. Thus, a configuration in terms of its degrees of freedom is given by σ=σ0. . . σN−1 with σ0=σNand N→ ∞ The set of coarse-grained configurations ΩCis defined as the set of infinite configurations in which the contiguous spins from σ0to σL−1have fixed indices and can take any value from {−1,1}. This can be expressed as ΩC={σ∈Ω|σ0, . . . , σL−1have fixed indices} Alternatively, the set of coarse-grained configurations can be defined as ΩC={C1, C2, . . .} with each coarse-grained configuration Cjdefined as Cj={σ∈Ω|σ0=s0, . . . , σL−1=sL−1} where s0, . . . , sL−1represent the fixed spin values at fixed indices 0, . . . , L −1. In more compact notation, this is written as: Cj={σ∈Ω|σL=sL} Fig. 2. Graphical representation of coarse–grained Ising phase space. Only the purple spins are assigned fixed indices. For clarity, down spins ↓are represented as 0 instead of −1. Notably, the act of coarse-graining changes our focus from individual configurations to sets, where each set Cj groups configurations by their shared spin values. Fig. 2, shows how the set of all possible infinite spin configurations Ω is partitioned into the set of coarse-grained configurations ΩC. Accordingly, we must adapt our notion of probability to match this perspective, transitioning from the concept of a probability distribution to that of a probability measure, denoted by µ[61] (pp. 331336). To formalize this, we introduce the concept of a sigma algebra, denoted by A. This is a collection of all subsets 5 of ΩCthat can be consistently assigned probabilities or measured, meaning they are physically relevant. The sigma algebra Ahas three key properties: 1. Entire Set Containment: Aincludes the sample space. In this case, that is the coarse-grained set of all infinite configurations ΩC: ΩC∈ A 2. Complement Closure: If a set Ais in A, then its complement ΩC\Amust also be in A: A∈ A =⇒ΩC\A∈ A 3. Countable Union Closure: If A1, A2, A3, . . . are in A, then their countable union is also in A: A1, A2,· · · ∈ A =⇒ ∞ [ i=1 Ai∈ A With the concept of a sigma algebra established, we can now turn to the probability measure. This measure is analogous to a probability distribution, but applies to sets rather than individual outcomes. It extends the key constructive properties of probability distributions—namely, nonnegativity, normalization and additivity—from finite to infinite configurations. The probability measure is formalized as a function µ:A → [0,1] that assigns a probability to each event in Aand satisfies the following three key properties: 1. Nonnegativity: In the same way that joint probabilities for finite configurations are never negative, the probability measure assigned to any set in A must also be nonnegative. µ(A)≥0 for every A∈ A. 2. Normalization: Similar to the sum of joint probabilities for all configurations equaling 1, the probability measure for the entire sample space, the set of coarse-grained configurations ΩC, must be 1. µ(ΩC) = 1 3. Countable addivity: Mirroring the additivity of joint probabilities, which asserts that the total probability of finite configurations equals the sum of their individual probabilities, probability measures demonstrate countable additivity. This property dictates that for any countable collection of non-overlapping sets (cylinder sets) {Ai}∞ i=1, the probability of their union is the sum of the probabilities of the individual sets: µ ∞ [ i=1 Ai!= ∞ X i=1 µ(Ai) where each Aiis a cylinder set corresponding to a coarse-grained configuration, and the union represents the combined event of these configurations. The last step in constructing the spin probability measure involves assigning each spin cylinder set’s probability measure the value of its associated embedded configuration’s probability. Notably, information measures in later sections are denoted with a µsubscript, indicating that their argument is a probability measure [2]. C. System and measurements: Stochastic Processes As mentioned in the introduction, we interpret configurations as realizations of a stochastic process. This section aims to delve further into this formalism by first explaining the reasons for departing from the conventional approach. Traditionally, a spin configuration is represented as an event sof a random variable S. For example, a configuration with all spins pointing up is depicted as: s=. . . ↑↑↑ . . . (8) However, this formalism impedes a direct examination of individual spins and their interactions. Furthermore, it leads to an unwieldy number of possible events. To address these issues, we adopt a more nuanced approach. Instead of representing a configuration as a single event, we depict it as a specific realization of events: ←→ s=. . . s−1s0s1. . . (9) This realization is an instance of a stochastic process, i.e., a partially-ordered chain of random variables: ←→ S=. . . S−1S0S1. . . (10) whose associated probability distribution is given by Pr (. . . S−1S0S1. . .) (11) Within this framework, the all-ups spin configuration is now denoted as: ←→ s=. . . ↑↑↑↑ . . . (12) Without loss of generality, we can split a process into two parts: the past process, defined as ←− S=. . . S−1(13) 6 along with its associated past realization, and the future process, defined as −→ S=S0. . . (14) along with its associated future realization. For simplicity, we will use the terms “past” and “future” to refer to both processes and their associated realizations, with the specific meaning inferred from the context. The spin stochastic process will be our object of study. In the following subsection, we will elaborate on how it relates to broader categories of processes, as seen in Ref. [62]. 1. Types of processes a. Stationary process A process in which the statistical properties of its random variables remain invariant over time. These properties include but are not limited to mean, variance, or joint distribution. b. Strictly stationary process A process whose joint distribution remains invariant under shifts in time. In other words, a process whose random variables are timetranslation invariant. That is, a process that satisfies: Pr (StSt+1 . . . St+L−1) = Pr (S0S1. . . SL−1) (15) c. Markovian process A process in which the probability distribution of the next random variable depends only on the preceding one. That is, a process whose joint distribution factors as follows: Pr(↔ S) = . . . Pr (Si|Si−1) Pr (Si+1 |Si). . . (16) d. R-order Markovian process A process in which the probability distribution of the next random variable depends only on the Rpreceding ones. That is, a process whose joint distribution is given as follows: Pr(↔ S) = . . . Pr (Si|Si−R, . . . , Si−1). . . (17) e. Spin process A process whose associated probability distribution is generated by a spin Hamiltonian model. For the models considered in this work (finiterange Ising, Solid on solid and Three body models), this process is strictly stationary and Markovian or R-order Markovian. We can now define information measures of randomness, regularity and structure for a stochastic process, starting from the basics of information theory. D. Information measures What is information? Information can be conceived as quantifiable surprise, defined in terms of probabilities [19] (p. 64). Through this lens, an event sthat is not likely to occur is deemed surprising, thus carrying high informational content. This means that the information of an event H(s) is inversely proportional to its probability, that is, H(s)∝1 p(s). More specifically, the event’s information content—termed self-information—[19] (p. 64) is defined as H(s) = −log2p(s) (18) Here, the presence of the logarithm is a convenient guarantee that the self-information possesses the additive property [63]. That is, the total surprise from combining events 1 and 2 equals the sum of their individual surprises. The natural next step is to consider a random variable S. Its information content is known as Shannon entropy. It is defined as the weighted sum of the self-information of each possible event within the variable. Mathematically, it is expressed as H(S) = −X s=±1 log2p(s) (19) Following this line of reasoning, we can define the conditional entropy (Refs. [63]; [21], p. 17) as the amount of information needed to specify a random variable S1 given that a random variable S0is known. H(S1|S0) = −X s0,s1=±1 Pr(s0, s1) log2Pr(s1|s0) (20) Moreover, we can define the joint entropy (Ref. [63]; Ref. [21], pp. 16-17) as the amount of information contained in two random variables. H(S0, S1) = −X s0,s1=±1 Pr(s0, s1) log2Pr(s0, s1) (21) Now, how may we define the entropy of our object of interest, that is, the stochastic process? The simplest answer would be to consider the growth entropy [64], that is, the Shannon entropy of the entire process. H(SL) = −X s0=±1 . . . X sL−1=±1 Pr(sL) log2Pr(sL) (22) However, as the length of the process increases, the growth entropy also rises and ultimately diverges when the process extends towards infinity (L→ ∞). This raises the question: how can we capture the total information of a stochastic process? A solution lies in the Shannon entropy rate (Ref. [64]; Ref. [21], pp. 74-76) defined as hµ= lim L→∞ H(SL) L(23) Again, the symbol µsignifies that the Shannon entropy rate is calculated in terms of a probability measure. Notably, this rate can be simplified for processes that are 7 both stationary and Markovian, like the spin process. For a stationary process, the entropy rate reduces to hµ=H(SL|SL−1, . . . , S1) (24) If the process is also Markovian, it becomes hµ=H(S0|S−1) (25) By recasting the Shannon entropy rate as a conditional entropy, we can understand it as the amount of surprise each spin contributes. This effectively measures the process’s randomness per spin. Furthermore, for one-dimensional spin models, the Shannon entropy rate matches the Boltzmann entropy density, the more familiar form of entropy in statistical mechanics, as shown in Appendix C. Since the regularity of the spin process is interpreted as the information shared between the process’ past and future, the regularity is defined as the process’ mutual information or excess entropy [22–25]. Mathematically, it is defined for the spin process as follows: E=I(←− S;−→ S) = I(S−1;S0) (26) Therefore, E=X s−1,s0=±1 Pr(s−1, s0) log2Pr(s−1, s0) Pr(s−1)Pr(s0)(27) Notably, the excess entropy Ecan be interpreted as predictable information. That is, it quantifies the amount of information an observer has for recognizing configuration patterns, even if that information is not enough to identify them. However, in the absence of entropy rate hµ,Eis sufficient to determine how much information is required for the observer to achieve synchronization with the underlying configuration patterns. Synchronization, from this purely information-theoretic perspective, refers to the observer’s ability to recognize and discern these configuration patterns. To measure the process’ structure or statistical complexity, we need to determine the asymptotic probabilities of its patterns or causal states S. In general, this often requires inferring the process’s ϵ-machine, especially for non-Markovian processes [65] (p. 37). However, for the spin process, we can calculate them directly since we have a natural definition of causal states. Given the Markovian nature of the spin process, the next spin only depends on the previous one. Thus, the probability distribution of future spins conditioned on past ones, matches the probability distribution of the future conditioned on the previous spin being up or down. Now, since the probability of a spin up and the probability of a spin down add up to 1, and they represent the probability per site throughout the process, they can be interpreted as the asymptotic probabilities of the causal states. Therefore, the statistical complexity of the spin process can be quantified as [2] Cµ=H(“patterns”) = H(S) = H(S0) (28) Therefore, Cµ=−X s0=±1 Pr(s0) log2Pr(s0) =−X s0=±1 (uL s0uR s0) log2(uL s0uR s0) =−X s0=±1 u2 s0log2u2 s0 (29) These information measures can be simply related via the identity H(S0) = H(S0|S−1) + I(S−1, S0) as Cµ=Rhµ+E(30) This relationship [65] (p. 37) formalizes our intuition that structure is a blending of randomness and regularity. Here, Rdenotes the neighborhood radius, which equals 1 for the nn Ising model. Since the causal states are sufficient to predict the process’s future, and considering that prediction is tantamount to reproduction, statistical complexity can be defined as the minimum amount of information required to reproduce the stochastic process [2]. As mentioned in the introduction, if structure is viewed as quantifiable information, then this suggests that the mechanism generating the structure can be described as a machine [28, 31]. E. Structure: Computational mechanics To formalize the mechanism generating a physical process’ structure, the concept of machine must be adapted to satisfy three statistical mechanical constraints: 1. Be capable of reproducing ensembles 2. Possess a well-defined notion of “state” 3. Be derivable from first principles Computational mechanics meets the first requirement by enhancing the simplest machine in TOC, the Deterministic Finite State Machine (DFSM), with probabilistic features while keeping its determinism intact [29, 66]. The former is achieved by incorporating probabilities into the state transitions, and the latter is maintained by ensuring that the probability of transitioning to the next state, given the current state and a specific outgoing symbol, is precisely one. These modifications result in a machine known as Probabilistic Finite State Machine (PDFM) or ϵ-machine. The second requirement is fulfilled by operationalizing TOC’s conceptual definition of a state—an entity that “remembers a relevant portion of the system’s history” [30] (pp. 2-3)—as a causal state. A causal state is the collection of all past realizations that when individually conditioning the process’ future yield the same conditional probability distribution [28, 29]. Notably, formalizing the 8 notion of “state” is crucial not just for conceptual clarity, but also to satisfy the third requirement. The reason for this is that without a clear understanding of what states are, the procedure for inferring them is much less clear. To satisfy the third condition, we recast the definition of causal state as a guiding principle for inferring causal states from realizations, that is, the causal equivalence principle [28, 29]. It dictates that two past realizations belong to the same causal state if they lead to the same conditional distributions over process’ futures. In practice, this principle allows us to construct the underlying ϵ-machine of an ensemble. In summary, the key ingredients of computational mechanics are the concepts of ϵ-machine, causal transition, causal state, and the causal equivalence principle [29]. While we introduced them in this order to capture how they would be re-discovered conceptually, we will now present them in reverse order to delve into their mathematical details more pedagogically. Causal equivalence principle. Two pasts are considered causally equivalent if and only if they make the same prediction over the future, i.e. ← s∼← s′⇐⇒ Pr(→ S|← s) = Pr(→ S|← s′) (31) Effectively, this principle groups pasts that lead to the same future into what are known as causal states. To formalize what we mean by “leads,” a causal state is defined as Causal state. A triple that contains 1. An event with its associated probability of the causal state random variable S: Siand Pr(Si) (32) 2. A distribution of the future conditioned on the causal event, i.e., a morph: Mi= Pr(→ s|Si) (33) 3. The set of histories that lead to the same morph: Hi={← s|Pr(→ S|Si) = Pr(→ S|← s)}(34) Now, assuming that our machine is deterministic in the computation theoretic sense, we can define the causal transition as Causal transition. The probability of transitioning from state Sito state Sjwhile emitting the symbol s∈ A T(s) ij = Pr(Sj, s|Si) = Pr(Sj|s, Si)Pr(s|Si) = Pr(s|Si) (35) These definitions allows us to construct the minimal machine supporting a stochastic process’ structure. ϵ-machine or PDFM. A pair that contains 1. The set of causal states 2. Transition dynamic (causal transitions gathered in a matrix) [27] For inferring ϵ-machines, it will be important to distinguish between two types of causal states: •Recurrent causal states: These are states to which the machine will repeatedly transition as it operates. Consequently, their asymptotic probability is non-zero. •Transient causal states: These are states that the machine may reach temporarily but will not return to. As a result, their asymptotic probability is zero: Pr(Si) = 0. Notably, the connectivity and number of transient states specify how difficult it is to identify the periodicity of configurations. In other words, these transient states reflect the computational effort required to achieve synchronization with the recurrent causal states. Here, synchronization is recast as the observer achieving certainty about the recurrent causal state it occupies, even in systems with nonzero entropy rate hµ. Thus, transient states offer a computational perspective on synchronization, which completes the informational interpretation provided by the excess entropy E. Since this is a principled approach, we can infer our machine of interest, rather than design it. For spin processes, an analytical method exists for inferring recurrent causal states [2]. Moreover, transient states can be reconstructed from these recurrent states, as detailed in Appendix B of Ref. [2]. Below, we provide a step-by-step explanation of the analytical reconstruction method for recurrent causal states. 1. Analytical method to infer ϵ-machines 1. Consider a finite configuration of length 2Lembedded in an infinite one. ←→ s=s−L. . . s−1s0s1. . . sL−1 2. Consider the joint probability of the embedded finite configuration. Pr(←→ s) = uL s−LuR sL−1 L−2 Q i=−L Vsisi+1 λ2L−1(36) 9 3. Compute the conditional probability of the right half of the configuration given the left half. Pr(→ s|← s) = uR sL−1 uR s−1 L−2 Q i=−1 Vsisi+1 λL 4. Notice that the only past element the conditional probability depends on is its last spin s−1. Thus, the conditional probability is Markovian. Pr(→ s|← s) = Pr(→ s|last spin) 5. Identify morphs. Pr(→ s|SA) = Pr(→ s|pasts whose last spin is ↑) Pr(→ s|SB) = Pr(→ s|pasts whose last spin is ↓) 6. Identify the number of causal states. Since there are two morphs, there are two causal states at most 7. Identify sets of histories that lead to the same morph. {← s|last spin is ↑} and {← s|last spin is ↓} 8. Apply definition of causal transitions. T(↑) AA = Pr(↑|↑) = eβ(J+B) λ T(↓) AB = Pr(↓|↑) = e−βJ λr1−m 1 + m T(↓) BB = Pr(↓|↓) = eβ(J−B) λ T(↑) BA = Pr(↑|↓) = e−βJ λr1 + m 1−m 9. Calculate asymptotic causal state probabilities using two facts: •Pr(→ s|SA) = Pr(→ s| ↑) •Pr(→ s|SB) = Pr(→ s| ↓) •Pr(SA) + Pr(SB)=1 Since Pr(↑) + Pr(↓) = 1, by inspection, we have •Pr(SA) = Pr(↑) = u2 ↑=1 + m 2 •Pr(SB) = Pr(↓) = u2 ↓=1−m 2 10. Build transition dynamic T. T=  0 Pr(SA) Pr(SB) 0 Pr(SA|SA) Pr(SB|SA) 0 Pr(SA|SB) Pr(SB|SB)  =    01+m 2 1−m 2 0eβ(J+B) λ e−βJ λq1−m 1+m 0e−βJ λq1+m 1−m eβ(J−B) λ     11. Find left eigenvector using ⟨π|T=⟨π|. ⟨π|= (0,1 + m 2,1−m 2) Since Tis a stochastic matrix, this is its asymptotic probability distribution vector, which contains the causal states’ probabilities, as seen in Refs. [61] (p. 330); [67]; [68] (p. 128). 12. Build HMM representation of ϵ-machine using the transition matrix T. Details of the resulting machine, for the parameter values J1= 1.0, B= 0.35, and T= 1.5, are provided in Appendix E. F. Patterns as ϵ-machines The following example illustrates how computational mechanics formalizes the concept of a pattern. Consider a spin configuration such as ↑↓↑↓↑↓. When asked, “What’s the pattern in this configuration?”, an intuitive answer might be ↑↓. However, if presented with an ensemble of spin configurations and posed with the same question, the concept of a pattern becomes vague. To reason towards a definition of pattern for ensembles, we can ask: “What’s the key property of a pattern?” A plausible candidate is that a pattern represents a compressed form of data that enables an observer to reproduce the original content [69]. Thus, we can then ask: “What’s the object that statistically reproduces such a configuration?” The framework of computational mechanics provides the answer: the ϵ-machine, which can be interpreted as a physical or ensemble pattern [28, 29]. Fig. 3 illustrates the relationship between configuration and ensemble patterns. From this point forward, the plotted machines will be derived using the CMPy package, which implements a tree-reconstruction method for inferring ϵ-machines, as described in Refs. [26, 27]. The transient and recurrent states of these machines are represented in purple and green, respectively. For clarity in visualization, spins ↑ and ↓, emitted during transitions between causal states, are represented as 1 and 0, respectively. The ensembles of spin models discussed in the following section include configurations of either 4 or 6 spins. Configurations with probabilities below 1 ×10−5are excluded from consideration. 16 whereas for J2<0, it leans toward period-4 configurations. Therefore, J2acts as a periodicity parameter of type 2. •−Jtbsisi+1si+2 is the expression that represents the three-body interaction. When Jtb >0, the configurations are biased toward a period-1 pattern, while Jtb <0 favors period-4 configurations. As a result, Jtb functions as a type 2 periodicity parameter. Fig. 10. Illustration of spin interactions in three-body models: nearest-neighbor (purple), next-nearest neighbor (green), and three-body (orange) interactions. The purpose of Fig. 11 is to illustrate how turning the nearest-neighbor coupling on and off in a three-body model affects both its configurations and information measures as a parameter of interest varies. Temperature is chosen as that parameter because it plays a key role in thermal desorption applications, where the goal is to identify the temperature that maximizes desorption [84, 87]. In both panels, the next-nearest-neighbor coupling J2is set to 0 to highlight the role of the nearestneighbor coupling J1, while the three-body coupling Jtb is set to −1. However, in Fig. 11(a), the nearest-neighbor coupling J1is set to 0, whereas in Fig. 11(b), it is set to 1. In both Fig. 11(a) and Fig. 11(b), Cµincreases and reaches its maximum value of Cµ= 2 as the temperature Trises, but the starting values differ. In Fig. 11(a), Cµbegins around 1.9, whereas in Fig. 11(b), it starts at approximately Cµ≈1.58. This suggests that at low temperature values, the typical configurations in Fig. 11(a) are period-4, and in Fig. 11(b), they are period-3. This difference can be attributed to the fact that Fig. 11(b) involves competing couplings, whereas Fig. 11(a) does not, as it only includes the three-body coupling. In particular, in both Fig. 11(a) and Fig. 11(b), the three-body coupling Jtb biases configurations toward a period-4 pattern. However, in Fig. 11(b), the ferromagnetic coupling J1also biases configurations toward a period-1 pattern. The competition leads to a compromise, resulting in period-3 configurations. This is consistent with the low-temperature typical configurations calculated using the Boltzmann distribution, which are shown below the horizontal axis in Fig. 11(b). Moreover, the nearest-neighbor coupling significantly reduces the uncertainty in predicting the next spin by expanding the neighborhood of spins that each state affects. This leads to a lower hµat very low temperatures in Fig. 11(b) compared to Fig. 11(a). This prevents Cµin Fig. 11(b) from being strongly influenced by hµat very low temperatures. Furthermore, although Cµis higher in Fig. 11(a) than in Fig. 11(b) at low temperatures, Eis lower in Fig. 11(a) compared to Fig. 11(b) at the same temperatures. This implies that while typical configurations in Fig. 11(a) at very low temperatures exhibit greater periodicity than those in Fig. 11(b) (period-4 versus period-3), the observer must examine more spin variables to discern the configuration pattern in Fig. 11(b). While this might seem to suggest that patterns in Fig. 11(b) are easier to discern than those in Fig. 11(a), the uncertainty per spin in Fig. 11(b) is significantly higher. Specifically, hµ≈0 for Fig. 11(a), whereas hµ≈0.9 for Fig. 11(b). This substantial difference makes an information-theoretic approach based on excess entropy Einsufficient for determining the ease of synchronization. We will soon address this by examining the computational properties of the three-body models. Notably, the information measures of the three-body model reveal new features that were absent in previously studied spin models. For instance, unlike the dependence of Eon temperature in the nearest-neighbor Ising model, where Edecays to 0 as Tincreases (as shown in Ref. [2] and Appendix B), Efor the three-body model remains nonzero even at high temperatures. Moreover, even though there is no magnetic field Bin Fig. (b), the information measures are not flat across the temperature range. This suggests that a diversity of configuration patterns is possible whenever competing parameters are present, regardless of their specific nature, which further reinforces the usefulness of our classification of parameter types. Ultimately, the information measures plots in Fig. 5, Fig. 8 and Fig. 11 suggest that different spin models give rise to distinct configuration patterns and structural behavior. Fig. 11. (a) hµ,Eand Cµv.s. Tfor three body model with J1= 0, J2= 0 and Jt=−1. (b) hµ,Eand Cµv.s. Tfor three body model with J1= 1, J2= 0 and Jt=−1. Fig. 12 aims to illustrate the structural changes in the ϵ-machine of a three-body model with competing couplings as the temperature increases. The plots in Fig. 12(a) and Fig. 12(b) depict the ϵ-machines corresponding to Fig. 11(b) at a very low temperature T= 0.025 and a low temperature T= 2, respectively. The outgoing probabilities from the causal transient state Ato the transient states Band Cin Fig. 12(a), 17 Fig. 12. (a) ϵ-machine for three body model with J1=−1, J2= 0, Jt= 1, T= 0.025. (b) ϵ-machine for three body model with J1=−1, J2= 0, Jt= 1, T= 2 which are circled in red and blue, are less uniform than those in Fig. 12(b). This implies that the ϵ-machine in Fig. 12(a) is easier to synchronize than the one in Fig. 12(b). At first, this may seem inconsistent with their excess entropy values, given that E≈1.58 for Fig. 12(a) and E= 1 for Fig. 12(b), as shown in Fig. 11(b). However, this apparent contradiction is resolved by observing the significantly higher value of hµin Fig. 12(b) compared to Fig. 12(a), where hµ≈1 for Fig. 12(b) and hµ≈0 for Fig. 12(a). As a result, while discerning configuration patterns in Fig. 12(a) may require an additional spin, the much higher uncertainty in predicting the next spin in Fig. 12(b) outweighs this requirement, making synchronization more challenging in Fig. 12(b) than in Fig. 12(a). This uncertainty is further supported by the fact that typical configurations for Fig. 12(b) are much less probable than those in Fig. 12(a). Specifically, the highest probability for a typical configuration in Fig. 12(a) is 0.33, whereas in Fig. 12(b), it is only 0.025. This contrast highlights how the computational approach provided by ϵ-machines offers a more nuanced perspective on synchronization than the randomness-agnostic viewpoint of excess entropy E. Moreover, the recurrent part of Fig. 12(a) is much less connected than that of Fig. 12(b). In the ϵ-machine for Fig. 12(a), each recurrent causal state has only one outgoing transition with probability 1.0. In contrast, the recurrent states in Fig. 12(b) each have two outgoing transitions, both with probabilities close to 0.50. Furthermore, Fig. 12(b) includes self-loops that enable it to recognize period-1 configurations consisting entirely of 0s or 1s, a feature absent in Fig. 12(a). This indicates that the machine in Fig. 12(b) generates a greater variety of spin configurations compared to the one in Fig. 12(a). This observation is consistent with the fact that at T= 0.025, there are only three typical configurations, whereas at T= 2, there are six. Lastly, the number of recurrent causal states, along with the low connectivity of the machine in Fig. 12(a), suggests that it can support configurations with periods of up to 3. In contrast, the machine in Fig. 12(b), which has the same number of recurrent causal states but higher connectivity, permits configurations with periods of up to 4. The typical configurations in Fig. 11(b) reflect this pattern, as Fig. 12(b) accommodates both period-4 and period-3 configurations, whereas Fig. 12(a) only supports period-3 configurations. Ultimately, this comparison of ϵmachines underscores the importance of considering not only typical configurations but also their probabilities when developing a computation-theoretic account of spin patterns. IV. CONCLUSION What, then, is a pattern in statistical mechanics? If one recasts the mechanism generating a system’s structure as an information processor, the answer for the one-dimensional spin models studied here is clear: the ϵ-machine. To support this perspective, we began by introducing computational mechanics and its application to statistical mechanics in a conceptual manner with only the necessary amount of mathematics. We then defined typical configurations and typical configuration patterns as the most likely configurations and configuration patterns within an ensemble. Furthermore, we classified parameters of spin models according to the type of behavior to which they give rise. Using this framework, we computed typical configurations from the embedded Boltzmann distribution and compared them to those implied by information measures and ϵ-machines for three different spin models: the finiterange Ising model, the SOS model, and the three-body model. Our findings confirmed consistency between the results, establishing the ϵ-machine as a representation of the Boltzmann distribution’s ensemble patterns. Moreover, our analysis showed that information measures and ϵ-machines offer a detailed and nuanced characterization of typical configuration patterns, allowing us to distinguish between them and identify their shared features. In the finite-range Ising model, the information plots show that Cµserves as a simple visual indicator of regions where no typical configurations exist. These regions, distinguished by the non-flat behavior of Cµ, are what we refer to as transition zones. Furthermore, Cµ captures the fact that different parameters influence the diversity of configuration patterns, and consequently, the computational demands. For instance, a dominant antiferromagnetic J2coupling maximizes computation, while competing effects between Band antiferromagnetic J1 lead to high but constrained computation. Moreover, the ϵ-machines of the finite-range Ising model provide a more refined perspective on the computational differences arising from varying parameters. 18 For instance, the high but constrained computation observed in the three-range Ising model with a high magnetic field and low temperature is represented by fewer causal states and lower connectivity compared to a system with a low magnetic field and moderate temperature. This distinction offers a more nuanced understanding of what it means for a system to require less or more computation. Additionally, the analysis shows that the number of causal states cannot simply be inferred from properties such as the number of neighbors a given spin has or the magnitude and sign of the parameters. In the SOS model, Cµallows us to quantify the reduction in computational effort caused by turning the wall on, even when the typical configuration remains unchanged. Furthermore, the observation that maximum Cµoccurs at very low kink coupling demonstrates that the peak of maximum Cµvaries depending on the specific parameter under consideration. Moreover, the ϵmachines of the SOS model show that turning on the wall parameter reduces the uniformity of the outgoing transition probabilities from the start state. This indicates that the typical configuration gets more likely as the wall parameter becomes nonzero. In computational terms, when the wall is fully activated, the machine becomes more similar to a single-state machine that solely outputs 1. More broadly, the machines from this case study, along with those of the nearest-neighbor Ising model, demonstrate that ϵ-machines provide a unified framework for identifying computational similarities (such as the number of states and connectivity) and differences (such as transition probabilities) between two distinct spin models. The information measures of the three-body models, both with and without nearest-neighbor coupling, are not monotonically dependent. Specifically, a high Eor hµis shown to not necessarily imply a high or low Cµ. The information plots of these three body models, along with those of the finite-range Ising models, capture how different spin models produce distinct configuration patterns when the same parameter, in this case temperature, is varied. Furthermore, the ϵ-machines of the three-body model with nearest-neighbor coupling provide an effective framework for identifying computational similarities and differences in the spin model as a parameter, such as temperature, changes. As temperature increases, typical configurations become more periodic, but also less likely to occur. The ϵ-machines capture this behavior by making the outgoing probabilities from transient causal states more uniform while increasing connectivity in the recurrent portion. This suggests that as typical configuration patterns become more periodic and less likely, they also become harder to discern overall. Notably, this result highlights the limitations of an information-theoretic perspective on synchronization—while useful, it remains incomplete without a computational viewpoint. This insight sheds light on subtle structural differences between systems that, despite having the same number of recurrent and transient causal states, exhibit distinct dynamical behaviors. Ultimately, information theory and computational mechanics offer powerful tools for defining patterns within Boltzmann ensembles and comprehensively characterizing the typical configurations generated by the Boltzmann distribution. They also enable a unified way of examining similarities and differences in the structure and patterns of a spin model under varying parameters and across different spin models. This perspective connects the abstract formalism of information theory and automata theory with the concrete physical models of statistical mechanics, providing a constructive and effective language to describe patterns in statistical mechanics. V. DATA AVAILABILITY STATEMENT The code supporting this study is available at: https: //github.com/omalagui/spin_patterns VI. ACKNOWLEDGEMENTS I am grateful to Josh Deutsch, Jim Crutchfield, Anthony Aguirre, Zara Brandt, Evan Frangipane, Vidyesh Rao and Jordan Scharnhorst for helpful feedback and insightful conversations. This research was supported by the Foundational Questions Institute and by the Faggin Presidential Chair Fund. VII. REFERENCES [1] S. Aaronson, S. M. Carroll, and L. Ouellette, arXiv preprint arXiv:1405.6903 (2014). [2] D. P. Feldman and J. P. Crutchfield, Entropy 24, 1282 (2022), authors’ note: Manuscript completed in 1998 (Santa Fe Institute Working Paper 98-04-026). [3] P. Bak, How Nature Works: The Science of Selforganized Criticality, ebook ed. (Springer New York, New York, 2013). [4] J. Rothstein, Science 114, 171 (1951). [5] I. Eliazar, Physica A: Statistical Mechanics and its Applications 568, 125662 (2021). [6] J. M. Yeomans, Statistical Mechanics of Phase Transitions (Clarendon Press, Oxford, 1992). [7] S. Krinsky and D. Furman, Physical Review B 11, 2602 (1975). 19 [8] R. Gheissari, C. Hongler, and S. C. Park, Communications in Mathematical Physics 367, 771 (2019). [9] M. Schulz and S. Trimper, Journal of Statistical Physics 94, 173 (1999). [10] R. H. Lacombe and R. Simha, The Journal of Chemical Physics 61, 1899 (1974). [11] D. P. Landau and K. Binder, in A Guide to Monte Carlo Simulations in Statistical Physics (Cambridge University Press, Cambridge, United Kingdom, 2015) 4th ed., pp. 7–46. [12] B. M. McCoy and T. T. Wu, Physical Review 176, 631 (1968). [13] P. D. Beale, Physical Review Letters 76, 78 (1996). [14] J. K¨ofinger and C. Dellago, New Journal of Physics 12, 093044 (2010). [15] M. M. Tsypin and H. W. J. Blote, Physical Review E 62, 73 (2000). [16] C. Chatelain and D. Karevski, Journal of Statistical Mechanics: Theory and Experiment 2006, P06005 (2006). [17] R. K. Pathria and P. D. Beale, Statistical Mechanics, 3rd ed. (Butterworth-Heinemann, 2011). [18] B. Derrida, Physical Review Letters 45, 79 (1980). [19] M. Tribus, Thermostatics and Thermodynamics: An Introduction to Energy, Information and States of Matter, with Engineering Applications (D. Van Nostrand Company, Inc., Princeton, New Jersey, USA, 1961). [20] G. Bateson, Steps to an Ecology of Mind: Collected Essays in Anthropology, Psychiatry, Evolution, and Epistemology (Jason Aronson Inc., Northvale, NJ and London, 1987). [21] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. (Wiley-Interscience, Hoboken, NJ, USA, 2006). [22] R. Shaw, The Dripping Faucet as a Model Chaotic System (Aerial Press, Santa Cruz, California, 1984). [23] J. P. Crutchfield and N. H. Packard, Physica D 7, 201 (1983). [24] P. Grassberger, International Journal of Theoretical Physics 25, 907 (1986). [25] K. Lindgren and M. G. Nordhal, Complex Systems 2, 409 (1988). [26] J. P. Crutchfield and K. Young, Physical Review Letters 63, 105 (1989). [27] J. P. Crutchfield, Physica D 75, 11 (1994). [28] J. P. Crutchfield, Nature Physics 8, 17 (2012). [29] C. R. Shalizi and J. P. Crutchfield, Journal of Statistical Physics 104, 817 (2001). [30] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed. (Addison-Wesley, 2001). [31] J. P. Crutchfield and C. R. Shalizi, Physical Review E 59, 275 (1999). [32] S. Still, J. P. Crutchfield, and C. J. Ellison, CHAOS 20, 037111 (2010). [33] C. C. Streloff and J. P. Crutchfield, Phys. Rev. E 89, 042119 (2014). [34] S. E. Marzen and J. P. Crutchfield, Journal of Statistical Physics 163, 1312 (2016). [35] A. Rupe, N. Kumar, V. Epifanov, K. Kashinath, O. Pavlyk, F. Schimbach, M. Patwary, S. Maidanov, V. Lee, Prabhat, and J. P. Crutchfield, in 2019 IEEE/ACM Workshop on Machine Learning in High Performance Computing Environments (MLHPC) (2019) pp. 75–87. [36] A. Rupe and J. P. Crutchfield, arXiv preprint (2020), arXiv:2010.05451. [37] N. Brodu and J. P. Crutchfield, Chaos: An Interdisciplinary Journal of Nonlinear Science 32, 023103 (2022). [38] A. M. Jurgens and N. Brodu, Chaos: An Interdisciplinary Journal of Nonlinear Science 35, 033162 (2025). [39] D. P. Feldman and J. P. Crutchfield, Physical Review E 67, 051104 (2003). [40] V. S. Vijayaraghavan, R. G. James, and J. P. Crutchfield, Santa Fe Institute Working Paper 15-10-042 (2016). [41] C. Aghamohammadi, J. R. Mahoney, and J. P. Crutchfield, Scientific Reports 7, 6735 (2017). [42] C. Aghamohammadi, J. R. Mahoney, and J. P. Crutchfield, Physics Letters A 381, 1223 (2017). [43] P. Chattopadhyay and G. Paul, arXiv preprint arXiv:2102.09981 (2024). [44] D. Chu and R. E. Spinney, Interface Focus 8, 20180037 (2018). [45] P. Strasberg, J. Cerrillo, G. Schaller, and T. Brandes, arXiv preprint arXiv:1506.00894 (2015). [46] D. H. Wolpert and J. Scharnhorst, arXiv preprint arXiv:2410.07131 (2024). [47] L. Li, L. Chang, R. Cleaveland, M. Zhu, and X. Wu, arXiv preprint arXiv:2402.13469 (2024). [48] A. S. Bhatia and A. Kumar, arXiv preprint arXiv:1901.07992 (2019). [49] D.-S. Wang, arXiv preprint arXiv:1912.03767 (2019). [50] A. Molina and J. Watrous, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 20180767 (2019). [51] N. A. Alves, B. A. Berg, and R. Villanova, Physical Review B 41, 383 (1990). [52] Y. Lin, F. Wang, X. Zheng, H. Gao, and L. Zhang, Journal of Computational Physics 237, 224 (2013). [53] A. M. Ferrenberg, J. Xu, and D. P. Landau, Physical Review E 97, 043301 (2018). [54] D. J. MacKay, Information Theory, Inference, and Learning Algorithms (Cambridge University Press, Cambridge, UK, 2003). [55] A. V. Myshlyavtsev, in Studies in Surface Science and Catalysis, Vol. 138, edited by A. Guerrero-Ruiz and I. Rodr´ıguez-Ramos (Elsevier Science B.V., Amsterdam, 2001) pp. 173–190. [56] J. C. Flack, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 375, 20160338 (2017). [57] C. R. Shalizi and C. Moore, Foundations of Physics 55, 2 (2025). [58] A. L. Ny, arXiv preprint arXiv:0712.1171 (2007), lectures given at the Semana de Mecˆanica Estat´ıstica, Universidade Federal de Minas Gerais and Universidade Federal do Rio Grande do Sul. [59] S. Muir, Nonlinearity 24, 2933 (2011). [60] N. Ganikhodjaev, Journal of Mathematical Analysis and Applications 336, 693 (2007). [61] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, second edition ed. (Cambridge University Press, Cambridge, United Kingdom, 2021). [62] J. P. Crutchfield and D. P. Feldman, arXiv preprint condmat/0102181 (2001), santa Fe Institute Working Paper 01-02-012. [63] C. E. Shannon and W. Weaver, The Mathematical Theory of Communication (University of Illinois Press, Champaign-Urbana, 1963). 20 [64] D. Feldman, A Brief Introduction to Information Theory, Excess Entropy, and Computational Mechanics, College of the Atlantic, Bar Harbor, ME (1998), revised October 2002. [65] C. R. Shalizi, Causal Architecture, Complexity, and SelfOrganization in Time Series and Cellular Automata, Ph.d. dissertation, University of Wisconsin-Madison, Madison, WI (2001), available at Santa Fe Institute: http://www.santafe.edu/~shalizi/thesis. [66] S. E. Marzen and J. P. Crutchfield, Entropy 24, 90 (2022). [67] K. Young and J. P. Crutchfield, Chaos, Solitons and Fractals 4, 5 (1994). [68] K. A. Young, The Grammar and Statistical Mechanics of Complex Physical Systems, Ph.d. dissertation, University of California, Santa Cruz (1991). [69] D. C. Dennett, The Journal of Philosophy 88, 27 (1991). [70] R. Kikuchi, Physical Review 99, 1666 (1955). [71] J. F. Dobson, Journal of Mathematical Physics 10 (1969). [72] M. Slotnick, Physical Review 83, 996 (1951). [73] C. Zener and R. R. Heikes, Reviews of Modern Physics 25, 191 (1953). [74] A. V. Zarubin, F. A. Kassan-Ogly, A. I. Proshkin, and A. E. Shestakov, Journal of Experimental and Theoretical Physics 128, 778 (2019). [75] K. A. Mutallib and J. H. Barry, Physical Review E 106, 014149 (2022). [76] R. Moessner and S. L. Sondhi, Physical Review B 63, 224401 (2001). [77] W. K. Burton, N. Cabrera, and F. C. Frank, Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences 243, 299 (1951). [78] J. D. Weeks, in Ordering in Strongly Fluctuating Condensed Matter Systems, NATO Advanced Study Institutes Series: Series B, Physics, Vol. 50, edited by T. Riste (Plenum Press, New York, 1980) pp. 293–315. [79] V. Privman and N. M. ˇ Svraki´c, Journal of Statistical Physics 51, 819 (1988). [80] D. B. Abraham, Department of Mathematics, University of Newcastle, Newcastle, New South Wales 2308, Australia (1979). [81] J. Wang, X. Feng, C. W. Anderson, Y. Xing, and L. Shang, Journal of Hazardous Materials 221, 1 (2012). [82] J. D. Aparicio, E. E. Raimondo, J. M. Saez, S. B. Costa-Gutierrez, A. Alvarez, C. S. Benimeli, and M. A. Polti, Journal of Environmental Chemical Engineering 10, 107141 (2022). [83] V. P. Zhdanov, Surface Science 111, 63 (1981). [84] P. A. Redhead, Vacuum 12, 203 (1962). [85] M. A. Morris, M. Bowker, and D. A. King, in Comprehensive Chemical Kinetics, Vol. 19 (Elsevier, 1984) pp. 1–179. [86] V. P. Zhdanov and K. I. Zamaraev, Soviet Physics Uspekhi 29, 755 (1986). [87] A. V. Myshlyavtsev, J. L. Sales, G. Zgrablich, and V. P. Zhdanov, Journal of Chemical Physics 91, 7500 (1989). Appendix A: Concept of “state” in theory of computation and its formalization in computational mechanics In automata theory, abstract machines—the primary objects of study—are formalized in terms of “states.” However, the concept of “state” itself lacks an explicit mathematical definition. Even at a conceptual level, a “state” is rarely defined. One notable exception appears in [30] (pp. 2-3), where a state is defined as the relevant portion of a system’s history. Although the purpose of this relevance is not specified, it is illustrated through the example of a very simple finite-state machine: an on-off switch, shown below. Fig. 13. Finite state machine modeling on/off. This example is reproduced from Hopcroft and Ullman’s Introduction to Automata Theory, Languages, and Computation. The machine only needs to remember “whether it is in the on state or off state.” From this, we can infer that a state represents the relevant part of a machine’s history needed to predict a portion of the machine’s future behavior. This raises the question: “How to formalize this notion of state?” Computational mechanics addresses this by formalizing the concept probabilistically, defining it as a triple, as shown in Section II E. Appendix B: Information measures across varying temperature in a nearest-neighbor Ising model Fig. 14 presents information measures Cµ,hµ, and E as functions of temperature Tfor a nn Ising model with B= 0.2 and ferromagnetic coupling J1= 1. This figure reproduces Fig. 13 of Ref. [2]. Appendix C: Shannon entropy density hµand Boltzmann entropy density htherm The form of the Boltzmann (thermodynamic) entropy density and Shannon entropy rate for a nn Ising model are presented in equations C1 and C2, respectively. These expressions are plotted as a function of temperature Tin Fig. 15, where they are graphically shown to be equivalent as temperature is varied. 21 Fig. 14. Cµ,hµ, and Ev.s. Tfor nn spin-1/2 Ising model with B= 0.2 and J1= 1. htherm =−∂ ∂T −T Nlog2λN(C1) hµ=−X s0,s−1=±1 Pr(s0, s−1) log2Pr(s0, s−1) Pr(s−1)(C2) Fig. 15. Boltzmann (thermodynamic) entropy density htherm and Shannon entropy rate hµv.s. temperature T Appendix D: Derivation of Boltzmann (thermodynamic) entropy density for nearest-neighbor Ising model 1. Consider htherm =−∂ ∂T −T Nlog2λN =∂ ∂T (Tlog2(λ)) = log2λ+T∂ ∂T (log2λ) 2. Using the chain rule: ∂ ∂T =dβ dT ∂ ∂β =−1 T2 ∂ ∂β =−β2∂ ∂β 3. Rewrite htherm in terms of β=1 T htherm = log2λ−β∂log2(λ) ∂β = log2λ−β1 log(2) 1 λ ∂λ ∂β 4. Split principal eigenvalue λinto two terms λ=eβJ cosh(βB) + qe2βJ sinh2(βB) + e−2βJ = term I + term II 5. Carry out d dβ term I and d dβ term II d dβ term I = eβJ (Jcosh(βB) + Bsinh(βB)) d dβ term II = 1 2e2βJ sinh2(βB) + e−2βJ −1 2· d dβ e2βJ sinh2(βB) + e−2βJ  6. Simplify d dβ e2βJ sinh2(βB) + e−2βJ  = 2Je2βJ sinh2(βB) + e2βJ ·2Bsinh(βB) cosh(βB)−2Je−2βJ = 2 Je2βJ sinh2(βB) + Be2βJ sinh(βB) cosh(βB)−Je−2βJ  = 2 e−2βJ (Je4βJ sinh2(βB) + Be4βJ sinh(βB) cosh(βB)−J) 7. Simplify d dβ term II =Je2βJ sinh2(βB) + Be2βJ sinh(βB) cosh(βB)−Je−2βJ qe2βJ sinh2(βB) + e−2βJ = 2Je2βJ sinh2(βB) + e2βJ ·2Bsinh(βB) cosh(βB)−2Je−2βJ = 2 Je2βJ sinh2(βB) + Be2βJ sinh(βB) cosh(βB)−Je−2βJ  = 2 e−2βJ (Je4βJ sinh2(βB) + Be4βJ sinh(βB) cosh(βB)−J) 22 8. Simplify dλ dβ dλ dβ =eβJ (Jcosh(βB) + Bsinh(βB)) + Je2βJ sinh2(βB) + Be2βJ sinh(βB) cosh(βB)−Je−2βJ qe2βJ sinh2(βB) + e−2βJ 9. Replace in htherm htherm = log2λ−β1 log(2) 1 λ ∂λ ∂β = log2λ−β1 log(2) 1 λ·(eβJ (Jcosh(βB) + Bsinh(βB)) + Je2βJ sinh2(βB) + Be2βJ sinh(βB) cosh(βB)−Je−2βJ qe2βJ sinh2(βB) + e−2βJ ) Appendix E: ϵ-machine of nearest-neighbor Ising model Fig. 16 presents the ϵ-machine of a nearest-neighbor Ising model with J1= 1.0, B= 0.35, and T= 1.5. This figure reproduces Fig. 10 of Ref. [2]. Fig. 16. ϵ-machine of nn Ising model with J1= 1.0, B= 0.35, and T= 1.5. Appendix F: Joint probability of infinite chain 1. Consider a periodic infinite spin chain whose spins can only take two values (up or down) and only interact with their nearest neighbors. s0, s1, s2, s3, ..., sN−1where s0=sN 2. Define a Hamiltonian for this system in a translation-invariant manner. E=E(s0, . . . , sN−1) = − N−1 X i=0 Jsisi+1− N−1 X i=0 B(si+si+1) 2 3. Calculate the system’s partition function. Z=X {si} e−βE 4. Define the Boltzmann probability of a given infinite configuration. Pr(s0. . . sN) = e−βE Z 5. Define the transfer matrix matrix, with components V(si, si+1) = Vsisi+1 =e−βE(sisi+1). V=e−βE(↑,↑)e−βE(↓,↑) e−βE(↑,↓)e−βE(↓,↓) 6. Express Boltzmann probability weight e−βE in terms of transfer matrix components. e−βE =e−βE(s0s1)e−βE(s1s2)... e−βE(sN−1sN) =Vs0s1Vs1s2... VsN−1sN 7. Calculate partition function in the thermodynamic limit N→ ∞. ZN→∞ =X s0=±1X s1=±1 ... X sN=±1 Vs0s1Vs1s2... VsN−1sN 8. Apply definition of matrix multiplication P s2 Vs1s2Vs2s3=V2 s1s3and enforce periodic boundary conditions s0=sN. ZN→∞ =X s0=±1X sN=±1 VN−1 s0sN=X s0=±1 VN s0s0 9. Apply definition of trace. ZN→∞ = (Tr(V))N= lim N→∞ λN ++λN − = lim N→∞ λN +(1 + λN + λN − ) = λN +=λN where λis principal eigenvalue 10. Express joint probability of a given infinite spin chain in terms of principal eigenvalue λand transfer matrix components Vsi,si+1 . Pr(s0, s1, ..., sN−1) = Vs0s1Vs1s2... VsN−1sN λN= N−1 Q i=0 Vsisi+1 λN 23 Appendix G: Eigenvalue decomposition of Transfer matrix 1. Express Vin terms of its eigenvalue decomposition V=UDU−1. V=u+u− u−−u+λ+0 0λ−u+u− u−−u+−1 =λ+u+u− u−−u+1 0 0λ− λ+u+u− u−−u+−1 2. Use fact that in the thermodynamic limit N→ ∞, λ+≫λ−. Rename λ+as λ. =u+u− u−−u+λ0 0 0u+u− u−−u+−1 =u+u− u−−u+λ0 0 0u+u− u−−u+ =u+u− u−−u+λu+λu− 0 0  Therefore, V=λu2 +λu+u− λu+u−λu2 − 3. Express transfer matrix components in terms of the principal eigenvalue λand the principal eigenvector components u+and u−at the thermodynamic limit. V(↑,↑) = λu2 + V(↑,↓) = V(↓,↑) = λu+u− V(↓,↓) = λu2 − (G1) Appendix H: Partition function of finite chain with fixed boundary conditions embedded on infinite chain Base Case (L= 3): 1. Consider the partition function of a finite chain of length 3 with fixed boundary conditions. Z3=X s1=±1 V(sfix 0, s1)V(s1, sfix 2) =V(sfix 0,↑)V(↑, sfix 2) + V(sfix 0,↓)V(↓, sfix 2) 2. Express transfer matrix components in terms of principal eigenvalue and principal eigenvector components. For simplicity, we will drop the Land R, because for the nn Ising model the left and right eigenvectors are the same. =λufix s0u↑·λu↑ufix s2+λufix s0u↓·λu↓ufix s2 =λufix s0ufix s2u2 ↑+λufix s0ufix s2u2 ↓ =λufix s0ufix s2(u2 ↑+u2 ↓) =λufix s0ufix s2 Inductive Step: 1. Assume the partition function of a finite chain of length Lhas the following expression. ZL=λL−1ufix s0ufix sL−1(H1) 2. Consider ZL+1. ZL+1 =X s1=±1 . . . X sL−1=±1 V(sfix 0, s1). . . V (sL−1, sfix L) 3. Sum over L−1. =V(↑, sfix L)·X s1=±1 . . . X sL−2=±1 V(sfix 0, s1). . . V (sL−2,↑) (H2) +V(↓, sfix L)·X s1=±1 . . . X sL−2=±1 V(sfix 0, s1). . . V (sL−2,↓) 4. Replace Eq. H1 in Eq. H2. =V(↑, sfix L)·λL−1ufix s0u↑+V(↓, sfix L)·λL−1ufix s0u↓(H3) 5. Replace Eq. G1 in Eq. H3 =λu↑ufix sL·λL−1ufix s0u↑+λu↓sfix L·λL−1ufix s0u↓ =λLufix s0ufix sLu2 ↑+ufix s0ufix sLu2 ↓ 6. Factor. =λLufix s0ufix sL(u2 ↑+u2 ↓) 7. Use normalization condition u2 ↑+u2 ↓= 1. ZL+1 =λLufix s0ufix sL(H4) 24 Appendix I: Joint probability of finite chain embedded on infinite chain 1. Consider a finite spin chain embedded in an infinite spin chain. −→ sL=s0, . . . , sL−1 2. The embedding of the finite spin chain implies: •The thermodynamic limit applies to the finite chain. •The magnetization is uniform across the bulk and boundaries of the finite chain. 3. To ensure uniform magnetization, express Prembedded in terms of conditional and marginal probabilities to separate the contributions from the bulk and boundaries. For simplicity, we denote Prembedded as Pr. Pr(−→ sL) = Pr(−→ sL|s0and sL−1are fixed)Pr(s0, sL−1) 4. Since s1and sLare independent, their probabilities can be factored as: Pr(−→ sL) = Pr(−→ sL|s0=sfixed 0, sL−1=sfixed L−1)Pr(s0)Pr(sL−1) 5. Express Pr(−→ sL|s0and sLare fixed) as a joint probability using Pr(sfixed i) = 1. Pr(−→ sL|s0and sLare fixed) = Pr(sfixed 0, . . . , sfixed L−1) Thus, Pr(−→ sL) = Pr(sfixed 0, . . . , sfixed L−1)Pr(s0)Pr(sL−1) (I1) 6. Replace relevant joint and marginal probabilities for nn Ising model in Eq. I1. Pr(−→ sL) = L−2 Q i=0 Vsisi+1 uL,s0uR,sL−1λL−1·u2 L,s0·u2 R,sL−1 = uL,s0uR,sL−1 L−2 Q i=0 Vsisi+1 λL−1 7. To recover Eq. (36), consider ←→ sLinstead of −→ sL Appendix J: Finite-range Ising model Hamiltonian for R= 1,2and 3 The finite-range Ising model Hamiltonian is written below for neighborhood radii R= 1, R= 2, and R= 3. In the notation used for the Hamiltonian, the neighborhood radius Ris denoted by n. For n= 1: Xηj=−B 1−1 X i=0 sj i− n=1 X k=1 Jk 1−k−1 X i=0 sj isj i+k! =−Bsj 0−0 = −Bsj 0 =−Bs0 Yηj,ηj+1 =− n=1 X k=1 Jk k−1 X i=0 sj 1−i−1sj+1 k−i−1! =−J1 1−1 X i=0 sj −isj+1 −i!=−J1sj 0sj+1 0 =−J1s0s1 Xηj+1 =−Bsj+1 0=−Bsj+1 0=−Bs1 For n= 2: Xηj=−B 2−1 X i=0 sj i− n=2 X k=1 Jk 2−k−1 X i=0 sj isj i+k! =−Bsj 0+sj 1−J1 2−1−1 X i=0 sj isj i+1!−J2 2−2−1 X i=0 sj isj i+2! =−Bsj 0+sj 1−J1sj 0sj 1 =−B(s0+s1)−J1s0s1 Yηj,ηj+1 =− n=2 X k=1 Jk k−1 X i=0 sj 2−i−1sj+1 k−i−1! =−J1 1−1 X i=0 sj 1−isj+1 0−i!−J2 2−1 X i=0 sj 1−isj+1 1−i! =−J1sj 1sj+1 0+J2sj 1sj+1 1+sj 0sj+1 0 =−J1s1s2−J2(s1s3+s0s2) Xηj+1 =−Bsj+1 0+sj+1 1−J1sj+1 0sj+1 1 =−B(s2+s3)−J1s2s3 25 For n= 3: Xηj=−B 3−1 X i=0 sj i− n=3 X k=1 Jk 3−k−1 X i=0 sj isj i+k! =−Bsj 0+sj 1+sj 2−J1 3−1−1 X i=0 sj isj i+1! −J2 3−2−1 X i=0 sj isj i+2! =−Bsj 0+sj 1+sj 2−J1sj 0sj 1+sj 1sj 2−J2sj 0sj 2 =−B 2 X i=0 si−J1(s0s1+s1s2)−J2s0s2 Yηj,ηj+1 =− 3 X k=1 Jk k−1 X i=0 sj 3−i−1sj+1 k−i−1! =−J1 1−1 X i=0 sj 2−isj+1 0−i!−J2 2−1 X i=0 sj 2−isj+1 1−i! −J3 3−1 X i=0 sj 2−isj+1 2−i! =−J1sj 2sj+1 0−J2sj 2sj+1 1+sj 1sj+1 0 −J3sj 2sj+1 2+sj 1sj+1 1+sj 0sj+1 0 =−J1(s2s3)−J2(s2s4+s1s3) −J3(s2s5+s1s4+s0s3) Xηj+1 =−Bsj+1 0+sj+1 1+sj+1 2 −J1sj+1 0sj+1 1+sj+1 1sj+1 2 −J2sj+1 0sj+1 2 =−B n=5 X i=3 si−J1(s3s4+s4s5)−J2s3s5 Appendix K: Three-body model transfer matrix The transfer matrix Vof the three-body spin model is shown in Eq. (K1). To simplify the notation of the matrix entries, we label each two-spin block as follows: ↑↑ = 1, ↑↓ = 2, ↓↑ = 3, and ↓↓ = 4. Moreover, we set the chemical potential µto zero. V= ↑↑ ↑↓ ↓↑ ↓↓ ↑↑ ↑↓ ↓↑ ↓↓    V11 V12 0 0 0 0 V23 V24 V31 V32 0 0 0 0 V43 V44    (K1) where V11 = exp µ−J1−J2−Jtb T, V12 = exp µ−J1 T, V23 = exp µ−J2 T, V24 = exp µ T, V31 =V32 =V43 =V44 = 1 Note that, unlike the finite-range Ising model, the spin blocks in this model overlap by one spin. Specifically, the last spin in a row label must match the first spin in a column label. For example, the spin block ↑↓ in the second row can only transition to spin blocks ↓↑ or ↓↓ in the third and fourth columns, as its last spin ↓matches the first spin of both ↓↑ and ↓↓.