WorksPhysics and Astronomy
Prestatability in the Macroscopic Limit
Abstract
We examine whether the variables required for a future macroscopic description of a given physical system can themselves be stated in advance. Representing macroscopic descriptions as coarse-grainings of a fixed microscopic phase space, we distinguish formal prestatability, concerning the existence of an effective complete vocabulary of admissible macroscopic distinctions, from dynamical prestatability, concerning whether the future relevance of those distinctions is decidable. Both obstructions disappear for finite microscopic state spaces. In the infinite limit, exhaustive formal prestatability can fail, while a restricted predictive architecture may remain formally pre-statable. We construct such an architecture and show that, under universal dynamics, the future relevance of a candidate variable is equivalent to the halting problem. Thus a fixed microscopic phase space can support macroscopic descriptions whose future variables are not fully pre-statable.
Introduction
A central question in the study of complex systems is not merely whether the future values of known variables can be predicted, but whether the variables needed to describe the future can themselves be stated in advance.
This distinction is central to the account of biological evolution developed by Kauffman and collaborators [1, 2, 3, 4, 5, 6, 7, 8]. In the usual mathematical description of a physical system, the relevant variables and their possible values are specified before the dynamics is considered. They define a phase space, and the subsequent evolution is represented as a trajectory within that space. The trajectory may be extremely difficult to predict, chaotic, stochastic, or computationally irreducible, but the space of possible states is nevertheless given in advance.
Kauffman and collaborators argue that biological evolution presents a different situation. Evolution goes beyond generating unexpected values of pre-existing variables: it gives rise to new phenotypes, functions, niches, and affordances that can themselves become relevant variables for the subsequent evolution of the biosphere [9, 10, 11]. In their account, these possibilities cannot be exhaustively specified beforehand. In particular, an affordance is not an intrinsic property of an object considered in isolation, but a possible use arising from the relation between an organism, its environment, and its possible actions [12]. As organisms and environments change, new such relations can arise. Selection may therefore reveal, only after the fact, features of organisms and environments that become relevant to a newly constituted niche.
This motivates Kauffman’s distinction between unpredictability and unprestatability. An unpredictable system may evolve within a phase space that is completely specified in advance: what is unknown is which trajectory will occur. An unprestatable system, by contrast, is one for which the relevant space of possibilities cannot itself be completely specified before the evolution unfolds. In this stronger sense, the problem is not only that we cannot predict what will happen, but that we cannot prestate all of the variables in terms of which future possibilities will eventually be described.
The present paper examines this claim by separating two notions that are usually left implicit: formal prestatability and dynamical prestatability.
Before examining these notions in detail, we first want to clarify the meaning of a macroscopic description. At the microscopic level, a single phase space is in principle sufficient to represent the complete state of the system. At the macroscopic level, however, one usually works with reduced descriptions that retain only those distinctions that matter for a particular scale, task, or regime. If one assumes that the microscopic phase space is fixed, a macroscopic description may be represented by a coarse-graining of , that is, by a partition of microscopic states into classes that are indistinguishable at the macroscopic level [13, 14]. A collection of macroscopic variables provides one way of generating such a partition: two microscopic states belong to the same block whenever all of the variables take the same values on them.
Different macroscopic questions may therefore require different coarse-grainings of the same underlying microscopic state space. A description appropriate for predicting one observable, identifying one function, or characterizing one regime need not remain appropriate when the system enters another context. In this sense, a macroscopic phase space is not merely a smaller copy of the microscopic one, but a task- and context-dependent representation of it. Once macroscopic description is understood in this way, the natural question is no longer only which state the system will occupy, but also which coarse-graining of the microscopic space will be required to describe it.
This formulation reveals two distinct ways in which the future macroscopic description may fail to be pre-statable.2 The first concerns the space of possible descriptions itself. Given a class of macroscopic coarse-grainings regarded as admissible, can one specify in advance an effective vocabulary of elementary distinctions from which every admissible description can be constructed? We call this question one of formal prestatability. A failure of formal prestatability means that no effectively specifiable vocabulary is sufficient to exhaust the macroscopic descriptions allowed by the theory.
The second question arises even if such a vocabulary has already been given. Suppose that every macroscopic variable that could possibly be required belongs to an explicitly specified family. Can one nevertheless determine, for an arbitrary member of that family, whether it will ever become relevant as the system evolves? We call this dynamical prestatability. It differs from ordinary unpredictability in the object being determined. Ordinary prediction takes a descriptive framework as fixed and asks which states or values will occur within it. Dynamical prestatability asks instead whether the future descriptive framework itself (the set of variables that will have to be retained) can be stated in advance. Its failure therefore indicates that the future macroscopic description cannot be fully determined from the dynamics ahead of time, even when the complete set of possible variables is known.
Nevertheless, neither obstruction can occur in the strict sense developed here for a genuinely finite, effectively specified deterministic system. If the microscopic state space is finite, there are only finitely many partitions of it, so every possible coarse-graining can in principle be enumerated. If the dynamical state space is also finite, every trajectory eventually repeats, so the question of whether a given variable will ever become relevant can likewise be settled by a finite exhaustive search. Computational complexity may make such procedures hopeless in practice, so finite systems may still be operationally unprestatable under physically available computational resources, but no strict mathematical obstruction to prestatability arises. Strict unprestatability therefore enters only when one passes to an infinite or effectively unbounded system.
The first obstruction appears already at the level of possible coarse-grainings. For an infinite microscopic phase space, the collection of all partitions of does not admit an effective exhaustive enumeration. If every mathematically possible coarse-graining were taken to represent an admissible macroscopic description, no effective vocabulary could therefore be complete. We refer to this as a failure of exhaustive formal prestatability. This is a genuine obstruction, but it must be interpreted with care: arbitrary partitions of a microscopic state space do not in general correspond to physically meaningful variables. Consequently, the non-enumerability of the full partition space does not by itself establish that the macroscopic descriptions relevant to a particular physical problem are unprestatable.
This motivates the second part of the analysis. We restrict attention to a specific operational class of macroscopic descriptions, defined by a fixed prediction problem, and construct an explicit effective vocabulary that is complete for that class. Formal prestatability is therefore granted from the outset. We then ask whether the future subset of variables that become relevant can be determined from the dynamics. Two models are constructed with the same infinite microscopic state space, the same observable, the same candidate macroscopic variables, and the same criterion of predictive relevance. They differ only in the dynamics that determines which microscopic distinctions are brought into the macroscopic description. In the first model, the relevant variables change indefinitely, but the entire future pattern can be stated in advance. The evolving macroscopic phase space is therefore pre-statable. In the second model, the dynamics performs a universal computation. Whether a candidate variable ever becomes relevant is then equivalent to whether a corresponding computation eventually halts. The complete vocabulary of possible variables is explicitly known, and the macroscopic description at every specified finite time is computable, yet there exists no algorithm that decides, for every candidate variable, whether it will ever be needed. The system is formally pre-statable but dynamically unprestatable.
Macroscopic Descriptions and Formal Prestatability
We introduce the mathematical framework used throughout the paper. The basic idea is to represent a macroscopic description as a coarse-graining of the microscopic state space.
Let denote the microscopic state space of a system. A point specifies a complete microscopic state. At this level, two distinct points of represent physically distinct microscopic configurations.
A macroscopic description generally contains less information. It identifies microscopic states whenever the distinctions between them are irrelevant for the description under consideration. Mathematically, this is naturally represented by a partition of .
A partition is a collection of disjoint subsets, or blocks, whose union is . Microscopic states belonging to the same block are regarded as indistinguishable at the macroscopic level. Equivalently, defines an equivalence relation
whenever and lie in the same block of . The corresponding macroscopic state space is the quotient
A point of is a class of microscopic states that the chosen macroscopic description does not distinguish [13, 14].
A macroscopic variable provides a particularly simple way of generating a partition. Let be a variable defined on microscopic states. It induces the partition
Two microscopic states belong to the same block of precisely when they give the same value of :
Thus specifying a macroscopic variable is equivalent, for our purposes, to specifying which microscopic distinctions that variable is capable of detecting.
Usually a macroscopic description involves more than one variable. Suppose, for example, that we retain . Two microscopic states are then macroscopically indistinguishable only if they agree on every one of these variables:
The resulting partition is the common refinement of the partitions generated by the individual variables. Given a finite family , we define its common refinement by
For the empty family, we set . The refinement retains every distinction made by any partition in .
It is useful to state the corresponding ordering explicitly. We say that a partition refines a partition if every block of is contained in a block of . In that case, distinguishes at least as many microscopic states as . Thus a finer partition corresponds to a more informative macroscopic description, while a coarser partition discards more microscopic information.
A simple example makes the construction transparent. Consider
Let
The variable separates states according to the first coordinate, whereas separates them according to the second. Each variable by itself produces a two-block partition. Their common refinement, , distinguishes all four microscopic states. The same microscopic space can therefore support descriptions of different resolution. One may retain neither distinction, only the first, only the second, or both.
The set contains every mathematically possible partition of . There is no reason, however, to regard every such partition as a physically meaningful macroscopic description. A particular physical problem will generally select only some of them. We therefore introduce an admissible class
The meaning of admissibility depends on the problem being studied. A partition might be admissible because it corresponds to experimentally accessible observables, because it is sufficient for a given prediction or control task, because it captures a relevant functional distinction, or because it satisfies some other operational criterion.
This distinction between and will be important. The former is the ambient mathematical space of all possible coarse-grainings. The latter contains only the coarse-grainings that the physical description actually allows. In the construction developed in § 5, admissibility will not be chosen arbitrarily. It will be defined by a fixed prediction problem: a macroscopic description will be admissible when it retains exactly the microscopic distinctions required to determine a specified future observable.
We can now formulate the first notion of prestatability. Suppose that the elementary distinctions available to the theory are represented by a family
We refer to as a macroscopic vocabulary. Its members should be thought of as elementary variables or distinctions that may be combined to form more detailed macroscopic descriptions.
From such a vocabulary we can construct all partitions obtained by retaining finitely many of its elements. We denote this finite-refinement closure by
Thus means that the macroscopic description can be expressed using finitely many distinctions drawn from the vocabulary.3 For prestatability, however, merely asserting the existence of such a family is not enough. The vocabulary itself must be specifiable.
Definition 1 (Effective vocabulary). A family
is an effective vocabulary if there exists a uniform effective procedure which, given , produces a finite specification of .
The precise form of such a specification depends on the model. For a coordinate variable, for example, the integer identifying the coordinate is already a finite specification. More complicated settings may require a formula, an algorithm, or some other finite rule. What matters is that the members of the vocabulary are not merely asserted to exist: they can be systematically named and described.
Effectivity alone is still insufficient. An effectively enumerable vocabulary may omit distinctions that are required by admissible macroscopic descriptions. We therefore also require completeness.
Definition 2 (Completeness). An effective vocabulary is complete for an admissible class if
In other words, every admissible macroscopic description can be constructed from finitely many distinctions belonging to the pre-specified vocabulary.
We may now state the first notion of prestatability precisely.
Definition 3 (Formal prestatability). An admissible macroscopic class is formally pre-statable if it possesses an effective vocabulary that is complete for .
The meaning of this definition is straightforward. Formal prestatability asks whether the theory possesses, in advance, a sufficiently rich language for describing every macroscopic state space that the problem may require. It does not ask which of those descriptions will actually occur. That is a separate dynamical question.
It is important that the definition is relative to the admissible class . If the physical problem allows only a restricted family of coarse-grainings, there is no reason to demand a vocabulary capable of constructing every member of . What must be pre-statable are the descriptions that can actually become relevant within the theory.
There is nevertheless a useful limiting case. If we take , we are asking whether every mathematically possible coarse-graining of the microscopic state space can be generated from an effective vocabulary. We will refer to this stronger requirement as exhaustive formal prestatability. The distinction between ordinary and exhaustive formal prestatability will be central in § 4. For a finite microscopic state space, is itself finite, so exhaustive formal prestatability presents no fundamental difficulty. For an infinite microscopic space, the situation can be very different. The first obstruction studied in this paper will arise precisely there.
The second obstruction is of another kind. Even when an effective complete vocabulary exists, it may still be impossible to determine which members of that vocabulary will enter the macroscopic description as the system evolves. To formulate that question, however, we first need an operational criterion for deciding when a microscopic distinction is relevant. We introduce such a criterion in the next section by defining the macroscopic description through a prediction task.
Predictive Relevance and Dynamical Prestatability
The previous section treated macroscopic descriptions abstractly as coarse-grainings of a fixed microscopic state space. We now need a criterion for deciding which coarse-graining is relevant in a given situation. Rather than choosing this criterion by hand, we will derive it from a prediction problem.
The idea is simple. Suppose that we are interested only in predicting a particular observable over some finite time interval. Two microscopic states should then be regarded as macroscopically equivalent whenever they lead to the same predictions for that observable. Microscopic distinctions that can never affect the prediction may be discarded, while distinctions that can affect it must be retained. In this way, the prediction task itself determines the macroscopic description.
Let be the microscopic state space of the system under consideration, and let
be the observable we wish to predict. We also introduce an internal context space . The complete microscopic state space is then
The -component of the update is written as
For the moment, we do not specify how the context itself evolves. We first ask what macroscopic description is required for a given sequence of contexts.
Fix a finite prediction horizon and a context word
Starting from an initial microscopic state , we define
The observable values generated over the prediction horizon are therefore
The map contains precisely the information relevant to the prediction task. If two microscopic states produce the same sequence of observable values, then the prediction problem has no reason to distinguish between them. We therefore define
The equivalence classes of this relation form a partition of , which we denote by
This partition has a direct operational meaning. Two microscopic states lie in the same block of exactly when they are indistinguishable with respect to the chosen prediction task. The associated quotient
is therefore the macroscopic phase space sufficient for predicting the observable over the horizon under the context word .
It is useful to emphasize the minimality of this construction. Suppose that two microscopic states and give different values of . Any description that is sufficient to determine the complete observable sequence must distinguish between them. Conversely, if they give the same value of , distinguishing them provides no additional information for the prediction task. Thus retains exactly the distinctions needed for the chosen prediction problem, and no others. Related constructions appear in observability theory, computational mechanics, and predictive-state representations [15, 16, 17, 18, 19, 20, 21, 22]. The broader problem of compressing microscopic information while preserving relevant or predictive information also underlies the information bottleneck and optimal causal inference [23, 24].
Different context words may require different predictive partitions. The prediction problem therefore determines a class
This will be the admissible macroscopic class considered from now on.
The notion of formal prestatability introduced in § 2 can now be applied directly. The predictive architecture is formally pre-statable if there exists an effective vocabulary
such that every partition in can be constructed from finitely many members of . In that case, all elementary distinctions that could be required by the prediction problem are available in advance.
Formal prestatability, however, does not tell us which of those distinctions will actually become relevant as the system evolves. To ask that question we must now introduce a dynamics for the context. Let
be a deterministic evolution of the internal context, and let be its initial state. The subsequent contexts are
Together, and define the autonomous microscopic dynamics
At time , prediction over the next steps depends on the context word
and therefore requires the predictive partition
The dynamics thus generates a sequence
of macroscopic descriptions. Equivalently, these are conditional coarse-grainings of the microscopic fiber , canonically identified with .
Suppose now that is an effective vocabulary that is complete for . We say that the elementary distinction is relevant at time when the predictive partition retains the distinction represented by . In terms of partitions, this means
The refinement condition has a simple interpretation. If refines , then two microscopic states that differ in the distinction encoded by cannot in general be identified by the predictive macroscopic description. The variable represented by must therefore be retained.
We can now ask which members of the vocabulary will ever become relevant. Define the future relevance set
This set describes the variables that will enter the macroscopic description at least once during the future evolution. It is important to distinguish this question from ordinary prediction. Ordinary prediction assumes that the descriptive variables are already fixed and asks which values those variables will take. Here we ask a different question: which variables will have to belong to the description at all? The latter question certainly depends on the dynamics, but its object is not a future microscopic or macroscopic state. Its object is the future descriptive scheme: the set of variables (distinctions) that will have to be retained as the system evolves.
This leads to the second notion of prestatability.
Definition 4 (Dynamical prestatability). Suppose that the predictive admissible class is formally pre-statable by an effective complete vocabulary . The future macroscopic description is dynamically pre-statable relative to if membership in
is decidable.
Thus dynamical prestatability asks whether, for an arbitrary candidate variable , there exists a terminating procedure that determines whether will ever be required by the future macroscopic description.
The distinction between the two notions introduced in Sections 2 and 3 can therefore be summarized as follows. Formal prestatability concerns the space of descriptions that the theory permits: do we possess an effective vocabulary rich enough to construct every admissible macroscopic description? Dynamical prestatability concerns the trajectory through that space: can we determine which elements of the available vocabulary will actually become relevant in the future?
Before constructing examples in which either notion fails, we must first establish an important baseline. For genuinely finite effectively specified systems, both questions are decidable in principle. The possibility of strict unprestatability therefore arises only when one passes to an infinite or effectively unbounded limit.
Finite Systems and the Infinite-System Limit
Before constructing examples of unprestatability, it is important to understand what can and cannot happen in finite systems. The distinction is conceptually important because both obstructions introduced in Sections 2 and 3 disappear at finite size.
Suppose first that the microscopic state space is finite. Then there are only finitely many possible partitions of . Indeed, if , then
where is the th Bell number. This number may be enormous, but it is finite. This already settles the question of exhaustive formal prestatability. Since every macroscopic description is simply one element of the finite set , one may in principle take the complete vocabulary to contain all of them. No possible coarse-graining lies beyond finite enumeration.
The same observation applies to dynamical prestatability once the dynamical state space is finite. Suppose that the context space is finite and that the context evolution in Eq. (22) is deterministic. Starting from some initial context , consider the trajectory
Because is finite, this sequence cannot visit new states indefinitely. Eventually some context must repeat. Once that happens, the subsequent evolution repeats periodically. Consequently, for any fixed finite prediction horizon , only finitely many different context words
can occur along the future trajectory. Each such word determines one predictive partition . After the context trajectory has entered its periodic part, no genuinely new predictive partition can appear. The complete future set of relevant macroscopic variables can therefore be determined by a finite search. One follows the context trajectory until a previously visited dynamical state is encountered, constructs the predictive partition at each stage, and records which candidate distinctions are retained. Once the trajectory repeats, the list is complete. This gives the finite-state baseline.
Proposition 1 (Finite-state baseline). Suppose that and are finite effectively specified sets, and that the microscopic update rule , the observable , and the context dynamics are effectively specified. Then, for every finite prediction horizon :
the predictive admissible class is formally pre-statable;
the future relevance problem is dynamically decidable.
Proposition 1 shows that neither formal nor dynamical unprestatability, in the strict sense used here, is possible in a finite effectively specified deterministic system. However, finite systems with a large number of degrees of freedom might still be unprestatable in practice. A proof of decidability permits arbitrarily large running times and memory, whereas real physical systems and observers have only finite computational resources. If the exhaustive procedure requires more time, memory, or energy than can be made available within the relevant physical regime, the future macroscopic description cannot in practice be stated in advance. Finite systems may therefore be operationally unprestatable even though they are not unprestatable in the strict mathematical sense defined here4.
The obstruction we seek is stronger, and requires some form of unboundedness. Closely related limit-dependent obstructions are known in mathematical physics: undecidable or uncomputable behavior has been established for thermodynamic observables, spectral gaps, phase diagrams, and renormalization group flows [25, 26, 27, 28]; see Ref. [29] for a review. These results concern different decision problems from the one studied here, but they likewise show how a property that is well defined for every finite instance can become undecidable in an unbounded limit.
We therefore consider a sequence of finite microscopic systems whose size increases without bound. A particularly simple example is
Each microscopic state consists of binary coordinates. For every finite ,
so is finite and Proposition 1 applies. The natural unbounded limit is
A state in contains a countably infinite sequence of binary coordinates. In the same limit, however, the partition space is uncountable. For every infinite set of cardinality , the set of its partitions (equivalently, its equivalence relations) has cardinality .5 For the infinite binary space in Eq. (33), we have
and therefore
The significance of this result becomes clear when compared with the notion of an effective vocabulary introduced in Section 2. Any effective vocabulary can contain at most countably many finitely describable elements:
Moreover, because each admissible macroscopic description is constructed from only finitely many members of the vocabulary, the finite-refinement closure is itself countable. There are only countably many finite subsets of , and each such subset selects only one finite common refinement. Hence a countable effective vocabulary can generate at most countably many macroscopic descriptions.
This immediately implies the first obstruction.
Proposition 2 (Failure of exhaustive formal prestatability). There exists no effective vocabulary that is complete for
Consequently, the full space of macroscopic coarse-grainings of is not exhaustively formally pre-statable.
The reasoning is simply one of cardinality. The finite-refinement closure of any effective vocabulary is countable, whereas is uncountable. Most partitions of the infinite microscopic state space therefore cannot be generated from any effective vocabulary in the sense defined in 3. This is the first mathematically precise sense in which prestatability can fail in the infinite-system limit. At every finite size, every possible coarse-graining can in principle be listed. In the infinite limit, no effective vocabulary can exhaust the full space of possible partitions.
The conclusion must nevertheless be interpreted carefully. The set contains every mathematically conceivable partition of the microscopic state space, including overwhelmingly many partitions for which no physical interpretation is apparent. The fact that the complete partition space is not effectively exhaustible therefore does not establish that the macroscopic descriptions relevant to a particular physical problem are themselves formally unprestatable.
A physical theory may select a much smaller admissible class , and that restricted class may possess a perfectly explicit effective complete vocabulary. This observation is essential because it separates the two obstructions introduced in § 2 and § 3. The failure of exhaustive formal prestatability follows already from the enormous size of the full partition space. To demonstrate that the second obstruction is genuinely distinct, we must construct an infinite system for which the physically admissible macroscopic descriptions possess an explicit complete vocabulary, and then ask whether the future dynamics selects from that vocabulary in a decidable way.
That is the purpose of the model introduced in the next section.
A Formally Pre-statable Predictive Architecture
We now construct a simple class of systems in which the admissible macroscopic descriptions possess an explicit effective complete vocabulary. This will allow us to study dynamical prestatability without relying on the formal obstruction established in Proposition 2.
We use the infinite binary microscopic state space introduced in Eq. (33). Thus a microscopic state consists of a countably infinite sequence of binary coordinates. We single out the coordinate as an observable readout. The remaining coordinates
will play the role of hidden microscopic variables. For every , define the binary variable
As discussed in § 2, each such variable induces a partition of the microscopic state space:
The partition therefore retains exactly one microscopic distinction: whether the th coordinate is equal to 0 or 1. We take
as our candidate macroscopic vocabulary. This vocabulary is manifestly effective. Given an integer , the corresponding partition is specified simply by asking for the value of the th binary coordinate. No search through the space of partitions is required, and every member of the vocabulary has a finite description.
The observable we wish to predict is fixed once and for all:
Thus the prediction problem concerns only the value of the readout coordinate. The remaining ingredient is a mechanism by which different hidden coordinates can become relevant to that prediction.
We introduce a context space together with a selector
The symbol means that no hidden coordinate is selected. The role of the context is simple: if , then the next value of the readout coordinate will be copied from . If , the readout is set to zero. Define
The microscopic update rule is then
The hidden coordinates therefore never change. The only effect of the context is to determine which hidden coordinate, if any, is copied into the observable register at the next step.
This simple construction is useful because it makes the relation between microscopic variables and macroscopic relevance completely transparent. If a future context selects , then knowledge of is necessary for predicting the subsequent observable value. If no relevant context selects , then that coordinate can be ignored for the prediction task.
Consider, for example, a single context satisfying . Starting from
one application of the microscopic dynamics gives
Since the next observable value is , two microscopic states that differ only in their third hidden coordinate can no longer be regarded as macroscopically equivalent for this prediction problem. The partition must be retained.
The same reasoning extends to an arbitrary finite prediction horizon. Let
be a context word of length . Since the hidden coordinates remain fixed under the dynamics, the observable sequence generated from an initial state is
The only hidden coordinates on which this sequence can depend are those selected somewhere in the context word. Define
The set contains the indices of all hidden coordinates that can influence the observable during the chosen prediction horizon. Two microscopic states and therefore give identical predictions if and only if they agree on the initial readout coordinate and on every hidden coordinate belonging to :
if and only if
The predictive partition is consequently
Equation (5.13) is the central observation of the construction. It says that the minimal macroscopic description needed for prediction consists simply of the readout variable together with the finitely many hidden coordinates that the context word makes relevant.
For example, suppose that and the successive contexts select
Then
and
Although the coordinate is consulted twice, it represents only one macroscopic distinction. The prediction problem therefore requires knowledge of precisely three variables: , , .
Notice also why only finitely many members of the vocabulary appear in each predictive description. The prediction horizon is finite, and at most one coordinate can be selected at each step. Consequently,
Every predictive partition is therefore a finite common refinement of coordinate partitions.
We can now establish the formal prestatability of the entire predictive architecture.
Proposition 3 (Formal prestatability of the predictive class). For every finite prediction horizon , the coordinate vocabulary
is effective and complete for the predictive admissible class
Proof. The vocabulary is effective because each partition is specified by the finite index . For any context word of length , the set contains at most indices. Equation (5.13) therefore expresses as a common refinement of finitely many members of . Hence
for every , and therefore
The vocabulary is thus complete for .
The significance of Proposition 3 should be emphasized. The microscopic space is infinite, and the full partition space is not exhaustively formally pre-statable, as shown in Proposition 2. But the prediction problem does not require access to arbitrary partitions of . Its admissible macroscopic descriptions form a much smaller class, and every member of that class can be constructed from the explicit coordinate vocabulary
Thus the predictive model suffers from no formal obstruction. Every elementary distinction that could ever be needed by the prediction task has already been specified. What remains undetermined is which of those distinctions the future dynamics will actually require.
To formulate this more explicitly, suppose that a context evolution and an initial context are given. At time , the relevant context word is
and the corresponding set of selected coordinates is
For every , the variable is relevant at time precisely when . The future relevance set therefore takes the particularly simple form
The readout partition is always present and will be omitted from this set, since its relevance is trivial. The problem of dynamical prestatability has thus been reduced to a concrete question: given an index , can we determine whether the future context trajectory will ever select the hidden coordinate ?
The next section shows that the answer depends entirely on the structure of the context dynamics. We will compare two systems built on exactly the same microscopic state space, observable, candidate vocabulary, and update rule. In the first, the complete future relevance set is immediately decidable. In the second, determining whether a candidate variable will ever become relevant is equivalent to the halting problem.
Two Context Dynamics
We are now in a position to ask the central dynamical question. The predictive architecture of the previous section is fixed. The microscopic state space is , the observable is always , and the candidate macroscopic vocabulary is
A context can make the variable relevant only by selecting the hidden coordinate and copying its value into the observable register. Every possible variable that could be needed by the prediction problem has therefore already been specified. What remains is to determine which coordinates the future context trajectory will actually select.
We compare two context dynamics. In the first, the sequence of selected coordinates can be written down explicitly in advance. In the second, the selection of coordinates is governed by a universal computation.
Consider first the simplest possible case. Let the context trajectory be , with
and define the selector by
Thus the successive contexts select
in order. Thus, at time , prediction over a horizon depends on the coordinates
Together with the initial observable , the prediction map is therefore
The corresponding macroscopic description is
For example, if , the relevant variables evolve as
The macroscopic description therefore changes continually. Variables that were relevant cease to be needed, while previously irrelevant variables enter the description. Yet there is no difficulty in stating the future pattern. Every hidden coordinate is eventually selected. Hence, for every ,
Given any candidate variable , we can therefore answer immediately that it will eventually become relevant. The system is dynamically pre-statable.
We now change only the process that determines which coordinates are selected. Let
be an effective enumeration of programs for a universal model of computation. For each , consider the computation obtained by running on its own index: . Define the diagonal halting set
Membership in is undecidable [30].
We now let the context dynamics simulate all of these computations in parallel by means of a standard dovetailing procedure. The idea of dovetailing is simply to ensure that no individual computation is neglected. One elementary step is performed for one program, then for another, and so on, repeatedly returning to each computation. If eventually halts, the dovetailer will therefore discover this after a finite number of steps. Let denote the initial state of the dovetailing computation, and let denote one elementary dovetailing step. The context dynamics is
The context state contains the finite information required to continue the dovetailing computation. Hence both and each individual finite step of the context evolution are effectively computable.
We now connect this computation to the predictive architecture of the previous section. Whenever a dovetailing step discovers for the first time that has halted, the corresponding context selects the coordinate . At all other steps, no hidden coordinate is selected. Thus
Recall that simply means that no hidden coordinate becomes relevant at that step. In such a context the readout is assigned the fixed value specified in Section 5.
Now consider a particular candidate variable . Suppose first that eventually halts. Because the dovetailing schedule is fair, this halt will eventually be discovered. At that moment, for some finite time . The microscopic update then copies into the observable register. Predicting the subsequent observable value therefore requires knowledge of , and the macroscopic description must retain . Hence
Conversely, suppose that never halts. The dovetailing computation can continue forever, but it will never discover a halt for this program. Consequently,
for every . The observable never depends on , and the prediction problem never requires the distinction . Therefore
Combining the two directions gives
Equivalently, for every finite prediction horizon ,
The future relevance problem is therefore undecidable.
Proposition 4 (Dynamical unprestatability). For every fixed finite prediction horizon , the universal model is formally pre-statable but dynamically unprestatable. Its candidate macroscopic vocabulary is effective and complete, but there exists no algorithm that decides, for every , whether will ever become relevant.
Proof. Formal prestatability was established in Proposition 3: every admissible predictive partition is a finite refinement of members of
Suppose now that there existed a terminating algorithm which, given , decided whether would ever become relevant. By Eq. (62), the same algorithm would decide whether eventually halts. This would decide membership in the diagonal halting set , contradicting the undecidability of the halting problem.
The contrast between the two models is particularly instructive. In both cases the microscopic phase space is completely specified. The observable is completely specified. The elementary macroscopic vocabulary is completely specified. Every admissible macroscopic description is constructed from that vocabulary, and the evolution at every specified finite time can be computed. The difference lies solely in the global structure of the context dynamics.
In the reducible model, the sequence of selected coordinates is
so the complete future relevance set can be stated immediately. In the universal model, a coordinate is selected precisely when a corresponding computation is discovered to halt. Every positive instance can eventually be witnessed: if becomes relevant, running the dynamics long enough will eventually reveal that fact. What cannot be determined in general is that will never become relevant, since this would require knowing that the corresponding computation will never halt.
Conclusion
At first sight, macroscopic unprestatability appears paradoxical. If the microscopic phase space is complete and the laws governing its evolution are fully specified, how can anything about the system’s future macroscopic description remain unknown or even unprestatable? After all, every macroscopic property must ultimately be grounded in the microscopic states, and no new microscopic possibilities can emerge outside the original phase space. One might therefore expect microscopic completeness to guarantee macroscopic prestatability.
The resolution lies in recognizing that microscopic states and macroscopic descriptions are fundamentally different objects. Macroscopic descriptions are ways of organizing and distinguishing microscopic states, and their space of possibilities can be vastly larger than the microscopic phase space itself. Indeed, even a finite phase space admits exponentially many subsets and an even larger number of possible partitions. For infinite spaces, the difference is no longer merely quantitative, but qualitative: the two spaces have different cardinality. Thus, knowing the complete microscopic phase space does not imply having a practically or algorithmically accessible catalogue of its possible macroscopic descriptions. The latter may be formally specified without being effectively enumerable.
Our construction takes this distinction further by showing that even when the relevant macroscopic descriptions are formally pre-statable, determining which of them will become relevant during the system’s evolution can be undecidable. Formal prestatability therefore does not guarantee dynamical prestatability, namely that the future macroscopic organization can be anticipated.
References
- [1]S. A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution (Oxford University Press, New York, 1993).
- [2]S. A. Kauffman, Investigations (Oxford University Press, New York, 2000).
- [3]G. Longo, M. Montévil, and S. A. Kauffman, “No entailing laws, but enablement in the evolution of the biosphere,” in Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation, 1379–1392 (2012). https://doi.org/10.1145/2330784.2330946
- [4]G. Longo and M. Montévil, “Extended criticality, phase spaces and enablement in biology,” Chaos, Solitons & Fractals 55, 64–79 (2013). https://doi.org/10.1016/j.chaos.2013.03.008
- [5]S. A. Kauffman and A. Roli, “The world is not a theorem,” Entropy 23, 1467 (2021). https://doi.org/10.3390/e23111467
- [6]S. A. Kauffman, “Is there a fourth law for non-ergodic systems that do work to construct their expanding phase space?” Entropy 24, 1383 (2022). https://doi.org/10.3390/e24101383
- [7]S. A. Kauffman and A. Roli, “A third transition in science?” Interface Focus 13, 20220063 (2023). https://doi.org/10.1098/rsfs.2022.0063
- [8]A. Roli, S. Succi, and S. A. Kauffman, “Artificial intelligence: unpredictable or unprestatable?” Frontiers in Physics 14, 1768372 (2026). https://doi.org/10.3389/fphy.2026.1768372
- [9]F. Tria, V. Loreto, V. D. P. Servedio, and S. H. Strogatz, “The dynamics of correlated novelties,” Scientific Reports 4, 5890 (2014). https://doi.org/10.1038/srep05890
- [10]T. Taylor et al., “Open-ended evolution: Perspectives from the OEE workshop in York,” Artificial Life 22, 408–423 (2016). https://doi.org/10.1162/ARTL_a_00210
- [11]N. Packard, M. A. Bedau, A. Channon, T. Ikegami, S. Rasmussen, K. O. Stanley, and T. Taylor, “An overview of open-ended evolution: Editorial introduction to the open-ended evolution II special issue,” Artificial Life 25, 93–103 (2019). https://doi.org/10.1162/artl_a_00291
- [12]J. J. Gibson, The Ecological Approach to Visual Perception (Houghton Mifflin, Boston, 1979).
- [13]H. Atmanspacher, “On macrostates in complex multi-scale systems,” Entropy 18, 426 (2016). https://doi.org/10.3390/e18120426
- [14]C. R. Shalizi and C. Moore, “What is a macrostate? Subjective observations and objective dynamics,” Foundations of Physics 55, 2 (2025). https://doi.org/10.1007/s10701-024-00814-1
- [15]E. D. Sontag, “On the observability of polynomial systems, I: Finite-time problems,” SIAM Journal on Control and Optimization 17, 139–151 (1979). https://doi.org/10.1137/0317011
- [16]H. Nijmeijer, “Observability of autonomous discrete time non-linear systems: A geometric approach,” International Journal of Control 36, 867–874 (1982). https://doi.org/10.1080/00207178208932936
- [17]R. Hermann and A. J. Krener, “Nonlinear controllability and observability,” IEEE Transactions on Automatic Control 22, 728–740 (1977). https://doi.org/10.1109/TAC.1977.1101601
- [18]J. P. Crutchfield and K. Young, “Inferring statistical complexity,” Physical Review Letters 63, 105–108 (1989). https://doi.org/10.1103/PhysRevLett.63.105
- [19]J. P. Crutchfield, “The calculi of emergence: Computation, dynamics and induction,” Physica D 75, 11–54 (1994). https://doi.org/10.1016/0167-2789(94)90273–9
- [20]C. R. Shalizi and J. P. Crutchfield, “Computational mechanics: Pattern and prediction, structure and simplicity,” Journal of Statistical Physics 104, 817–879 (2001). https://doi.org/10.1023/A:1010388907793
- [21]M. L. Littman, R. S. Sutton, and S. Singh, “Predictive representations of state,” in Advances in Neural Information Processing Systems 14, 1555–1561 (2001).
- [22]A. C. Costa, T. Ahamed, D. Jordan, and G. J. Stephens, “Maximally predictive states: From partial observations to long timescales,” Chaos 33, 023136 (2023). https://doi.org/10.1063/5.0129398
- [23]N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” in Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing, 368–377 (1999).
- [24]S. Still, J. P. Crutchfield, and J. P. Ellison, “Optimal causal inference: Estimating stored information and approximating causal architecture,” Chaos 20, 037111 (2010). https://doi.org/10.1063/1.3489885
- [25]M. Gu, C. Weedbrook, Á. Perales, and M. A. Nielsen, “More really is different,” Physica D: Nonlinear Phenomena 238, 835–839 (2009). https://doi.org/10.1016/j.physd.2008.12.016
- [26]T. S. Cubitt, D. Pérez-García, and M. M. Wolf, “Undecidability of the spectral gap,” Nature 528, 207–211 (2015). https://doi.org/10.1038/nature16059
- [27]J. Bausch, T. S. Cubitt, and J. D. Watson, “Uncomputability of phase diagrams,” Nature Communications 12, 452 (2021). https://doi.org/10.1038/s41467-020-20504-6
- [28]J. D. Watson, E. Onorati, and T. S. Cubitt, “Uncomputably complex renormalisation group flows,” Nature Communications 13, 7618 (2022). https://doi.org/10.1038/s41467-022-35179-4
- [29]A. Perales-Eceiza, T. Cubitt, M. Gu, D. Pérez-García, and M. M. Wolf, “Undecidability in physics: A review,” Physics Reports 1138, 1–29 (2025). https://doi.org/10.1016/j.physrep.2025.06.004
- [30]A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society s2-42, 230–265 (1937). https://doi.org/10.1112/plms/s2-42.1.230