Abstract

Classical undecidability comes from self-reference applied to a fixed input. A program is handed a description, and the description does not change while the program runs. Many real limits have a different shape: the act of finding out alters what is being found out. Measuring a quantum system changes its state. Evaluating an economic plan consumes the resources the plan allocates. Driving down a road changes the traffic on the roads next to it.

Reflexive Computational Systems formalize that shape. A system is a state space together with an interaction function that returns an outcome and a transformation function that consumes the outcome and returns the next state. The transformation reads the outcome as well as the interaction, and that dependence is what makes the structure reflexive. Deterministic and non-deterministic variants are given, and three consequences are proved: prior states can be unrecoverable, information obtained by interaction describes the state the interaction produced, and no prediction is stable when the system is built to falsify it.

Two undecidability results follow, and they are different results. Fixing a property in advance and reducing the halting problem to it shows that no interactive machine decides termination across a family of these systems, with the bound surviving bounded-error randomization. Letting the property depend on the predictor's own forecast shows something else: in a counter-predictive system, no interactive machine can finish with a recorded verification that matches the state it has produced. The first result is undecidability in the classical sense on an interactive family. The second is the failure of a fixed point, and it is what distinguishes reflexive limits from static ones.

Reflexivity in Plain Terms

Publish a poll a week before an election and the poll changes the vote. Nobody lied. People who see their side comfortably ahead stay home, and people who see it just behind turn out. The number was accurate when it was taken, and publishing it made the election different from the one it described.

That pattern has a shape worth naming. Something is done, a result comes back, and the result itself determines how the thing being examined changes. Not just the act, the result: a high reading leads somewhere different from a low one. Once the loop closes that way, three familiar troubles follow.

The first is that you may not be able to work backwards. Two different starting points can end at the same place after a measurement, so the reading plus the outcome do not tell you where you began. The second is that what you learn is already out of date, and not by accident: the reading describes the state your reading produced. The third is the sharpest. If the system is built to do the opposite of whatever you predict, then announcing an accurate prediction makes it wrong, and announcing an inaccurate one makes it right. There is no answer that stays true once given.

The last case is worth separating from the familiar one. Turing showed that no program can decide, for every program, whether it halts. There the question is fixed and the difficulty is self-reference in the encoding. Here the question is not fixed: it is about a system that reacts to being asked. Both limits are real, they have different sources, and a stubborn traffic jam that worsens wherever the navigation app sends people is an instance of the second kind.

1. Limits That Come from Interaction

Every discipline that studies its own limits has found a version of this. In physics, measurement disturbs what it measures, and the disturbance depends on the outcome obtained. In thermodynamics, recording and erasing information costs energy, a fact Landauer (1961) fixed at k_BT ln 2 per erased bit. In computer science, Turing (1936) showed that a fixed question about programs can be undecidable, and Rice (1953) extended that to every non-trivial semantic property. In economics, publishing a forecast moves the market the forecast is about, which Grunberg and Modigliani (1954) and Simon (1954) analysed as a problem about fixed points.

These look like separate difficulties, and one structure is common to them. Information is not acquired from outside the system. The acquisition is an event inside it, and the event's outcome determines how the system changes. Reflexivity names that structure, and Reflexive Computational Systems make it precise enough to prove things about.

A concrete case makes the target clear. A traveller plans a route through a city where each road taken changes the traffic on the roads nearby, and the change depends on which road was taken. The planner cannot treat the map as fixed, because the map is a function of the plan being executed. This is not a harder version of an ordinary routing problem. It is a routing problem whose instance is defined by the solution attempt, and the same reversal appears in measurement, in planning, and in self-prediction.

2. Reflexive Computational Systems

2.1 The Deterministic Case

The whole content is in the third argument of T. A transformation of the form T(x, y) would describe a system that is disturbed by being probed, which is ordinary. Writing T(x, y, o) says that the disturbance depends on what the probe returned, so two runs of the same interaction that happen to yield different outcomes leave the system in different places. That is the reflexive coupling, and everything below follows from it.

2.2 The Non-Deterministic Case

The coupling survives the move to distributions. The outcome is drawn first, and the distribution over next states is conditioned on the outcome that was drawn. A model in which the next state depended only on (x, y) would be an ordinary Markov decision process; the conditioning on o is what keeps it reflexive.

2.3 The Cycle

Both variants run the same loop. From state x an interaction y produces outcome o, deterministically through V or by sampling V_prob; the outcome then selects the next state through T or by sampling T_prob; and the loop repeats from x′. A run is the sequence

x₀ →(y₀, o₀) x₁ →(y₁, o₁) x₂ → …

where o_i is the outcome at x_i and x_i+1 = T(x_i, y_i, o_i).

2.4 Two Instances

A degrading sensor (deterministic). Let a state be a pair (temp, acc), the true temperature and the sensor's accuracy in [0,1], with the single interaction "measure". Let

V((temp, acc), measure) = ( temp·(1 + α(1 − acc)),  β(1 − acc) )

returning a reading biased by the accuracy shortfall together with an error estimate, and let

T((temp, acc), measure, (temp_m, err)) = ( temp − γ|temp − temp_m|,  max(0, acc(1 − δ)) )

so that the probe perturbs the temperature by an amount fixed by the reading it returned, and the sensor degrades. The transformation reads temp_m, a component of the outcome, which is what makes the example reflexive rather than merely noisy.

Projective measurement (non-deterministic). Let X be the density operators on a finite-dimensional Hilbert space, Y a set of observables, and O the union of their spectra. For an observable A = Σ_k λ_k P_k, let

P(λ_k | ρ, A) = Tr(P_k ρ)         (Born rule)
T_prob(ρ, A, λ_k) = δ at  ρ′_k = P_k ρ P_k / Tr(P_k ρ)   when Tr(P_k ρ) > 0

which is von Neumann's (1932) measurement postulate in the form Lüders (1951) gave it. The outcome is drawn from the Born distribution and the post-measurement state is determined by which outcome was drawn. Quantum measurement is a reflexive system in the exact sense of Definition 2.2, and the framework does not explain the Born rule, which enters here as an input.

2.5 What Makes This Different from Ordinary Computation

A Turing machine reads a fixed input. The machine's configuration changes as it runs and the input string does not, so a question about the input has an answer that stays put while the machine looks for it. Verification in complexity theory has the same character: an instance and a certificate are both static, and checking them changes neither.

In a reflexive system the object under examination evolves as a consequence of the examination, and the direction of that evolution depends on what the examination returned. This places the framework among models of interactive computation, where a machine exchanges values with an environment over time rather than consuming a fixed input. Wegner (1997) argued that interaction changes what computation means, and Goldin and colleagues (2004) gave the model used below: persistent Turing machines, which retain their configuration between interactions. Reflexivity adds one requirement to that setting, that the environment's transition depends on the outcome it returned, and the results below come from that requirement.

3. Three Consequences of the Cycle

Three results follow from the coupling alone, before any question of decidability arises. Each says what an observer interacting with such a system can and cannot come to know.

3.1 Prior States Can Be Unrecoverable

The condition is a hypothesis about the system and not a theorem about all of them. A reflexive system whose transformations are injective loses nothing, which is why the condition appears explicitly wherever the loss is claimed.

3.2 Information Describes the State the Interaction Produced

This is the formal content of the blood-pressure cuff. Each reading is accurate about the state it found, and that state is one the reading helped bring about. Sequential measurements of quantities that do not commute have the same structure: the first measurement fixes the context in which the second is taken, so the pair of results describes a trajectory rather than a single prior state. The uncertainty relation is proved from the Hilbert-space representation and a supplied commutator, which is a separate argument, and the reflexive structure supplies the operational picture rather than the inequality.

3.3 No Prediction Is Stable Against a Counter-Predictive System

The registered outcome and the resulting state always disagree, so the pair (o, x′) is never consistent. This is the fixed-point failure at the centre of the framework, and Section 5 turns it into a statement about machines.

3.4 The Probabilistic Version

Softening the prediction into a probability does not restore stability. Let p(x, y) = P(accurate | x, y) be the chance that y holds at x, and suppose the transformation drives that chance the other way: for some δ₁, δ₂ > 0,

E[ p(x′, y) | x, y, accurate ]   ≤ p(x, y) − δ₁
E[ p(x′, y) | x, y, inaccurate ] ≥ p(x, y) + δ₂

Accuracy near one decays and accuracy near zero recovers, so a predictor facing such a system settles into an intermediate band. Perfect prediction and perfect anti-prediction are equally unavailable, which is the probabilistic image of Lemma 3.4.

3.5 What the Three Lemmas Give

• Information loss, under the non-injectivity hypothesis of Lemma 3.1.
• Context shift, unconditionally, by Lemma 3.2: what an interaction reveals is a property of the state that interaction produced.
• Fixed-point failure, in counter-predictive systems, by Lemmas 3.4 and 3.5.

The first two constrain what can be learned; the third constrains what can be settled. Section 5 shows that the third is the one that yields a limit classical undecidability does not already cover.

4. Where the Structure Appears

4.1 Measurement

Section 2.4 already exhibits projective measurement as an ND-RCS. The observer effect is the dependence of T_prob on the outcome drawn from V_prob, and successive measurements of incompatible observables instantiate Lemma 3.2, since the second acts on the state the first produced. The framework supplies the operational shape of these facts. It does not derive the Born rule, the commutator, or the uncertainty relation, each of which requires the Hilbert-space structure as a separate input.

4.2 Irreversibility and the Cost of Records

Reversing a process to reach a specific earlier microstate requires knowing that microstate, and knowledge of it is obtained by interactions that form a reflexive cycle. Lemma 3.1 gives conditions under which those interactions destroy the distinctions needed, and Lemma 3.2 says the information obtained describes a later state. This is a constraint on the epistemic route to reversal, and it is not a proof that reversal is physically impossible: the second law is established by other arguments, and the reflexive account describes why an observer inside the process cannot assemble what reversal would require.

Where a transformation is logically irreversible, in the deterministic case a non-injective T and in the probabilistic case a T_prob that mixes distinct predecessors, its physical implementation obeys Landauer's (1961) bound of k_BT ln 2 per erased bit, analysed further by Bennett (1982). A demon that sorts molecules must record outcomes and reset its memory, and those steps carry the cost, which is the reflexive reading of why the demon buys no free work. Whether a given RCS erases anything is a property of the specific T, so the thermodynamic consequence attaches to systems that are shown to be non-injective and not to reflexivity in general.

4.3 Economic Calculation

Mises (1920) and Hayek (1945) argued that a central planner lacks access to knowledge that only prices reveal. There is a second obstacle of a computational kind, and it is reflexive. Model the economy as a D-RCS whose state (R, P, U, C) records resources, production possibilities, utilities, and the planner's remaining computational budget. Let interactions be candidate plans, let V(x, A) = (feasible, metrics, C_A) evaluate a plan and report the cost of evaluating it, and let T(x, A, o) deduct C_A from the budget.

An optimal plan has to account for the cost of its own selection, and that cost is known only after the evaluation that consumes it. By Lemma 3.2 each evaluation reports on a state whose budget has already been reduced by earlier evaluations, so the planner never evaluates plans against the resources actually available at the moment of choosing. The knowledge problem and the computational problem are independent, and this model addresses the second.

4.4 Routing on a Map That Reacts

The mapping to Definition 2.1 is direct: states are distance functions, interactions are edges, outcomes are the costs incurred, and T(d, e, cost) = τ(d, e). A congestion rule that raises the cost of edges adjacent to the one just used gives the traffic example of Section 1.

The proposition locates the phenomenon. Reflexivity is not a hardness property, which is why a deterministic reactive map sits in the same class as a static one, and the limits it does impose are limits on settlement rather than on computation — which is what Theorem 5.5 proves. In the non-deterministic variant the expected cost of a single fixed tour is a sum over exponentially many trajectories of the update rule, so it need not be computable in polynomial time, and the decision problem is not known to lie in NP. The same reversal appears in the Canadian traveller problem of Papadimitriou and Yannakakis (1991), where edge costs are revealed as the traveller arrives, and where the adaptive version is PSPACE-complete. Time-dependent and dynamic vehicle routing, surveyed by Psaraftis (1995), studies the case where the map changes on a schedule rather than in response to the route.

5. Two Undecidability Results

Two limits arise for machines interacting with these systems, and they have different sources. The first fixes a question in advance and reduces the halting problem to it. The second lets the question depend on the probe, and it is the one that does not reduce to any static result.

5.1 Machines That Persist Between Interactions

This is the persistent Turing machine of Goldin and colleagues (2004), coupled to an environment that transforms according to the outcomes it returns.

5.2 A Fixed Property That No Machine Decides

Randomization with bounded error does not help, provided the machine's resources are bounded in a way that keeps its behaviour enumerable.

What Theorems 5.3 and 5.4 establish is that the interactive setting inherits classical undecidability rather than escaping it. The property is fixed before any decider is considered, and the strength of the result comes from the halting problem. This is worth stating because the interesting limit is the next one, and it is a different limit.

5.3 A Question That No Interaction Can Settle

Now let the question concern a prediction, and let the system be built to react to it. The obstruction changes character: nothing is undecidable in the classical sense, and instead no answer survives the act of obtaining it.

The difference from Section 5.2 is the source of the difficulty. There the property was fixed and the machine could not compute it. Here the machine computes something exactly, records it correctly, and the record is false of the world the recording produced. No amount of computation repairs this, because computation is not what is missing.

5.4 Which Limit Is Which

The two results are worth keeping apart, because they are often merged.

• Fixed property, uniform decider excluded. Theorems 5.3 and 5.4 fix TERM in advance and rule out a total decider on the family. The construction is a reduction, the limit is classical, and interaction is the setting rather than the cause.
• Live property, no stable answer. Theorem 5.5 lets the property depend on the probe. The limit is a fixed-point failure of the kind Lemma 3.4 describes, and it does not follow from the halting problem or from Rice's (1953) theorem, both of which concern properties fixed before the decider is chosen.

Wolpert (2008) proved a related bound for physical inference devices embedded in the universe they measure, and reached the same conclusion by a different route: two such devices cannot be mutually correct, and no device is correct about every question concerning a universe containing it. The reflexive framework isolates the mechanism that forces this in the interactive case, which is the dependence of the transformation on the outcome.

6. What Follows

6.1 For Computation

The interactive setting inherits classical undecidability, which Theorem 5.3 shows, and it also carries a limit of its own, which Theorem 5.5 shows. The second matters for embedded computation, where the algorithm is part of the system it analyses and its queries are events in that system. An algorithm outside the system is not subject to Theorem 5.5, which is the formal reason external audit is worth more than introspection.

6.2 For Modelling and Control

An agent that is part of what it models, and whose actions have consequences that depend on their outcomes, cannot hold a stable complete model of the system it belongs to. Control that assumes perfect prediction is therefore misspecified for this class, and control designed around margins, monitoring, and revision is not. In artificial systems the point is concrete: an agent whose actions change its environment, including the humans and other agents in it, changes the distribution its own forecasts were fitted to, so a forecast validated before deployment is evidence about a system that deployment has altered.

6.3 For Social Systems

Published forecasts change behaviour, which Merton (1948) described as the self-fulfilling prophecy. The reflexive framing sharpens the question into one about fixed points. Where the reaction to a forecast moves the outcome toward it, a stable published forecast can exist, which is the case Grunberg and Modigliani (1954) and Simon (1954) analysed. Where the reaction moves the outcome away, Lemma 3.4 applies and no stable forecast exists. Which case holds is a property of the reaction function, and it is an empirical question about the particular system.

6.4 For Physics and Information

Reflexivity gives the common shape of measurement disturbance, the epistemic obstacles to reversal, and the cost of records, without replacing the physics. The Born rule, the commutator, the second law and Landauer's bound enter as the physics of each case, and what the framework supplies is the structure they share: an outcome that determines how the system it was drawn from changes. That structure carries consequences of its own, proved in Section 3 and applied in Section 5, and they hold across every instance regardless of which physics fills it.

7. Conclusion

Reflexivity is the property that a system's transformation depends on the outcome of the interaction that examined it. Reflexive Computational Systems make that precise in deterministic and probabilistic forms, and three consequences follow from the coupling: prior states can be unrecoverable, what an interaction reveals is a property of the state it produced, and no prediction is stable against a system built to invert it.

Two limits follow for machines. Fixing a property in advance and reducing the halting problem shows that interactive computation inherits classical undecidability, and randomization with bounded error does not evade it. Letting the property depend on the probe shows a limit of a different kind: a machine can compute correctly, record correctly, and still end holding a verification that the world it produced has falsified. The first limit is about what can be computed. The second is about what can be settled, and it is the one that belongs to interaction.

For systems where an observer is embedded and its interactions are transformative, the practical consequence is that the goal of a stable, complete, externally verifiable account has to be replaced. What remains available is exactly what Sections 3 and 5 leave standing: bounded knowledge, revisable models, and predictions that are useful without being fixed points.

References

• Bennett, Charles H. "The Thermodynamics of Computation: A Review." International Journal of Theoretical Physics 21, no. 12, 1982, 905–940.
• Goldin, Dina Q., Scott A. Smolka, Paul C. Attie, and Elaine L. Sonderegger. "Turing Machines, Transition Systems, and Interaction." Information and Computation 194, no. 2, 2004, 101–128.
• Grunberg, Emile, and Franco Modigliani. "The Predictability of Social Events." Journal of Political Economy 62, no. 6, 1954, 465–478.
• Hayek, F. A. "The Use of Knowledge in Society." The American Economic Review 35, no. 4, 1945, 519–530.
• Karp, Richard M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, edited by Raymond E. Miller and James W. Thatcher, Plenum Press, 1972, 85–103.
• Landauer, Rolf. "Irreversibility and Heat Generation in the Computing Process." IBM Journal of Research and Development 5, no. 3, 1961, 183–191.
• Lüders, Gerhart. "Über die Zustandsänderung durch den Meßprozeß." Annalen der Physik 443, nos. 5–8, 1951, 322–328.
• Merton, Robert K. "The Self-Fulfilling Prophecy." The Antioch Review 8, no. 2, 1948, 193–210.
• Mises, Ludwig von. "Die Wirtschaftsrechnung im sozialistischen Gemeinwesen." Archiv für Sozialwissenschaft und Sozialpolitik 47, 1920, 86–121.
• Papadimitriou, Christos H., and Mihalis Yannakakis. "Shortest Paths Without a Map." Theoretical Computer Science 84, no. 1, 1991, 127–150.
• Psaraftis, Harilaos N. "Dynamic Vehicle Routing: Status and Prospects." Annals of Operations Research 61, 1995, 143–164.
• Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Transactions of the American Mathematical Society 74, no. 2, 1953, 358–366.
• Simon, Herbert A. "Bandwagon and Underdog Effects and the Possibility of Election Predictions." Public Opinion Quarterly 18, no. 3, 1954, 245–253.
• Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42, no. 1, 1936, 230–265.
• von Neumann, John. Mathematische Grundlagen der Quantenmechanik. Springer, 1932.
• Wegner, Peter. "Why Interaction Is More Powerful Than Algorithms." Communications of the ACM 40, no. 5, 1997, 80–91.
• Wolpert, David H. "Physical Limits of Inference." Physica D 237, no. 9, 2008, 1257–1281.