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

arXiv: https://arxiv.org/abs/2606.27407 · HTML: https://mlsanity.com/paper/2606.27407/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2026.

## Built on by (most cited first, 1 of 1)

- [A Non-Formulable Theorem: A Fundamental Limit of Finite Syntactic Systems and Its Consequences for Security and AI](https://mlsanity.com/paper/2609.04086/) (2026)

## Abstract (arXiv)

We introduce the observational hierarchy, a new axis of classification for formal languages, orthogonal to the Chomsky hierarchy. An observer is a function O : Sigma^* → S that determines which information about the input is accessible to a computational system. The order-blind automaton, which perceives the input as a multiset of symbols rather than a sequence, constitutes the paradigmatic case. We prove that the class of languages recognisable by any machine equipped with such an observer coincides exactly with the permutation-closed languages. We then define a partial order on observers that induces a hierarchy of language classes parametrised not by the computational power of the machine, but by the structure of the observer. We prove that this hierarchy has the structure of a partial order with a diamond-shaped profile sub-lattice, comprising the length branch O_bot prec Olen prec Oprof prec O_top and the parity branch O_bot prec Opar prec Oprof prec O_top, with Olen and Opar incomparable, and an infinite subsequence branch O_bot prec O1 prec O2 prec cdots prec O_top, both converging to the complete observer. We prove that the observational hierarchy is strictly incomparable with the Chomsky hierarchy, and introduce the notion of observational complexity of a language. We further define observer-parametrised complexity classes PO and NPO, and show that computational hardness and structural blindness are two independent phenomena. In particular, P_Oprof = NP_Oprof holds as a structural collapse strictly inside P.