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

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.