Consistency of Generalised Probabilistic Theories is Undecidable

Imagine you are an architect trying to design a new universe. You have a set of blueprints (the rules of physics) that describe how things exist and how they interact. In the real world, we have Classical Mechanics (like billiard balls) and Quantum Mechanics (like fuzzy, spooky particles). But what if you wanted to invent a third kind of physics? Maybe one where things are "fuzzier" than quantum mechanics, or where information behaves in weird new ways.

This is what Generalised Probabilistic Theories (GPTs) are: a giant, flexible toolbox for inventing new universes.

The paper by Serge Massar asks a simple question: "If I give you a few new rules for how things move or how they get entangled, can you be 100% sure that your new universe won't collapse into nonsense?"

The answer, surprisingly, is No. In fact, it is mathematically impossible to ever know for sure.

Here is the breakdown using simple analogies.

1. The "Lego Universe" Problem

Think of a GPT as a set of Lego bricks.

States are the shapes of the bricks.
Measurements are the ways you can snap them together.
Transformations are the instructions on how to move or rotate the bricks.

In a consistent universe, every time you snap bricks together, the probability of them staying together must be a number between 0% and 100%. You can't have a -10% chance of a brick existing. That would be nonsense.

Massar's paper looks at two specific ways people try to expand their Lego universe:

Adding Movement: "Let's add a rule that says 'if you push a brick, it spins'."
Adding Entanglement: "Let's add a rule that says 'if two bricks touch, they become a super-brick'."

2. The Infinite Chain Reaction

The problem isn't just adding one new rule. It's what happens when you let those rules run wild.

The Transformation Trap (The Infinite Dance):
Imagine you have a dance move (a transformation). If you do it once, it's fine. If you do it twice, it's fine. But what if you do it 1,000 times? Or 1,000,000 times?
In these theories, doing a move over and over generates new moves. It's like a dance that evolves every time you do it.

The Issue: To prove your universe is safe, you have to check that every single possible dance sequence (even the ones nobody has ever thought of yet) results in a valid probability (0 to 1).
The Catch: Because you can combine moves in infinite ways, you have to check an infinite list of conditions.

The Entanglement Trap (The Teleportation Loop):
Imagine you have a "teleportation" machine. You put a brick in, and it comes out on the other side, but slightly changed.

The Issue: If you teleport a brick, then teleport the result, then teleport that result... you generate a never-ending stream of new, weird bricks.
The Catch: Just like the dance, you have to check if every single one of these infinitely generated bricks is a valid shape. If even one of them turns into a "negative brick" (a probability less than zero), your whole universe collapses.

3. The "Halting Problem" Connection

This is where the paper gets really deep. It connects physics to computer science.

There is a famous problem in computing called the Halting Problem. It asks: "If I give you a computer program, can you write a second program that looks at it and tells you if it will run forever or stop?"
The answer is No. It is mathematically impossible to build a "stop-checker" that works for every program. Some programs will just run forever, and you can't know that without actually running them forever.

Massar proves that checking if your new physics theory is consistent is exactly the same problem as the Halting Problem.

The Analogy: Your physics theory is the "program." The "infinite dance" or "infinite teleportation" is the program running.
The Result: There is no "magic calculator" you can build that will look at your new rules and say, "Yes, this is safe" or "No, this breaks."
Why? Because to know if it breaks, you might have to wait for the infinite chain of events to finish. But since the chain is infinite, you wait forever. And because of the math behind it, you can never shortcut that wait.

4. Why Does This Matter?

You might think, "So what? We just use computers to check the first million steps."

The paper argues that this is a fundamental limit of knowledge, not just a lack of computing power.

The "Black Box" of Physics: If you try to invent a new theory of physics that includes complex dynamics or entanglement, you cannot mathematically prove it works. You can only guess or assume it works.
The "Numerical Search" Trap: Scientists are currently using computers to search for these new theories (finding "consistent" ones by trial and error). Massar warns that this is like trying to find a needle in a haystack that keeps growing. Because the problem is "undecidable," these computer searches might be finding things that look safe for a while but are actually doomed to fail later.

The Big Takeaway

Imagine you are building a bridge. Usually, you can calculate the stress on every beam and say, "This bridge will hold."
Massar is saying that for certain types of "universes" (Generalised Probabilistic Theories), there is no formula to calculate the stress.

You can build the bridge, and it might look fine for a million years. But because the rules of the universe allow for infinite, complex interactions, there is no way to guarantee it won't suddenly collapse tomorrow due to a weird combination of events you couldn't predict.

In short: We cannot fully automate the creation of new physical theories. We will always need human intuition, extra assumptions, or "physical guesses" to decide if a new theory makes sense, because the math itself refuses to give us a definitive "Yes" or "No."

Here is a detailed technical summary of the paper "Consistency of Generalised Probabilistic Theories is Undecidable" by Serge Massar.

1. Problem Statement

The paper addresses a fundamental limitation in the framework of Generalised Probabilistic Theories (GPTs). GPTs provide a unifying mathematical structure for classical mechanics, quantum mechanics, and hypothetical physical theories. While GPTs are used to derive physical principles (like no-cloning or contextuality) and study resources (like entanglement), the paper investigates the computational decidability of extending these theories.

Specifically, the author asks: Given a finite set of initial states, effects, and transformations (or entangled states/effects), is it possible to algorithmically determine if the closure of these elements under composition (for transformations) or teleportation (for entanglement) remains consistent with the axioms of GPTs?

Consistency in this context requires that:

All generated states and effects remain within the valid cones (convex, closed, pointed).
All outcome probabilities calculated via the inner product of states and effects remain non-negative and bounded by 1.

The paper proves that determining this consistency is undecidable, meaning it is computationally equivalent to the Halting Problem for Turing machines.

2. Methodology

The proof strategy relies on reducing known undecidable problems in automata theory and matrix analysis to the consistency problem of GPTs.

A. Mathematical Framework

GPT Axioms: States ( $\omega$ ) and effects ( $e$ ) are vectors in a real vector space. Probabilities are given by $P(e|\omega) = e^T \omega$ . The theory requires $0 \le e^T \omega \le 1$.
Transformations: Modeled as linear maps $T$ . In a specific coordinate system (where the unit effect is the first basis vector), transformations take a block form:
$T = \begin{pmatrix} 1 & 0 \\ s & R \end{pmatrix}$
where $R$ acts on the "Bloch" vector. Composing transformations corresponds to multiplying the $R$ blocks.
Teleportation: In GPTs, teleportation (remote state preparation) acts as a probabilistic transformation. Iterating teleportation on entangled states generates new states via matrix products analogous to the $R$ blocks in transformations.

B. Reduction to Undecidable Problems

The author utilizes two specific undecidable results from theoretical computer science:

Strict Emptiness of Probabilistic Automata (Theorem 1): Given a set of stochastic matrices $\{M_i\}$ , a start vector $q$ , a final vector $F$ , and a cut-point $\lambda$ , it is undecidable whether there exists a word $w$ such that $F^T M_w q > \lambda$ .
Unboundedness of Matrix Products (Theorem 2): Given a set of matrices $\{M_i\}$ , it is undecidable whether the spectral norm of all possible products $M_w$ remains bounded.

The paper constructs GPTs where the consistency conditions (positivity of probabilities) map directly to these matrix problems.

3. Key Contributions and Results

The paper presents two main categories of undecidability results:

Result I: Undecidability of Discrete Dynamics (Transformations)

Theorem 3: Given a finite set of transformations $T_0$ $T_{0}$ , it is undecidable whether the set of all compositions $T_{gen}$ $T_{g e n}$ (the closure under composition) can be completed with some state and effect sets to form a consistent GPT.
- Mechanism: If the matrix products associated with the transformations become unbounded, the positivity condition ( $e^T T \omega \ge 0$ ) will eventually be violated for any full-dimensional state/effect set. Since boundedness is undecidable, consistency is undecidable.
Theorem 4: Given a specific single-party GPT $(S_0, E_0)$ $(S_{0}, E_{0})$ and a consistent set of transformations $T_0$ $T_{0}$ , it is undecidable whether the triple $(S_0, E_0, T_0)$ $(S_{0}, E_{0}, T_{0})$ forms a consistent generating set.
- Mechanism: By embedding the "Strict Emptiness" problem into the specific choice of states and effects, the positivity of probabilities for specific sequences of transformations becomes equivalent to the undecidable cut-point problem.

Result II: Undecidability of Entanglement in Translation-Invariant Systems

Context: The paper considers infinite systems with translation invariance (e.g., 1D spin chains), described by a finite "unit cell" and a translation operator.
Theorem 5: Given a translation-invariant set of multipartite entangled states and effects, it is undecidable whether they can be completed with translation-invariant single-party states/effects to form a consistent GPT.
- Mechanism: Teleportation in this 1D chain allows a state to be "moved" along the chain. Iterating this process generates a sequence of transformations equivalent to matrix products. The unboundedness of these products leads to negative probabilities, which is undecidable to check.
Theorem 6: Given a consistent translation-invariant single-party GPT and a consistent set of multipartite entangled states/effects, it is undecidable whether the combined system is consistent.
- Mechanism: Similar to Theorem 4, the specific choice of states and effects in the unit cell encodes the probabilistic automata problem. The consistency of the infinite chain depends on whether specific matrix products exceed a threshold, which is undecidable.

4. Technical Significance

Fundamental Obstruction: The results demonstrate that there is no general algorithm to verify if a proposed extension of a GPT (adding dynamics or entanglement) is physically valid. This is a stronger result than previous undecidability proofs in physics (like the spectral gap), as it questions the very existence of the theory's consistent extension.
Source of Undecidability: The undecidability arises from the infinite generation of new conditions.
- In dynamics, composing a finite set of transformations generates an infinite set of new transformations.
- In entanglement, the "teleportation" mechanism iteratively generates new states from a finite set of entangled resources.
- Checking consistency requires verifying an infinite number of probability constraints, which maps to the halting problem.
Implications for GPT Research:
- Classification Limits: It is impossible to provide a complete classification of all possible dynamics or entanglement structures compatible with GPT axioms.
- Numerical Inefficiency: Numerical searches for consistent multipartite GPTs (as attempted in recent literature) are likely to be extremely inefficient (NP-hard or worse) because they are solving finite versions of undecidable problems.
- Need for Constraints: To make GPTs tractable, researchers must introduce additional physical or mathematical assumptions (e.g., restricting the dimension of the state space, limiting the number of compositions, or imposing specific symmetry constraints) to render the consistency problem decidable.

5. Conclusion

Serge Massar's paper establishes that the consistency of Generalised Probabilistic Theories, when extended to include discrete dynamics or entangled states in translation-invariant settings, is computationally undecidable. The proof leverages the correspondence between GPT composition/teleportation and matrix products, reducing the problem to the undecidability of probabilistic automata acceptance and matrix boundedness. This implies that the search for a "Theory of Everything" within the GPT framework cannot rely on brute-force consistency checks and requires new, restrictive axioms to ensure computability.