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

Fabio Francesco Gabriele Buono · 2026

Read Observers, Symmetries, and the Hierarchy of Language Classes: A Theory of Computation Parameterized by the Observer by Fabio Francesco Gabriele Buono (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27407.txt.

Introduction

Buono argues that what a computer can perceive about its input deserves its own hierarchy, beside the classic Chomsky hierarchy of grammars. An observer is a function that fixes which information about the input string a machine may access. The order-blind automaton, which sees only the multiset of symbols, is the guiding example. In 2026, languages recognisable under that observer are proven to be exactly the permutation-closed languages, those unchanged by shuffling their strings.

A partial order on observers induces the hierarchy, driven by perception rather than machine power. Its profile contains a diamond: a length branch and a parity branch, incomparable with each other, plus an infinite subsequence branch, all converging to the complete observer. The hierarchy is strictly incomparable with Chomsky's. Observer-parametrised complexity classes follow, with one collapse inside ordinary polynomial time. Hardness and blindness are independent phenomena.

Catalog record

CREATORFabio Francesco Gabriele Buono
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27407

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Observers, Symmetries, and the Hierarchy of Language Classes: A Theory of Computation Parameterized by the Observer Fabio Francesco Gabriele Buono Abstract We introduce the observational hierarchy , a new axis of classification for formal languages, orthogonal to the Chomsky hierarchy. An observer is a function O : Σ ∗ → S O:\Sigma^{*}\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 ⊥ ≺ O len ≺ O prof ≺ O ⊤ O_{\bot}\prec O_{\mathrm{len}}\prec O_{\mathrm{prof}}\prec O_{\top} and the parity branch O ⊥ ≺ O par ≺ O prof ≺ O ⊤ O_{\bot}\prec O_{\mathrm{par}}\prec O_{\mathrm{prof}}\prec O_{\top} , with O len O_{\mathrm{len}} and O par O_{\mathrm{par}} incomparable, and an infinite subsequence branch O ⊥ ≺ O 1 ≺ O 2 ≺ ⋯ ≺ O ⊤ O_{\bot}\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 observational complexity of a language. We further define observer-parametrised complexity classes 𝐏 O \mathbf{P}_{O} and 𝐍𝐏 O \mathbf{NP}_{O} , and show that computational hardness and structural blindness are two independent phenomena. In particular, 𝐏 O prof = 𝐍𝐏 O prof \mathbf{P}_{O_{\mathrm{prof}}}=\mathbf{NP}_{O_{\mathrm{prof}}} holds as a structural collapse strictly inside 𝐏 \mathbf{P} . 1 Introduction The classical theory of computational complexity classifies problems according to the power of the machine required to solve them. Finite automata, pushdown machines, Turing machines, and their deterministic and nondeterministic variants [ 2 , 9 ] . In this framework, the input is always a string, an ordered sequence of symbols, and full access to that sequence is taken for granted. This paper inverts that perspective. We ask: which languages can a computational system recognise when it does not have access to the complete input, but only to a projection of it? The power of the machine becomes secondary; what matters is the structure of the observer , that is, of the function that transforms the input into available information. The motivating case is that of an observer that cannot distinguish the temporal order of symbols, but perceives only their counts. Formally, such an observer maps every string x\in\Sigma^{*} to its profile \mathrm{prof}(x)\in\mathbb{N}^{k} , where k=|\Sigma| and the i -th component counts the occurrences of symbol a_{i} . An automaton equipped in this way does not distinguish 01 from 10 , nor aab from aba or baa . Main contributions. (i) Definition of the order-blind automaton and characterisation of the languages it recognises (Section 2 ). (ii) Definition of the preorder of observers, the induced partial order of observational power, the notion of O -saturation, and the monotonicity of induced language classes (Section 3 ). (iii) Construction of the observational hierarchy: proof that it has the structure of a partial order with a diamond-shaped profile sub-lattice (with O_{\mathrm{len}} and O_{\mathrm{par}} incomparable, both below O_{\mathrm{prof}} ) and an infinite subsequence branch, with explicit separations (Section 4 ). (iv) Formal connection with Simon’s hierarchy and piecewise testable languages; observational reformulation of Simon’s theorem (Section 5 ). (v) Proof that the observational hierarchy is orthogonal to the Chomsky hierarchy (Section 6 ). (vi) Definition and first properties of observational complexity (Section 7 ). (vii) Physical interpretation of the framework (Section 8 ). (viii) Definition of observer-parametrised complexity classes \mathbf{P}_{O} and \mathbf{NP}_{O} ; separation of computational hardness from structural blindness; proof that \mathbf{P}_{O_{\mathrm{prof}}}\subsetneq\mathbf{P} (Section 9 ). 2 The base model: the order-blind automaton Let \Sigma=\{a_{1},\dots,a_{k}\} be a finite alphabet. Definition 2.1 (Profile) . The profile of a string x\in\Sigma^{*} is the function \mathrm{prof}(x)=(c_{1},\dots,c_{k})\in\mathbb{N}^{k} where k=|\Sigma| and c_{i}=|x|_{a_{i}} is the number of occurrences of a_{i} in x . Definition 2.2 (Permutation-closed language) . A language L\subseteq\Sigma^{*} is permutation-closed if x\in L\;\Rightarrow\;\forall\,y\in\Sigma^{*}\ \text{with}\ \mathrm{prof}(y)=\mathrm{prof}(x),\quad y\in L. Equivalently, L is permutation-closed if and only if there exists a function f:\mathbb{N}^{k}\to\{0,1\} such that L=\{x\in\Sigma^{*}\mid f(\mathrm{prof}(x))=1\} . Definition 2.3 (Order-blind automaton) . An order-blind automaton is a quintuple A=(Q,\,\Sigma,\,\delta,\,q_{0},\,F) where Q is a finite set of states, q_{0}\in Q is the initial state, F\subseteq Q is the set of accepting states, and \delta:Q\times\mathbb{N}^{k}\to Q is the transition function. The extended transition function is \hat{\delta}(q_{0},x)\coloneqq\delta(q_{0},\,\mathrm{prof}(x)), (1) and the recognised language is L(A)=\{x\in\Sigma^{*}\mid\hat{\delta}(q_{0},x)\in F\}. (2) Remark 2.4 . Unlike a classical DFA, whose transition function has type Q\times\Sigma\to Q and processes the input symbol by symbol, the order-blind automaton has transition function \delta:Q\times\mathbb{N}^{k}\to Q , which reads the entire profile in a single step (equation ( 1 )). This is intentional: the model is designed to recognise any permutation-closed language, including non-regular ones such as \{x\mid|x|_{0}=|x|_{1}\} . Theorem 2.5 (Characterisation) . A language L\subseteq\Sigma^{*} is recognisable by an order-blind automaton if and only if it is permutation-closed. Proof. (\Rightarrow) Let L=L(A) for some order-blind automaton A . If x\in L and \mathrm{prof}(y)=\mathrm{prof}(x) , then \hat{\delta}(q_{0},y)\overset{\eqref{eq:delta-hat}}{=}\delta(q_{0},\mathrm{prof}(y))=\delta(q_{0},\mathrm{prof}(x))\overset{\eqref{eq:delta-hat}}{=}\hat{\delta}(q_{0},x)\in F, so y\in L . (\Leftarrow) Let L be permutation-closed, so there exists f:\mathbb{N}^{k}\to\{0,1\} with L=\{x\in\Sigma^{*}\mid f(\mathrm{prof}(x))=1\} . Construct A with Q=\{q_{0},q_{\mathrm{acc}},q_{\mathrm{rej}}\} , F=\{q_{\mathrm{acc}}\} , and \delta(q_{0},v)=\begin{cases}q_{\mathrm{acc}}&\text{if }f(v)=1,\\ q_{\mathrm{rej}}&\text{otherwise.}\end{cases} Then \hat{\delta}(q_{0},x)=\delta(q_{0},\mathrm{prof}(x)) by ( 1 ), so A accepts x if and only if f(\mathrm{prof}(x))=1 , giving L(A)=L . ∎ Example 2.6 . Over \{0,1\} : • L_{1}=\{x\mid|x|_{1}\equiv 0\pmod{2}\} is permutation-closed: recognisable. • L_{2}=\{x\mid|x|_{0}>|x|_{1}\} is permutation-closed: recognisable. • L_{3}=\{x\mid x\text{ starts with }1\} is not permutation-closed: \mathrm{prof}(10)=\mathrm{prof}(01)=(1,1) but 10\in L_{3} and 01\notin L_{3} . Not recognisable. • L_{4}=0^{*}1^{*} is not permutation-closed: \mathrm{prof}(01)=\mathrm{prof}(10)=(1,1) but 01\in L_{4} and 10\notin L_{4} . Not recognisable. Remark 2.7 . Theorem 2.5 shows that the finiteness of Q is not the binding constraint: it is the observer that determines the class. The power of the machine cannot compensate for the weakness of the observer. With an observer that maps everything to the same value, no machine, not even a Turing machine, could recognise anything beyond \emptyset and \Sigma^{*} . The transition function \delta:Q\times\mathbb{N}^{k}\to Q is not required to be computable. The purpose of Theorem 2.5 is to characterise all permutation-closed languages, which includes non-recursive and non-r.e. languages (Theorem 9.9 (ii)). Restricting \delta to computable functions would yield a strictly smaller class. The model is therefore a mathematical characterisation rather than a computational one. Corollary 2.8 . For any machine M and any language L\notin\{\emptyset,\Sigma^{*}\} , a system equipped with the trivial observer O_{\bot}:x\mapsto\star does not recognise L , regardless of the computational power of M . Proof. The trivial observer identifies all strings, the only O_{\bot} -decidable languages are \emptyset and \Sigma^{*} . Any L\notin\{\emptyset,\Sigma^{*}\} contains some x and omits some y , yet O_{\bot}(x)=O_{\bot}(y)=\star , so no system receiving only O_{\bot}(x) can decide L correctly on both inputs. ∎ 3 Theory of observers Definition 3.1 (Observer) . Let \Sigma be a finite alphabet and S a set (the

Read the complete text