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

Abstract

We introduce the \emph{observational hierarchy}, a new axis of classification for formal languages, orthogonal to the Chomsky hierarchy. An observer is a function $O:{\Sigma }^{\ast }\to 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_{\perp }\prec O_{\mathrm{len}}\prec O_{\mathrm{prof}}\prec O_{\top }$ and the parity branch $O_{\perp }\prec O_{\mathrm{par}}\prec O_{\mathrm{prof}}\prec O_{\top }$, with $O_{\mathrm{len}}$ and $O_{\mathrm{par}}$ incomparable, and an infinite subsequence branch $O_{\perp }\prec O_1\prec O_2\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 \emph{observational complexity} of a language. We further define observer-parametrised complexity classes ${\mathbf{P}}_O$ and ${\mathbf{NP}}_O$, and show that computational hardness and structural blindness are two independent phenomena. In particular, ${\mathbf{P}}_{O_{\mathrm{prof}}}={\mathbf{NP}}_{O_{\mathrm{prof}}}$ holds as a structural collapse strictly inside $\mathbf{P}$.