💻 computer science

Observers, Symmetries, and the Hierarchy of Language Classes: A Theory of Computation Parameterized by the Observer

This paper introduces the "observational hierarchy," a new classification axis for formal languages based on the information-access constraints of an observer rather than machine computational power, proving that this hierarchy is orthogonal to the Chomsky hierarchy, exhibits a specific diamond-shaped lattice structure, and can induce structural collapses in complexity classes such as $\mathbf{P}_{O_{\mathrm{prof}}} = \mathbf{NP}_{O_{\mathrm{prof}}}$ .

Original authors: Fabio F. G. Buono

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fabio F. G. Buono

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a puzzle, but instead of being handed the puzzle pieces in the correct order, you are handed a bag of mixed-up pieces. You can count how many red pieces you have, or how many blue ones, but you cannot see the picture they form when put together in a line.

This is the core idea of the paper "Observers, Symmetries, and the Hierarchy of Language Classes."

The author, Fabio Francesco Gabriele Buono, proposes a new way to look at computer science problems. Usually, we ask: "How powerful does the computer need to be to solve this?" (Is it a simple calculator, or a super-computer?). This paper asks a different question: "What information is the computer allowed to see?"

Here is a breakdown of the paper's main ideas using simple analogies.

1. The "Observer" is the Gatekeeper

In this theory, an Observer is like a filter or a pair of glasses. Before a computer (the machine) tries to solve a problem, the Observer looks at the input (a string of letters or numbers) and decides what to show the computer.

The "Complete" Observer ( $O_{\top}$ ): This is like a human looking at a sentence. They see every letter, in every order. "The cat sat" is different from "sat the cat."
The "Order-Blind" Observer ( $O_{prof}$ ): This is like a chef who only cares about the count of ingredients, not the order they were added. If you give them "2 eggs and 1 cup of flour," they can't tell if you made a cake or scrambled eggs. They only see the numbers: (2, 1).
The "Trivial" Observer ( $O_{\bot}$ ): This is a broken camera that shows a blank white screen for every input. The computer sees nothing but "white."

2. The Main Discovery: The Machine Doesn't Matter as Much as the Glasses

The paper proves a surprising fact: No matter how powerful the computer is, if the Observer is "blind" to certain details, the computer cannot solve problems that require those details.

The Analogy: Imagine a super-genius mathematician (a Turing Machine) trying to solve a riddle. But, the riddle is written on a piece of paper that has been shredded into a pile of confetti, and the mathematician is only allowed to count the number of red and blue confetti pieces.
The Result: Even the smartest mathematician cannot figure out the original sentence from the confetti counts. The "blindness" of the Observer is a harder limit than the "intelligence" of the machine.

3. The "Observational Hierarchy" (The Ladder of Vision)

The author builds a ladder of different types of observers, ranging from the most blind to the most clear.

The Bottom (Blind): The Trivial Observer. The computer can only say "Yes" to everything or "No" to everything.
The Middle (Partial Vision):
- The "Length" Observer: Only sees how long the string is (e.g., "It has 5 letters").
- The "Parity" Observer: Only sees if the counts are odd or even (e.g., "There is an odd number of A's").
- The "Profile" Observer: Sees the exact count of every letter, but not the order. (e.g., "3 A's, 2 B's").
- The "Subsequence" Observer: Sees small chunks of the order (e.g., "Does the string contain 'AB' somewhere?").
The Top (Clear Vision): The Complete Observer. Sees the whole string exactly as it is.

The paper shows that these levels form a specific shape (a "diamond" and an "infinite ladder"). Some levels are incomparable; for example, knowing the total length of a string doesn't help you know the parity (odd/even) of specific letters, and vice versa.

4. Connection to Physics: The "Macroscopic" View

The paper draws a fun parallel to physics.

Microscopic View: In physics, a gas is made of trillions of individual molecules moving in specific orders.
Macroscopic View: A thermometer (the Observer) only sees the average temperature and pressure. It cannot see which molecule is where.
The Insight: Just as a thermometer cannot tell you the exact path of a single molecule, a computer with a "Profile Observer" cannot tell you the exact order of letters. The "disorder" (entropy) isn't just a physical property; it's a result of what the observer is allowed to see.

5. Complexity and the "P vs NP" Question

The paper tackles a famous computer science mystery: Is it easier to check a solution than to find one? (The P vs NP problem).

The Twist: The author defines new complexity classes based on the Observer.
The Finding: If you use the "Profile Observer" (who only sees counts), the difference between "finding" and "checking" disappears.
- Why? Because the Observer has thrown away so much information (the order) that there is no complex puzzle left to solve. The computer just counts.
- The Takeaway: This doesn't solve the real-world P vs NP problem (where we have full vision). Instead, it proves that "Hardness" (how hard a problem is to solve) and "Blindness" (what information is missing) are two totally different things. You can have a problem that is easy to solve if you have full vision, but impossible if you are blind, even if the computer is super-smart.

Summary

This paper argues that we need to stop looking only at how "smart" a computer is. We must also look at what the computer is allowed to see.

If your "glasses" (Observer) are too blurry, no amount of computing power will let you see the picture.
The author has mapped out a new "ladder" of vision, showing exactly how much information is lost at each step and how that loss changes what problems can be solved.
Ultimately, the paper suggests that structural blindness (missing information) is just as important as computational hardness (lack of power).

Technical Summary: Observers, Symmetries, and the Hierarchy of Language Classes

Problem Statement

Classical computational complexity and formal language theory traditionally classify problems based on the computational power of the machine (e.g., finite automata, pushdown automata, Turing machines) and assume the input is a fully accessible, ordered sequence of symbols. This paper inverts that perspective, positing that the limitations of a computational system may arise not from the machine's processing power, but from the structure of the observer.

The central problem addressed is: Which languages can a computational system recognize when it does not have access to the complete input string, but only to a specific projection or transformation of it? The paper investigates how the "blindness" or "structural limitations" of an observer function $O: \Sigma^* \to S$ (which maps an input string to an observation space $S$ ) dictates the class of recognizable languages, independent of the machine's computational model.

Methodology

The paper introduces a formal framework centered on the concept of an observer:

Observer Definition: An observer is a function $O$ that transforms an input string $x$ into an observation $O(x)$ . A computational system $(M, O)$ receives $O(x)$ as its input instead of $x$ .
O-Saturation: A language $L$ is O-saturated if membership in $L$ depends solely on the observation $O(x)$ . Formally, $x \sim_O y \implies (x \in L \iff y \in L)$ . If a language is not O-saturated, no machine equipped with observer $O$ can decide it, regardless of its computational power.
Observational Order: A preorder $\preceq$ is defined on observers where $O_1 \preceq O_2$ if $O_1$ can be derived from $O_2$ (i.e., $O_1 = f \circ O_2$ ). This induces a hierarchy of language classes $\mathcal{L}(O)$ , where $O_1 \preceq O_2 \implies \mathcal{L}(O_1) \subseteq \mathcal{L}(O_2)$ .
Canonical Observers: The paper defines specific observers to construct a hierarchy:
- $O_\perp$ : Trivial observer (maps all strings to a constant).
- $O_{len}$ : Length observer (maps to $|x|$ ).
- $O_{par}$ : Parity observer (maps to counts modulo 2).
- $O_{prof}$ : Profile observer (maps to the vector of symbol counts, ignoring order).
- $O_k$ : Subsequence observer (maps to the set of subsequences of length $\le k$ ).
- $O_\top$ : Complete observer (identity, $O(x) = x$ ).

Key Contributions and Results

1. The Order-Blind Automaton and Permutation-Closed Languages

The paper characterizes the order-blind automaton, a machine that processes the profile of a string (the multiset of symbol counts) rather than the sequence.

Theorem 2.5: A language is recognizable by an order-blind automaton if and only if it is permutation-closed (invariant under symbol reordering).
This result demonstrates that the finiteness of states is not the primary constraint; rather, the observer determines the class. Even a Turing machine with a trivial observer can only recognize $\emptyset$ and $\Sigma^*$ .

2. The Observational Hierarchy

The paper constructs a partial order of language classes based on the observational power of canonical observers. The hierarchy exhibits a specific structure:

Diamond-Shaped Profile Sub-lattice:
- $O_\perp \prec O_{len} \prec O_{prof} \prec O_\top$ (Length branch)
- $O_\perp \prec O_{par} \prec O_{prof} \prec O_\top$ (Parity branch)
- $O_{len}$ and $O_{par}$ are incomparable.
Infinite Subsequence Branch:
- $O_\perp \prec O_1 \prec O_2 \prec \dots \prec O_\top$ .
- This branch corresponds to Simon's hierarchy of piecewise testable languages.
Orthogonality: The profile sub-lattice (counting information) and the subsequence branch (partial ordering information) are incomparable. $O_{prof}$ is incomparable with any $O_k$ .

3. Orthogonality with the Chomsky Hierarchy

The paper proves that the observational hierarchy is strictly orthogonal (incomparable) to the Chomsky hierarchy (Regular, Context-Free, etc.).

There exist languages that are Regular but not O-saturated (e.g., $0^*1^*$ is not $O_{prof}$ -saturated).
There exist languages that are O-saturated but not Regular (e.g., $\{x \mid |x|_0 = |x|_1\}$ is $O_{prof}$ -saturated but not regular).
This establishes that "structural blindness" and "computational complexity" are independent axes of classification.

4. Connection to Simon's Hierarchy

The paper reformulates Simon's theorem regarding piecewise testable languages.

The family of observers $\{O_k\}$ corresponds exactly to the equivalence relations in Simon's hierarchy.
A regular language is piecewise testable if and only if it is decidable by some finite $O_k$ .
The profile class $\mathcal{L}(O_{prof})$ and the union of piecewise testable languages $\bigcup_k \mathcal{L}(O_k)$ are incomparable.

5. Observer-Parametrised Complexity Classes (PO and NPO)

The framework is extended to complexity theory by defining classes $PO$ and $NPO$ where complexity is measured relative to the size of the observation $|enc(O(x))|$ rather than the input size $|x|$ .

Structural Collapse: The paper proves $PO_{prof} = NPO_{prof}$ $P O_{p r o f} = N P O_{p r o f}$ .
- Significance: This is not a resolution of $P$ vs $NP$. Instead, it is a structural collapse occurring because the observer $O_{prof}$ discards all combinatorial structure (order). Without order, nondeterminism offers no advantage over determinism.
- Strict Containment: $PO_{prof} \subsetneq P$ . The class $PO_{prof}$ contains only $O_{prof}$ -saturated languages computable in polynomial time relative to the profile size. Since $0^*1^*$ is in $P$ but not $O_{prof}$ -saturated, the containment is strict.
Independence of Hardness and Blindness: The paper demonstrates that computational hardness and observational decidability are independent. There are languages in $P$ that are not $O_{prof}$ -saturated, and languages outside the recursively enumerable (RE) class that are $O_{prof}$ -saturated (e.g., languages defined by the halting problem on symbol counts).

Significance and Claims

The paper claims to introduce a new, independent axis for classifying formal languages and computational problems. Its primary significance lies in:

Decoupling Machine Power from Observer Structure: It establishes that the "weakness" of an observer can render a problem unsolvable even for a Turing machine, while a weaker machine (like a DFA) can solve it with a stronger observer.
Distinction Between Hardness and Blindness: It formally separates computational hardness (difficulty due to algorithmic complexity) from structural blindness (inability to distinguish inputs due to information loss). The collapse $PO_{prof} = NPO_{prof}$ is presented as evidence that these are distinct phenomena; the collapse occurs because the observer removes the very structure that makes problems hard, not because nondeterminism is inherently weak.
Physical Interpretation: The framework offers a formal analogy to statistical mechanics, where a macroscopic observer (seeing only aggregate quantities like temperature or density) cannot distinguish between microscopic histories that are permutations of each other. This provides a mathematical basis for the concept of "thermodynamic irreversibility" as an observational property.

The paper concludes that the observational hierarchy provides a rigorous framework for analyzing systems where information is inherently limited or aggregated, suggesting that future research should explore probabilistic observers, categorical compositions of observers, and the quantitative relationship between observational complexity and information preservation.