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

Source: arXiv:2606.27407 · Published 2026-06-25 · By Fabio F. G. Buono

TL;DR

This paper introduces a novel hierarchy of formal language classes defined by the notion of an "observer," a function that determines which information about the input string is accessible to a computational system. Unlike classical language classification based solely on machine power (the Chomsky hierarchy), this observational hierarchy classifies languages based on how structurally blind or detailed the observer's view of the input is. The foundational example is the "order-blind automaton" that sees only the multiset (profile) of symbols, without their order, characterizing permutation-closed languages. The paper defines a partial order on observers, forming a rich lattice structure including length-based, parity-based, profile-based, subsequence-based, and a maximal "complete" observer, each defining distinct language classes. These classes are shown to be strictly incomparable with the classical Chomsky hierarchy.

Going further, the work introduces observational complexity theory by parameterizing complexity classes (P and NP) by observers (e.g., POprof and NPOprof). Notably, the paper proves a collapse POprof = NPOprof strictly inside P, demonstrating that computational hardness and structural blindness from observer limitations are independent phenomena. The framework also admits a physical analogy viewing observers as macroscopic measurements that discard microscopic order. Overall, this research provides a rigorous formal framework exposing the fundamental role of observational constraints in computation, language recognition, and complexity.

Key findings

• Languages recognized by order-blind automata correspond exactly to permutation-closed languages (Theorem 2.5).
• The observational hierarchy forms a partial order with a diamond-shaped sub-lattice and an infinite subsequence branch, with explicit incomparabilities among canonical observers (Propositions 4.3, 4.4, 4.5).
• The observational hierarchy is strictly orthogonal and incomparable with the Chomsky hierarchy: neither includes the other (Theorem 6.2, Corollary 6.3).
• Observational complexity classes PO and NPO parameterized by observer O generalize classical classes, with POprof = NPOprof strictly contained in P, separating computational hardness from observer-induced blindness (Propositions 9.6, 9.7).
• The minimal observer complexity of classical languages varies, e.g., O(Σ*), O(∅) = O⊥; even-length strings = Olen; parity-based properties = Opar; equality of symbol counts = Oprof; 01 = O⊤ (Proposition 7.2).
• There exist languages in P that are not Oprof-saturated and languages outside RE that are Oprof-saturated, proving independence of observer saturation from classical decidability (Theorem 9.9).
• The observational preorder on observers coincides with functional post-processing: O1 ⪯ O2 if O1 factors as f ◦ O2 (Definition 3.7, Proposition 3.10).
• The subsequence observers Ok correspond exactly to Simon's hierarchy of piecewise testable languages, with strict hierarchy L(Ok) ⊊ L(Ok+1) for all k (Theorem 5.8).

Threat model

The framework assumes an adversary modeled as a computational system receiving only reduced input information filtered through an observer O, which determines observational equivalence classes of inputs indistinguishable to the system. The adversary cannot access the original full input string, only the observer's output. Under fixed observer O, the adversary’s capability is limited to computations over enc(O(x)). Structural blindness induced by O prevents distinguishing some inputs regardless of computational power, imposing fundamental limits beyond classical complexity.

Methodology — deep read

The paper develops the theory systematically, starting from formal definitions.

1. Threat Model & Assumptions: The adversary is formalized as the computational machine which receives only partial input information filtered through an observer function O : Σ* → S rather than the full string. The observer defines structural blindness limits the system’s ability to distinguish certain inputs. This is a purely theoretical, structural setup focusing on inherent informational constraints.

2. Data & Preprocessing: The "data" is formal languages over finite alphabets Σ. Observers transform input strings into elements of an observation space S (e.g., profiles Nk, subsequence sets, lengths). A canonical binary encoding enc : S → {0,1}* is fixed when S is infinite, ensuring machines work over finite strings.

3. Architecture / Algorithms: The core computational model is a Turing machine receiving enc(O(x)) as input, where O is fixed. The order-blind automaton is defined with transition function δ : Q × Nk → Q processing the entire profile at once, not symbol-by-symbol as in classical finite automata.

Observers are partially ordered by factorization: O1 ⪯ O2 iff ∃f such that O1 = f ◦ O2. This induces a partial order on language classes L(O), sets of languages saturated under O-equivalence.

The observational hierarchy is constructed from canonical observers: trivial (O⊥), length (Olen), parity (Opar), full profile (Oprof), subsequence sets of bounded length (Ok), and complete (O⊤). Their strict orderings and incomparabilities are proved using witness languages exploiting counting, parity, order, and subsequence properties.

4. Training / Computation Regime: Not applicable—this is a theoretical, mathematical framework. Proofs use classical techniques in formal languages and automata.

5. Evaluation Protocol: Language class inclusions/exclusions, strictness proofs via separating languages, and equivalence with classical hierarchies (e.g., Simon's hierarchy). Complexity classes PO and NPO parametrize machines by observers, and collapses/separations are formally proved.

6. Reproducibility: All definitions and proofs are explicit. No code or data needed; results are mathematical. Canonical encodings ensure standard models.

Concrete Example End-to-End: Consider the language L = {x | number of 1's in x is even} over {0,1}. Let observer be Opar(x) = (|x|0 mod 2, |x|1 mod 2). L depends only on parity of |x|1, so membership depends only on Opar(x). Hence L is Opar-saturated and recognized by a machine receiving Opar(x) as input. However, it is not Olen-saturated since length alone cannot distinguish parity of 1's. Thus Opar ≻ Olen in the hierarchy, separating classes via easily interpreted languages.

Technical innovations

• Definition of a novel "observational hierarchy" of language classes parameterized by the partial information accessible via an observer function, distinct from classical machine-based hierarchies.
• Characterization of permutation-closed languages as exactly those recognizable by order-blind automata processing symbol multisets rather than sequences.
• Proof that the observational hierarchy forms a rich partial order with a diamond-shaped profile sub-lattice and an infinite subsequence branch of observers.
• Introduction of observer-parametrized complexity classes PO and NPO showing a structural collapse POprof = NPOprof strictly inside P, separating computational hardness from observer-imposed blindness.

Baselines vs proposed

• Classical P and NP: PO⊤ = P, NPO⊤ = NP as baseline full information observer.
• Trivial observer: PO⊥ = NPO⊥ = {∅, Σ∗} minimal classes.
• Profile observer: POprof = NPOprof strictly contained in P (Proposition 9.7).
• Simon’s hierarchy: L(Ok) ⊊ L(Ok+1) for all k ≥ 0 (Theorem 5.8), establishing strict Wil hierarchy on subsequence observers.

Limitations

• The model abstracts away computational cost of the observer; computability and polynomiality of observers is assumed or fixed to make complexity comparisons, but uncomputable observers are included in the theory.
• The observational complexity framework is non-standard and does not resolve classical P vs NP questions; it only shows structural collapses under limited observation.
• No empirical evaluation or application to real-world systems is given; the framework is purely theoretical.
• The paper does not explore stochastic or probabilistic observers in depth, leaving open connections to information theory and Blackwell channel degradation.
• Certain open questions remain about the existence of other canonical observers strictly between known levels (e.g., between O⊥ and Oprof).
• The physical interpretation relating observers to macroscopic measurements is discussed only as analogy without rigorous linkage to physical axioms or dynamical systems.

Open questions / follow-ons

• Are there additional canonical observers strictly between the trivial observer O⊥ and full profile observer Oprof, incomparable with existing canonical observers like Olen or Opar?
• How to extend the observational hierarchy and complexity theory framework to stochastic or probabilistic observers mapping strings to distributions, connecting to Blackwell channel degradation?
• Can the physical analogy be rigorously developed with added structure (probability measures, dynamics, entropy) to derive thermodynamic irreversibility properties from the observational framework?
• What are the practical implications of observers with limited information in real computational systems, particularly for approximate computation or privacy-preserving models?

Why it matters for bot defense

Bot-defense and CAPTCHA systems fundamentally rely on distinguishing human-generated input from automated or adversarial input based on limited or partial observations of interaction data. This paper’s framework formalizes how restricting or limiting the "observer"—the information accessible to the system—creates fundamental structural limitations in what input patterns or languages can be recognized, regardless of computational power. In bot-defense, features or signals extracted from client behavior often discard ordering or detailed information, e.g., aggregated counts or partial event sequences, analogous to weaker observers such as Oprof or Ok.

Understanding the observational hierarchy elucidates which classes of bot behavior patterns can be recognized or differentiated given the structural blindness imposed by limited observations. It also explains why increasing computational sophistication alone (e.g., more complex machine learning models) cannot compensate for loss of key structural information in inputs. Furthermore, the separation of computational hardness from observational blindness suggests that hardness assumptions in CAPTCHAs must consider whether the adversary is constrained by an observer and its induced equivalence classes. This potentially guides design toward observing richer information modalities or dynamic features beyond permutation-invariant or parity features, thus increasing system distinguishability power. Overall, the theory advises CAPTCHA practitioners on the fundamental limits of language recognition under observational constraints, helping prioritize where richer observations are most critical to robust bot detection.

Cite

@article{arxiv2606_27407,
  title={ Observers, Symmetries, and the Hierarchy of Language Classes: A Theory of Computation Parameterized by the Observer },
  author={ Fabio F. G. Buono },
  journal={arXiv preprint arXiv:2606.27407},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.27407}
}

Read the full paper

• arXiv:2606.27407 (abstract)
• arXiv:2606.27407 (PDF)