Computable Representation Theory: The Hierarchical Representational Machine

Background: Classical computability and complexity theory analyze how costly a computation is in time or space, assuming inputs are already encoded as finite strings. The knowledge-representation tradition recognizes that representation choices constrain inference—most notably through the expressiveness–tractability tradeoff—but focuses on the complexity of querying a fixed representation, not on whether certain representational resources are necessary for a task to be expressible at all. Meanwhile, deep learning systems exhibit systematic failures on compositional and multi-object reasoning, symbolic systems face the classical symbol-grounding problem, and neuro-symbolic architectures lack a formal account of which representational resources are required for which tasks. Objectives: I aim to develop a computability-theoretic framework that classifies computational tasks by their minimal representational requirements—an axis orthogonal to time–space complexity—thereby providing formal criteria for determining when connectionist, symbolic, or neuro-symbolic architectures are representationally adequate, or provably inadequate, for a given task. Methods: I introduce the Hierarchical Representational Machine (HRM), which stratifies representational resources into four layers: Structured Input Space (L1), grounded in Type-2 Theory of Effectivity; Equivalence and Measurement (L2), formalized via computable quotient spaces and representational measurement theory; Formal Symbolic Representation (L3), providing compositional syntax with effective derivation; and Admissibility Constraints (L4), supplying decidable meta-level filters for safety, legality, and verification. For each layer, I define necessity schemas that identify structural conditions on tasks—invariance, unbounded compositionality, and hard admissibility—under which that layer is provably required. I establish separation results via diagonal and undecidability arguments, and introduce the meta-problem HRM-Classify with the minimal requirement operator Req(T). Results: The main results are: (i) three necessity schemas identifying when specific layers are unavoidable; (ii) separation theorems establishing strict gaps between layer-restricted solvability classes—{L1} ⊊ {L1,L2}, {L3} ⊊ {L1,L2,L3}, and {L1,L2,L3} ⊊ {L1,L2,L3,L4} under external-standard semantics—demonstrating that these layers correspond to genuine computability-theoretic distinctions even for constant-output tasks; and (iii) a solvability classification via Req(T) with worked examples spanning object recognition, program verification, and autonomous driving that illustrate the full layer hierarchy. Conclusions: HRM provides a formal vocabulary for diagnosing representational insufficiency in AI systems: distribution-shift brittleness is identified as missing invariance structure, systematic compositional failures as insufficient symbolic resources, and constraint violations as absent admissibility gates. The framework serves as a principled pre-architectural analysis tool that determines minimal representational commitments before algorithm selection. Because HRM addresses representational feasibility rather than computational efficiency, it complements existing frameworks such as PAC/VC theory, knowledge compilation, and category-theoretic approaches, and is applicable wherever the question "what must be representable?" precedes "how hard is inference?"