A Taxonomy of Function Representations and Computational\nExpressivity<\/title> \n<meta charset='utf-8' \/> \n<meta content='TeX4ht (https:\/\/tug.org\/tex4ht\/)' name='generator' \/> \n<meta content='width=device-width,initial-scale=1' name='viewport' \/> \n<link href='springtail-blog.css' rel='stylesheet' type='text\/css' \/> \n<meta content='function-classes.tex' name='src' \/> \n<script>window.MathJax = { tex: { tags: \"ams\", }, }; <\/script> \n<script async='async' id='MathJax-script' src='https:\/\/cdn.jsdelivr.net\/npm\/mathjax@3\/es5\/tex-chtml-full.js' type='text\/javascript'><\/script> \n<style>\ntable{ \n border-left:solid black 1px; border-right:solid black 1px; \n border-top:solid black 1px; border-bottom:solid black 1px; \n border-collapse: collapse;\n}\n #TBL-2-1-{border-bottom: 1px solid black;}\n #TBL-2-1{border-right:1px solid black;}\n #TBL-2-2{border-right:1px solid black;}\n #TBL-2-3{border-right:1px solid black;}\n #TBL-2-4{border-right:1px solid black;}\n #TBL-2-5{border-right:1px solid black;}\n #TBL-2-6{border-right:1px solid black;}\n #TBL-2-7{border-right:1px solid black;}\n<\/style>\n<\/head><body><main>\n<a href='https:\/\/springtail.ai\/wp\/wp-content\/uploads\/2026\/09\/function-classes.pdf'>pdf version of this post<\/a>\n <h3 class='sectionHead' id='introduction'>1 <\/span> <a id='x1-10001'><\/a>Introduction<\/h3>\nThe goal of this document is to better understand what types of functions\nexist, with the intuition that <\/span>functions are knowledge<\/span>, and so a taxonomy of\nfunctions is a taxonomy of the ways to represent knowledge. Descriptive\ncategorization is helpful for:<\/span> <\/p>\n <ul class='itemize1'>\n <li class='itemize'>Finding gaps and continuations: what\u2019s missing, and why? What\n classes of functions can <\/span>not <\/span>be easily represented by other classes?<\/span>\n <\/li>\n <li class='itemize'>Improving the capacity and generalization properties of models –\n to better match the \u2018true\u2019 function that generated the data.<\/span>1<\/span><\/sup>1<\/span><\/sup> See<\/span>\n <a href='https:\/\/springtail.ai\/wp\/2026\/02\/16\/to-build-a-ml-strange-loop\/'>previous post\u2019s<\/span><\/a> discussion of equivalence classes<\/span><\/span><a id='x1-1001r2'><\/a>\n <\/li>\n <li class='itemize'>Enhancing the learning & optimization algorithms that build\n them, e.g. for learning the right function with less data or fewer\n interactions. Function inverses, which map data back to generating\n funcions, are <\/span>themselves <\/span>functions \/ algorithms that need to be\n derived or learned<\/span>2<\/span><\/sup>2<\/span><\/sup> DL, of course, derives them with the chain rule,\n but this is only one means of propagating information from data to a\n compressed model. Inverses might well range from LUTs to heuristics\n to algorithms – they are in general not in the same class as the forward\n function!<\/span><\/span><a id='x1-1002r3'><\/a>.<\/span><\/li><\/ul>\n Most of the functions levels below are, at the limit, interchangeable – you\ncan approximate any input-output mapping (or algorithm) with a giant\nlook-up table. Functional equivalence means that extensional properties are\nthe same, while intensional properties may differ. LUTs can be tremendously\n<\/span>inefficient <\/span>in terms of learning and storage; they have effectively zero\ncompression, hence <\/span>\\(\\sim 0\\) <\/span>generalization. As you get higher and higher levels of\ncompression you <\/span>generally <\/span>need more sophisticated algorithms for inducing\nthe function from data, as not only may one element of the function affect\nmany or all outputs, but frequently relationships between functional elements\n(pairwise and higher-order) affect the outputs. Indeed, a key element of\ncompression is to form representations from pairwise and higher-order\ninteractions; this is critical for compositionality. Another key element is\nre-use, which enables the few-to-many expansions during function\napplication.<\/span>\n<\/p> At the limit of this, I argue <\/span><a href='https:\/\/springtail.ai\/wp\/2026\/02\/16\/to-build-a-ml-strange-loop\/'>elsewhere<\/span><\/a> that the induction algorithm must\nbe a strange loop. This is a loop (as in iteration or recurrence) in which state\nvariables index over abstraction itself, e.g. whether functions are treated as\n \n \nthe result of computation (data) or the cause of computation (code). There\nare a wide variety of strange loops, from the trivial oscillators of like \u201cthis\nstatement is false\u201d to the knowledge and abstraction generating strange loops\nwe embody. Open-ended induction \/ compression requires repeated,\nrecurrent abstraction-generation to circumvent exponential hypothesis\nspace.<\/span>\n<\/p> \\(\\sim \\)<\/span>\n<\/p> The remainder of this document was created with the help Gemini and\nClaude; I tried to edit down into reasonable coherence. About half the\nexamples (on folding and ordering computation, XOR problem, others) are\nmy own, the rest are filled in by AI. I think more work can be done wrt\ndescribing the learning and generalization properties of each class – properties\nwhich are uncomputable and hence only heuristic \/ approximate – but that\u2019s\na matter of continuing effort.<\/span>\n<\/p>\n <div class='maketitle'>\n\n <div class='author'><\/div> \n<div class='date'><\/div>\n <\/div>\n <section class='abstract' role='doc-abstract'> \n<h3 class='abstracttitle'>\nAbstract<\/span>\n<\/h3>\n\n <\/p> A function is a mathematical mapping <\/span>\\(f: X \\to Y\\)<\/span>.<\/span>3<\/span><\/sup>3<\/span><\/sup> Elements of\n X and Y could be scalars or vectors; the non-function case\n that they are sets is not covered here, though it\u2019s important\n for random processes…<\/span><\/span><a id='x1-1003r4'><\/a> The properties of this mapping\n can be categorized by the mechanism of representation,\n the geometry of the resulting hypothesis class, and the\n computational architecture used to calculate it. The following\n taxonomy attempts to segment functions by their structural\n or compressional efficiency, progressing from unstructured\n memorization to the theoretical limits of computation. In\n \n \n the real world, functions are in one or several classes, or\n are compositions of different classes, leading to composite\n attributes, costs, and complexity.<\/span>\n<\/p>\n<\/section>\n \n <h3 class='likesectionHead' id='level-explicit-tabular-representations-pure-memorization'><a id='x1-2000'><\/a>Level 0: Explicit Tabular Representations (Pure Memorization)<\/h3>\nThe domain \\(X\\)<\/span> and codomain \\(Y\\)<\/span> are treated as unstructured, discrete &\nunordered sets.4<\/span><\/sup>4<\/span><\/sup> Technically: \u201cEquipped solely with the discrete\ntopology.\u201d<\/span><\/span><a id='x1-2001r5'><\/a>\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The function is represented explicitly as an exhaustive\n set of tuples \\((x, y)\\)<\/span>.\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>The concept of \u201cnearness\u201d does not\n exist. Because the discrete topology isolates every point, \\(f(x)\\)<\/span> has zero\n mutual information to \\(f(x’)\\)<\/span> , \\(\\forall x, x’ : x’ \\neq x\\)<\/span>.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Information Theory): <\/span>The\n information required to specify the mapping is the Shannon\n entropy of the full Cartesian product. For a discrete domain of size\n \\(|X| = 2^{b_{in}}\\)<\/span> and codomain size \\(|Y| = 2^{b_{out}}\\)<\/span>, specification requires \\(\\mathcal {O}(2^{b_{in}} \\times b_{out})\\)<\/span> bits.\n <\/li>\n <li class='itemize'>Capacity: <\/span>The Vapnik-Chervonenkis (VC) dimension is strictly \\(|X|\\)<\/span>\n (or infinite for infinite domains). Every possible mapping can be\n represented, provided sufficient memory.\n <\/li>\n <li class='itemize'>Generalization: <\/span>None. Out-of-distribution (OOD) generalization\n is impossible without any inductive bias or structural priors.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Triviality): <\/span>Learning is an \\(\\mathcal {O}(1)\\)<\/span>\n memory allocation and storage operation per sample. There is no\n optimization landscape to navigate, no loss surface, and no credit\n \n \n assignment. The computational cost of training and querying can\n be constant in the case of a hashmap, or can scale gracefully with\n other datastructures.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-metric-topological-interpolators-nonparametric-smoothness'><a id='x1-3000'><\/a>Level 1: Metric & Topological Interpolators (Non-Parametric\nSmoothness)<\/h3>\nThe domain \\(X\\)<\/span> is endowed with a metric \\(d_X(x, x’)\\)<\/span> or a specified topological\nstructure, allowing the representation to leverage the native geometry of\nthe input space.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The \u201cordered look-up table.\u201d Outputs for novel\n inputs are interpolated based on proximity to known inputs,\n bounded by a smoothness constraint (e.g., Lipschitz or H\u00f6lder\n continuity). Examples include \\(k\\)<\/span>-Nearest Neighbors, Splines, and\n Kernel Methods.\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>The function constructs a\n non-parametric cover of the space. It relies entirely on the ambient\n metric \\(d_X\\)<\/span> to define local neighborhoods, meaning it cannot discover\n new geometries; it merely smooths over the existing one.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Approximation Theory): <\/span>The\n complexity of this class is measured by Metric Entropy (or\n Kolmogorov \\(\\epsilon \\)<\/span>-entropy). To approximate a function with smoothness\n \\(s\\)<\/span> in a \\(d\\)<\/span>-dimensional space to an error \\(\\epsilon \\)<\/span>, the required number of\n interpolation points scales as \\(\\mathcal {O}(\\epsilon ^{-d\/s})\\)<\/span>.\n <\/li>\n <li class='itemize'>Capacity: <\/span>The capacity scales strictly with the size of the observed\n data, theoretically capable of approximating any continuous\n function given infinite samples.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Can be robust; inductive bias is obviously toward\n in-distribution interpolation. OOD generalization (extrapolation)\n fails gracefully; the degradation is deterministic, governed directly\n by the chosen metric. In-domain generalization is inherently\n bottlenecked by the Curse of Dimensionality <\/span>(evident in the \\(d\/s\\)<\/span>\n \n \n exponent), as the volume of the space grows exponentially faster\n than it can be populated by data points.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Convex Bottlenecks): <\/span>Many\n methods (kNN, splines) do not have optimization and hence\n do not have a loss landscape. For kernel methods (e.g., Kernel\n Ridge Regression, SVMs), the optimization landscape is strictly\n convex, guaranteeing convergence to a global optimum without\n the risk of local minima. However, learning is heavily bottlenecked\n by computational complexity rather than optimization difficulty.\n Constructing and inverting the kernel Gram matrix requires \\(\\mathcal {O}(N^3)\\)<\/span> time\n and \\(\\mathcal {O}(N^2)\\)<\/span> memory. This can be remedied with random features, as\n discussed in the next section.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-shallow-parameterized-maps-fixedbasis-global-approximation'><a id='x1-4000'><\/a>Level 2: Shallow Parameterized Maps (Fixed-Basis Global\nApproximation)<\/h3>\nThe function takes the form \\(f(x) = \\phi (x; \\theta )\\)<\/span>, decoupling the representation from the ambient\nmetric \\(d_X\\)<\/span> by embedding the input into a learned or fixed parameterized\nspace.<a href='function-classes2.html#fn1x0'>1<\/sup><\/a><\/span><a id='x1-4001f1'><\/a> \n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The mapping relies on a finite set of parameters\n decoupled from the size of the training data. This encompasses\n single<\/span>-hidden-layer neural networks and fixed global basis\n expansions.\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>The map \\(x \\mapsto \\phi (x; \\theta )\\)<\/span> pushes the data forward\n into a fixed-dimensional latent manifold, substituting the extrinsic\n metric of the input space with an intrinsic, learned metric. Rather\n than covering a space with small local metric balls (Level 1), it\n defines global level sets. For example, a hidden layer \\(\\sigma (W x + b)\\)<\/span> partitions\n the space globally; rather than defining a local region of interest,\n a single hyperplane slices the entire domain space in half.\n \n \n <\/li>\n <li class='itemize'>Mathematical Grounding (Statistical Learning Theory):<\/span>\n Complexity is bounded by the size and numerical resolution of\n the parameter space \\(\\mathcal {O}(|\\theta |)\\)<\/span>, formally measured by VC Dimension or\n Rademacher Complexity. This parameter compression enables a\n degree of geometric generalization.\n <\/li>\n <li class='itemize'>Capacity: <\/span>By the Universal Approximation Theorem (UAT), a\n single hidden layer can approximate any continuous function on a\n compact subset of \\(\\mathbb {R}^n\\)<\/span>. However, achieving sufficient representational\n capacity may require the width of the basis (the dimensionality of\n \\(\\theta \\)<\/span>) to grow exponentially with the input dimension.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Capable of global generalization, including\n limited OOD extrapolation, as always if and only if <\/span>the true\n generative function lies within the span of the fixed hypothesis\n class. Empirically, has weaker inductive bias and sample efficiency\n than Level 3, though with better training dynamics.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Fixed-Basis Convexity):<\/span>\n Highly efficient. If the parameterized basis is fixed and randomized\n (e.g., Random Fourier Features, Reservoir Computing), learning\n is restricted to a final linear readout layer. This reduces the\n problem to convex Ordinary Least Squares, solvable in \\(\\mathcal {O}(N |\\theta |^2)\\)<\/span> time. If the\n parameters are actively trained (e.g., a shallow neural network),\n the landscape becomes non-convex but generally avoids the severe\n vanishing gradient pathologies of deeper architectures.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-deep-compositional-functions-hierarchical-architectures'><a id='x1-5000'><\/a>Level 3: Deep Compositional Functions (Hierarchical Architectures)<\/h3>\nThe introduction of sequential algebraic composition and intermediate\nrepresentations: \\(f(x) = (h_L \\circ h_{L-1} \\circ \\dots \\circ h_1)(x)\\)<\/span>.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The function permits exponential compression of\n specific representational classes by computing intermediate states,\n reusing sub-functions to build hierarchical features.\n \n \n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>Each layer \\(h_i\\)<\/span> is a piecewise affine map\n that acts to fold and quotient the space. Geometrically, a shallow\n network (Level 2) requires \\(k\\)<\/span> distinct hyperplanes to polygonize a\n circular decision boundary; a deep network can use absolute-value\n folds (e.g., ReLUs) to fold the space such that after 4 folds a single<\/span>\n linear hyperplane cut creates a 16-sided polygon. Furthermore,\n intermediate layers act as quotient maps, identifying structurally\n equivalent points (symmetries and invariances) that may be highly\n distant under the ambient metric \\(d_X\\)<\/span>.\n <\/li>\n <li class='itemize'>\n Mathematical Grounding (Circuit & Approximation Theory):<\/span>\n Deep networks bypass the bottlenecks of shallow networks via Depth\n Separation Theorems<\/span>. <\/p>\n <ul class='itemize2'>\n <li class='itemize'>Discrete space: <\/span>In Boolean circuit complexity, calculating\n the parity of \\(N\\)<\/span> bits requires \\(\\mathcal {O}(2^{N})\\)<\/span> depth-2 gates. However,\n allowing intermediate states (a deeper circuit of XOR gates,\n \\(\\mathsf {NC}^1\\)<\/span> complexity) solves it with \\(\\mathcal {O}(N)\\)<\/span> gates; parity \\(\\notin \\mathsf {AC}^0\\)<\/span> for any constant\n depth; a log-depth\\({NC}^1\\)<\/span> XOR-tree does it in \\(O(N)\\)<\/span>.\n <\/li>\n <li class='itemize'>Continuous space: <\/span><a href='https:\/\/arxiv.org\/abs\/1602.04485'>Telgarsky (2016)<\/a> and <a href='https:\/\/arxiv.org\/abs\/1512.03965'>Eldan & Shamir\n (2016)<\/a> demonstrated that there exist functions computable by\n deep neural networks of polynomial width that require strictly\n exponential <\/span>width to be approximated by shallow networks.<\/li><\/ul>\n <\/li>\n <li class='itemize'>\n Capacity: <\/span>Depth allows the construction of decision boundaries with\n exponentially complex Betti numbers5<\/span><\/sup>5<\/span><\/sup> In topology, Betti numbers\n simply count the number of \u201dholes\u201d of different dimensions in a shape. The\n 0-th Betti number is the number of distinct connected pieces, the 1st\n is the number of circular holes (like a donut), and the 2nd is the\n number of hollow voids (like a balloon). In the context of classification,\n higher Betti numbers mean the decision boundary can separate highly\n fragmented or \u201dswiss-cheese-like\u201d clusters of data.<\/span><\/span><a id='x1-5001r6'><\/a> (topological holes and\n connected components) using \\(\\sim \\)<\/span> linear number of parameters.\n <\/p>\n <ul class='itemize2'>\n <li class='itemize'>Bianchini and Scarselli (2014) showed that the sum of Betti\n numbers of a deep network\u2019s expressible regions can grow\n exponentially with its depth \\(\\mathcal {O}(2^L)\\)<\/span>, while only requiring parameters\n proportional to \\(\\mathcal {O}(L W^2)\\)<\/span> where \\(L\\)<\/span> is depth and \\(W\\)<\/span> is width. A shallow\n \n \n network would require an exponentially wider layer to achieve\n the same topological complexity.<\/li><\/ul>\n <\/li>\n <li class='itemize'>Generalization: <\/span>If <\/span>training succeeds, enables compositional\n generalization<\/span>. Because intermediate representations capture\n structural invariances (e.g. quotienting via nonlinearities), the function\n can extrapolate accurately to OOD data. However, as the folds that\n capture the invariances and symmetries are (almost always) static, in\n struggles to represent higher-order invariances, like parameterized\n manifolds.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Non-Convex Credit Assignment):<\/span>\n The optimization landscape is highly non-convex, riddled with\n saddle points, and computationally demanding. Learning requires\n backpropagation to solve complex credit assignment across hierarchical\n layers. The compute cost scales linearly with depth and quadratically\n with width, necessitating massively parallel hardware. Crucially,\n learning here relies heavily on the geometry of overparameterization<\/span>,\n which acts to smooth the loss landscape and make otherwise\n unnavigable local minima into saddles traversable via stochastic\n gradient descent.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-statebound-sequential-machines-dynamical-systems-and-automata'><a id='x1-6000'><\/a>Level 4: State-Bound Sequential Machines (Dynamical Systems and\nAutomata)<\/h3>\nThe domain shifts from fixed-length vectors to trajectories and sequences:\n\\(f: X^* \\to Y^*\\)<\/span>. This entails temporal recursion and\/or internal state. Levels 0\u20133\nconcern approximation of fixed-arity maps; 4\u20136 concern computation\nover unbounded inputs, where the relevant complexity measure\nchanges from hypothesis-class capacity to computational model\npower.<\/span>\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Computations are defined via the recurrence \\(s_t = \\psi (s_{t-1}, x_t)\\)<\/span>,\n processing inputs along a strictly 1-dimensional metric progression\n (time) via a fixed-size internal memory.6<\/span><\/sup>6<\/span><\/sup> With unbounded precision\n and time, RNNs are Turing-complete (Siegelmann\u2013Sontag) – here we\n assume finite precision. <\/span><\/span><a id='x1-6001r7'><\/a>\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>This level bridges the continuous\n and discrete domains. These functions are dynamical systems, so\n evaluation shifts from pointwise distances to trajectory distances\n (e.g., dynamic time warping). If the function map contains distinct\n attractors, it stores information; if it is a contraction, it exhibits\n fading memory. If the state is topologically discrete then it is a\n type of finite automata.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Automata Theory): <\/span>Governed\n formally by the Chomsky Hierarchy and the Myhill-Nerode\n Theorem. Fixed-state sequential machines map perfectly to Finite\n State Machines (bounded \\(\\mathcal {O}(1)\\)<\/span> memory, so cannot solve \\(a^n b^n\\)<\/span>) grammars;\n with augmented fixed-mechanism memory, Push-Down Automata\n (can solve \\(a^n b^n\\)<\/span> but not \\(a^n b^n c^n\\)<\/span>) etc.\n <\/li>\n <li class='itemize'>Capacity: <\/span>Memory and state-transitions are bounded by the\n internal capacity of the transition function \\(\\psi \\)<\/span>, but the temporal\n operations scale linearly with the sequence length.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Introduces systematic length extrapolation<\/span>.\n The model can be trained on trajectories or sequences of length\n \\(N\\)<\/span> and generalize to length \\(N+M\\)<\/span> (OOD), provided the underlying\n generative grammar or dynamic transition rule \\(\\psi \\)<\/span> was correctly\n identified. In practice, this is quite hard: semi-continuous7<\/span><\/sup>7<\/span><\/sup> Floats\n are rationals, not reals<\/span><\/span><a id='x1-6002r8'><\/a> transformers and RNNs struggle with length\n generalization.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Temporal Pathologies):<\/span>\n Dominated by the extreme difficulty of temporal credit assignment.\n Because the mapping \\(s_t = \\psi (s_{t-1}, x_t)\\)<\/span> is iterated recursively, the Jacobian\n of the transition function is multiplied sequentially over time.\n Depending on the spectral radius of this Jacobian, gradients\n will deterministically vanish or explode (Backpropagation\n Through Time). Learning long-term dependencies requires heavy\n architectural interventions\u2014such as gating mechanisms (LSTMs)\n or structured linear state-spaces\u2014to explicitly force the memory\n dynamics to remain stable and differentiable.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-expanding-state-sequential-machines-transformers'><a id='x1-7000'><\/a>Level 4.5: Expanding state sequential machines (Transformers)<\/h3>\n \n \nPolynomially bounded computation with linearly growing state. This\nstate can be appended to, but cannot be modified, which enables parallel\ntraining.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Rather than compressing history into a fixed-capacity\n vector \\(s_t\\)<\/span> (Level 4), computation acts over an explicitly growing\n memory buffer (e.g., the Context Window \/ KV Cache). This\n class is inherently composite: it evaluates sequences by embedding\n a Level 1 kernel smoother (softmax attention) parameterized by\n Level 2 affine maps (FFN layers), stacked into a Level 3 deep\n hierarchy.\n <\/li>\n <li class='itemize'>Topological Mechanism (Dynamic computation graphs):<\/span>\n Replaces the strictly 1-dimensional progression of time with a\n dynamically weighted, fully connected graph. The topological\n distance between the \\(1\\)<\/span>st and \\(N\\)<\/span>-th input token is forcibly collapsed\n to a single \\(\\mathcal {O}(1)\\)<\/span> hop.8<\/span><\/sup>8<\/span><\/sup> This dense routing topology effectively simulates\n the \u201cmultiple heads\u201d of a Level 5 Turing Machine, allowing distant\n structural dependencies to interact directly without physical temporal\n traversal.<\/span><\/span><a id='x1-7001r9'><\/a> The \u201cmetric\u201d determining interactions is not the ambient\n space, but a dynamically computed data-dependent affinity\n (query-key dot products).\n <\/li>\n <li class='itemize'>Mathematical Grounding (Circuit Complexity):<\/span>\n A bounded-depth Transformer operating in a single forward pass\n without recurrence is formally restricted to the complexity class\n \\(\\mathsf {TC}^0\\)<\/span>. It is theoretically incapable of computing inherently sequential\n problems (e.g., evaluating arbitrary deterministic finite automata\n or calculating parity over long strings) purely in the forward\n pass. However, when combined with chain-of-thought, the output\n tape itself serves as an externally expanding state, effectively\n mimicking Level 5 algorithmic indirection and pushing the model\u2019s\n expressivity toward \\(\\mathsf {P}\\)<\/span>-completeness (Merrill & Sabharwal).\n <\/li>\n <li class='itemize'>Capacity: <\/span>State capacity grows linearly \\(\\mathcal {O}(N)\\)<\/span> with the sequence,\n completely eliminating the information bottleneck and fading\n memory limits of Level 4 recurrent systems. This perfect recall\n comes at the cost of computational complexity, which (in standard\n dense attention) scales quadratically \\(\\mathcal {O}(N^2)\\)<\/span>, bounding the maximum\n sequence length by available physical memory bandwidth rather\n than theoretical representational limits.\n \n \n <\/li>\n <li class='itemize'>Generalization: <\/span>Exhibits deeply bifurcated generalization\n properties. Systematic length extrapolation (OOD length) is\n notoriously fragile; because the attention manifold is calibrated\n for a specific maximum \\(N\\)<\/span> during training, longer sequences\n fundamentally distort the softmax entropy and positional\n geometries. Conversely, the explicitly preserved state enables\n profound in-context learning<\/span>: the architecture can act as\n a meta-learner, essentially performing non-parametric Level 1\n interpolation over the novel token state provided at inference time,\n achieving algorithmic generalization without weight updates.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Parallel\n Credit Assignment): <\/span>Exceedingly favorable for gradient descent.\n By unrolling the temporal recurrence into a spatial graph (causal\n masking over a simultaneous batch), it completely bypasses the\n sequential Jacobian multiplications that cause vanishing\/exploding\n gradients in Level 4 (BPTT). The error signal propagates directly\n across all tokens in \\(\\mathcal {O}(1)\\)<\/span> depth per layer. Optimization is therefore\n bottlenecked not by the fragility of sequential temporal dynamics,\n but by the memory limits of large batch, high-dimensional\n non-convex geometry (Level 3).<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-turingcomplete-computation'><a id='x1-8000'><\/a>Level 5: Turing-Complete Computation<\/h3>\nUnbounded computation with unbounded memory. The function is\ninstantiated by an algorithm that dynamically manipulates arbitrary\nstate.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Functions where the mapping from input to output is\n achieved via algorithms capable of navigating an arbitrary amount\n of state over an arbitrary number of steps.\n <\/li>\n <li class='itemize'>\n Topological Mechanism (The Geometry of Indirection):<\/span>\n Computation in Levels 4 and 4.5 are bound to the fixed 1D topology of\n Time. Level 5 escapes this: the order of computation is itself\n computed<\/span>. <\/p>\n <ul class='itemize2'>\n <li class='itemize'>This in turn leads to the natural architectural hierarchy\n within Turing-complete computation. If computation is\n fundamentally the traversal of a directed acyclic dependency\n graph, then a single-head, single-tape Turing Machine forces\n a strict 1-dimensional embedding of this graph. If causally\n linked variables are distant, the machine must physically\n traverse the intervening tape, costing time.\n <\/li>\n <li class='itemize'>Introducing multiple heads <\/span>on a single tape allows concurrent\n access to distant regions, effectively acting as dynamic\n \u201cpointers\u201d that bridge disparate parts of the graph without\n requiring continuous physical traversal.\n <\/li>\n <li class='itemize'>A multi-tape <\/span>Turing Machine extends this further by\n providing parallel, independent 1-dimensional workspaces,\n allowing complex data routing and decoupling previously\n entangled computations.\n <\/li>\n <li class='itemize'>Taking this to the limit, Random Access Memory (RAM)\n induces absolute new locality<\/span>.\n <\/li>\n <li class='itemize'>Memory indirection9<\/span><\/sup>9<\/span><\/sup> An old adage in computer science says\n that all problems can be solved with another level of indirection…<\/span><\/span><a id='x1-8001r10'><\/a>\n acts as a dynamically constructed shortcut edge in the\n dependency graph, collapsing the metric distance between any\n two causally linked states strictly to \\(\\mathcal {O}(1)\\)<\/span>.10<\/span><\/sup>10<\/span><\/sup> In reality, this is <\/span>\\(O(\\log n)\\)\n <\/span>cost due to the cost of communication (speed of light, energy) as\n bits must be in physically different locations. (Compare this with\n the quadratic cost of graph attention in a transformer.)<\/span><\/span><a id='x1-8002r11'><\/a>\n <\/li>\n <li class='itemize'>Example: palindrome recognition requires \\(O(N^2)\\)<\/span> on a single-head\n single-tape TM; can be done in \\(O(N)\\)<\/span> with two heads or two tapes.<\/li><\/ul>\n <\/li>\n <li class='itemize'>Mathematical Grounding (Computability Theory): <\/span>The\n complexity of a function is no longer measured by VC dimension, but\n by Kolmogorov Complexity <\/span>\\(K(x)\\)<\/span> (the length of the shortest program\n that computes the output).\n <\/li>\n <li class='itemize'>Capacity (Time\/Space Complexity): <\/span>Driven by the Time\n Hierarchy Theorem. A multi-tape Turing Machine can solve\n \n \n certain problems in \\(\\mathcal {O}(N \\log N)\\)<\/span> time that a single-tape TM requires \\(\\mathcal {O}(N^2)\\)<\/span> time to\n solve, purely by overcoming the topological constraints of a 1D\n tape.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Algorithmic equivalence. This represents the\n ultimate theoretical ceiling of OOD generalization: if the exact\n algorithmic generator of the data is discovered, generalization is\n perfect.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Combinatorial Discontinuity):<\/span>\n Exceptionally hostile and fundamentally non-differentiable. The search\n space of discrete algorithms and logic is vast, discontinuous, and lacks\n the smooth gradient geometry required for continuous optimization.\n Learning at this level (e.g., Program Synthesis, Inductive Logic\n Programming) requires navigating combinatorial spaces via discrete\n search algorithms (Monte Carlo Tree Search, Evolutionary Algorithms,\n or Reinforcement Learning). Finding the optimal algorithm is\n theoretically uncomputable in the limit, forcing practical learning to\n rely on heuristics.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-hypercomputation-the-theoretical-ceiling'><a id='x1-9000'><\/a>Level 6: Hypercomputation (The Theoretical Ceiling)<\/h3>\nFunctions that represent valid mathematical mappings \\(f: X \\to Y\\)<\/span> but cannot be\ninstantiated, evaluated, or learned by any finite physical or algorithmic\ncomputational device.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Mappings that inherently require a Turing Oracle or\n infinite computational steps to resolve. They exist strictly as\n abstract mathematical realities rather than executable procedures.\n <\/li>\n <li class='itemize'>Topological Mechanism (The Limit of Reachability): <\/span>Not\n very meaningful. In the geometric interpretation of computation as\n the traversal of a dependency graph, these functions are analogous\n to disconnected components or paths of infinite length.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Computability & Set Theory):<\/span>\n Governed by the strict limits of uncomputability. Canonical\n examples include the Halting Function (determining if an arbitrary\n Turing machine halts), the Busy Beaver function, and the exact\n calculation of Kolmogorov Complexity itself.\n <\/li>\n <li class='itemize'>Capacity: <\/span>Complete. This level encompasses the entirety of the\n mathematical universe, including the uncountable infinities of\n mappings that transcend Turing computability (demonstrable via\n Cantor\u2019s diagonal argument).\n <\/li>\n <li class='itemize'>Generalization: <\/span>Empirically moot. Because\n these functions cannot be represented by computable architectures\n or approximated to arbitrary precision by finite algorithms, the\n concept of generalization does not apply. Its inclusion in this\n taxonomy serves strictly to establish the absolute upper bound,\n delineating the universe of pure mathematical mappings from the\n infinitely smaller subset of computable representations.\n <\/li>\n <li class='itemize'>Learnability & Optimization : <\/span>Impossible.<\/li><\/ul>\n \n<\/main><\/body> \n<\/html>\n\n","protected":false},"excerpt":{"rendered":"A Taxonomy of Function Representations and Computational Expressivity pdf version of this post 1 Introduction The goal of this document is to better understand what types of functions exist, with the intuition that functions are knowledge, and so a taxonomy of functions is a taxonomy of the ways to represent knowledge. Descriptive categorization is helpful […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-257","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts\/257","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/comments?post=257"}],"version-history":[{"count":2,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts\/257\/revisions"}],"predecessor-version":[{"id":259,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts\/257\/revisions\/259"}],"wp:attachment":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/media?parent=257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/categories?post=257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/tags?post=257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

{"id":257,"date":"2026-09-03T23:34:03","date_gmt":"2026-09-03T23:34:03","guid":{"rendered":"https:\/\/springtail.ai\/wp\/?p=257"},"modified":"2026-09-03T23:34:03","modified_gmt":"2026-09-03T23:34:03","slug":"a-taxonomy-of-function-representations","status":"publish","type":"post","link":"https:\/\/springtail.ai\/wp\/2026\/09\/03\/a-taxonomy-of-function-representations\/","title":{"rendered":"A Taxonomy of Function Representations"},"content":{"rendered":"\n \n \nA Taxonomy of Function Representations and Computational\nExpressivity<\/title> \n<meta charset='utf-8' \/> \n<meta content='TeX4ht (https:\/\/tug.org\/tex4ht\/)' name='generator' \/> \n<meta content='width=device-width,initial-scale=1' name='viewport' \/> \n<link href='springtail-blog.css' rel='stylesheet' type='text\/css' \/> \n<meta content='function-classes.tex' name='src' \/> \n<script>window.MathJax = { tex: { tags: \"ams\", }, }; <\/script> \n<script async='async' id='MathJax-script' src='https:\/\/cdn.jsdelivr.net\/npm\/mathjax@3\/es5\/tex-chtml-full.js' type='text\/javascript'><\/script> \n<style>\ntable{ \n border-left:solid black 1px; border-right:solid black 1px; \n border-top:solid black 1px; border-bottom:solid black 1px; \n border-collapse: collapse;\n}\n #TBL-2-1-{border-bottom: 1px solid black;}\n #TBL-2-1{border-right:1px solid black;}\n #TBL-2-2{border-right:1px solid black;}\n #TBL-2-3{border-right:1px solid black;}\n #TBL-2-4{border-right:1px solid black;}\n #TBL-2-5{border-right:1px solid black;}\n #TBL-2-6{border-right:1px solid black;}\n #TBL-2-7{border-right:1px solid black;}\n<\/style>\n<\/head><body><main>\n<a href='https:\/\/springtail.ai\/wp\/wp-content\/uploads\/2026\/09\/function-classes.pdf'>pdf version of this post<\/a>\n <h3 class='sectionHead' id='introduction'>1 <\/span> <a id='x1-10001'><\/a>Introduction<\/h3>\nThe goal of this document is to better understand what types of functions\nexist, with the intuition that <\/span>functions are knowledge<\/span>, and so a taxonomy of\nfunctions is a taxonomy of the ways to represent knowledge. Descriptive\ncategorization is helpful for:<\/span> <\/p>\n <ul class='itemize1'>\n <li class='itemize'>Finding gaps and continuations: what\u2019s missing, and why? What\n classes of functions can <\/span>not <\/span>be easily represented by other classes?<\/span>\n <\/li>\n <li class='itemize'>Improving the capacity and generalization properties of models –\n to better match the \u2018true\u2019 function that generated the data.<\/span>1<\/span><\/sup>1<\/span><\/sup> See<\/span>\n <a href='https:\/\/springtail.ai\/wp\/2026\/02\/16\/to-build-a-ml-strange-loop\/'>previous post\u2019s<\/span><\/a> discussion of equivalence classes<\/span><\/span><a id='x1-1001r2'><\/a>\n <\/li>\n <li class='itemize'>Enhancing the learning & optimization algorithms that build\n them, e.g. for learning the right function with less data or fewer\n interactions. Function inverses, which map data back to generating\n funcions, are <\/span>themselves <\/span>functions \/ algorithms that need to be\n derived or learned<\/span>2<\/span><\/sup>2<\/span><\/sup> DL, of course, derives them with the chain rule,\n but this is only one means of propagating information from data to a\n compressed model. Inverses might well range from LUTs to heuristics\n to algorithms – they are in general not in the same class as the forward\n function!<\/span><\/span><a id='x1-1002r3'><\/a>.<\/span><\/li><\/ul>\n Most of the functions levels below are, at the limit, interchangeable – you\ncan approximate any input-output mapping (or algorithm) with a giant\nlook-up table. Functional equivalence means that extensional properties are\nthe same, while intensional properties may differ. LUTs can be tremendously\n<\/span>inefficient <\/span>in terms of learning and storage; they have effectively zero\ncompression, hence <\/span>\\(\\sim 0\\) <\/span>generalization. As you get higher and higher levels of\ncompression you <\/span>generally <\/span>need more sophisticated algorithms for inducing\nthe function from data, as not only may one element of the function affect\nmany or all outputs, but frequently relationships between functional elements\n(pairwise and higher-order) affect the outputs. Indeed, a key element of\ncompression is to form representations from pairwise and higher-order\ninteractions; this is critical for compositionality. Another key element is\nre-use, which enables the few-to-many expansions during function\napplication.<\/span>\n<\/p> At the limit of this, I argue <\/span><a href='https:\/\/springtail.ai\/wp\/2026\/02\/16\/to-build-a-ml-strange-loop\/'>elsewhere<\/span><\/a> that the induction algorithm must\nbe a strange loop. This is a loop (as in iteration or recurrence) in which state\nvariables index over abstraction itself, e.g. whether functions are treated as\n \n \nthe result of computation (data) or the cause of computation (code). There\nare a wide variety of strange loops, from the trivial oscillators of like \u201cthis\nstatement is false\u201d to the knowledge and abstraction generating strange loops\nwe embody. Open-ended induction \/ compression requires repeated,\nrecurrent abstraction-generation to circumvent exponential hypothesis\nspace.<\/span>\n<\/p> \\(\\sim \\)<\/span>\n<\/p> The remainder of this document was created with the help Gemini and\nClaude; I tried to edit down into reasonable coherence. About half the\nexamples (on folding and ordering computation, XOR problem, others) are\nmy own, the rest are filled in by AI. I think more work can be done wrt\ndescribing the learning and generalization properties of each class – properties\nwhich are uncomputable and hence only heuristic \/ approximate – but that\u2019s\na matter of continuing effort.<\/span>\n<\/p>\n <div class='maketitle'>\n\n <div class='author'><\/div> \n<div class='date'><\/div>\n <\/div>\n <section class='abstract' role='doc-abstract'> \n<h3 class='abstracttitle'>\nAbstract<\/span>\n<\/h3>\n\n <\/p> A function is a mathematical mapping <\/span>\\(f: X \\to Y\\)<\/span>.<\/span>3<\/span><\/sup>3<\/span><\/sup> Elements of\n X and Y could be scalars or vectors; the non-function case\n that they are sets is not covered here, though it\u2019s important\n for random processes…<\/span><\/span><a id='x1-1003r4'><\/a> The properties of this mapping\n can be categorized by the mechanism of representation,\n the geometry of the resulting hypothesis class, and the\n computational architecture used to calculate it. The following\n taxonomy attempts to segment functions by their structural\n or compressional efficiency, progressing from unstructured\n memorization to the theoretical limits of computation. In\n \n \n the real world, functions are in one or several classes, or\n are compositions of different classes, leading to composite\n attributes, costs, and complexity.<\/span>\n<\/p>\n<\/section>\n \n <h3 class='likesectionHead' id='level-explicit-tabular-representations-pure-memorization'><a id='x1-2000'><\/a>Level 0: Explicit Tabular Representations (Pure Memorization)<\/h3>\nThe domain \\(X\\)<\/span> and codomain \\(Y\\)<\/span> are treated as unstructured, discrete &\nunordered sets.4<\/span><\/sup>4<\/span><\/sup> Technically: \u201cEquipped solely with the discrete\ntopology.\u201d<\/span><\/span><a id='x1-2001r5'><\/a>\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The function is represented explicitly as an exhaustive\n set of tuples \\((x, y)\\)<\/span>.\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>The concept of \u201cnearness\u201d does not\n exist. Because the discrete topology isolates every point, \\(f(x)\\)<\/span> has zero\n mutual information to \\(f(x’)\\)<\/span> , \\(\\forall x, x’ : x’ \\neq x\\)<\/span>.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Information Theory): <\/span>The\n information required to specify the mapping is the Shannon\n entropy of the full Cartesian product. For a discrete domain of size\n \\(|X| = 2^{b_{in}}\\)<\/span> and codomain size \\(|Y| = 2^{b_{out}}\\)<\/span>, specification requires \\(\\mathcal {O}(2^{b_{in}} \\times b_{out})\\)<\/span> bits.\n <\/li>\n <li class='itemize'>Capacity: <\/span>The Vapnik-Chervonenkis (VC) dimension is strictly \\(|X|\\)<\/span>\n (or infinite for infinite domains). Every possible mapping can be\n represented, provided sufficient memory.\n <\/li>\n <li class='itemize'>Generalization: <\/span>None. Out-of-distribution (OOD) generalization\n is impossible without any inductive bias or structural priors.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Triviality): <\/span>Learning is an \\(\\mathcal {O}(1)\\)<\/span>\n memory allocation and storage operation per sample. There is no\n optimization landscape to navigate, no loss surface, and no credit\n \n \n assignment. The computational cost of training and querying can\n be constant in the case of a hashmap, or can scale gracefully with\n other datastructures.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-metric-topological-interpolators-nonparametric-smoothness'><a id='x1-3000'><\/a>Level 1: Metric & Topological Interpolators (Non-Parametric\nSmoothness)<\/h3>\nThe domain \\(X\\)<\/span> is endowed with a metric \\(d_X(x, x’)\\)<\/span> or a specified topological\nstructure, allowing the representation to leverage the native geometry of\nthe input space.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The \u201cordered look-up table.\u201d Outputs for novel\n inputs are interpolated based on proximity to known inputs,\n bounded by a smoothness constraint (e.g., Lipschitz or H\u00f6lder\n continuity). Examples include \\(k\\)<\/span>-Nearest Neighbors, Splines, and\n Kernel Methods.\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>The function constructs a\n non-parametric cover of the space. It relies entirely on the ambient\n metric \\(d_X\\)<\/span> to define local neighborhoods, meaning it cannot discover\n new geometries; it merely smooths over the existing one.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Approximation Theory): <\/span>The\n complexity of this class is measured by Metric Entropy (or\n Kolmogorov \\(\\epsilon \\)<\/span>-entropy). To approximate a function with smoothness\n \\(s\\)<\/span> in a \\(d\\)<\/span>-dimensional space to an error \\(\\epsilon \\)<\/span>, the required number of\n interpolation points scales as \\(\\mathcal {O}(\\epsilon ^{-d\/s})\\)<\/span>.\n <\/li>\n <li class='itemize'>Capacity: <\/span>The capacity scales strictly with the size of the observed\n data, theoretically capable of approximating any continuous\n function given infinite samples.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Can be robust; inductive bias is obviously toward\n in-distribution interpolation. OOD generalization (extrapolation)\n fails gracefully; the degradation is deterministic, governed directly\n by the chosen metric. In-domain generalization is inherently\n bottlenecked by the Curse of Dimensionality <\/span>(evident in the \\(d\/s\\)<\/span>\n \n \n exponent), as the volume of the space grows exponentially faster\n than it can be populated by data points.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Convex Bottlenecks): <\/span>Many\n methods (kNN, splines) do not have optimization and hence\n do not have a loss landscape. For kernel methods (e.g., Kernel\n Ridge Regression, SVMs), the optimization landscape is strictly\n convex, guaranteeing convergence to a global optimum without\n the risk of local minima. However, learning is heavily bottlenecked\n by computational complexity rather than optimization difficulty.\n Constructing and inverting the kernel Gram matrix requires \\(\\mathcal {O}(N^3)\\)<\/span> time\n and \\(\\mathcal {O}(N^2)\\)<\/span> memory. This can be remedied with random features, as\n discussed in the next section.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-shallow-parameterized-maps-fixedbasis-global-approximation'><a id='x1-4000'><\/a>Level 2: Shallow Parameterized Maps (Fixed-Basis Global\nApproximation)<\/h3>\nThe function takes the form \\(f(x) = \\phi (x; \\theta )\\)<\/span>, decoupling the representation from the ambient\nmetric \\(d_X\\)<\/span> by embedding the input into a learned or fixed parameterized\nspace.<a href='function-classes2.html#fn1x0'>1<\/sup><\/a><\/span><a id='x1-4001f1'><\/a> \n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The mapping relies on a finite set of parameters\n decoupled from the size of the training data. This encompasses\n single<\/span>-hidden-layer neural networks and fixed global basis\n expansions.\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>The map \\(x \\mapsto \\phi (x; \\theta )\\)<\/span> pushes the data forward\n into a fixed-dimensional latent manifold, substituting the extrinsic\n metric of the input space with an intrinsic, learned metric. Rather\n than covering a space with small local metric balls (Level 1), it\n defines global level sets. For example, a hidden layer \\(\\sigma (W x + b)\\)<\/span> partitions\n the space globally; rather than defining a local region of interest,\n a single hyperplane slices the entire domain space in half.\n \n \n <\/li>\n <li class='itemize'>Mathematical Grounding (Statistical Learning Theory):<\/span>\n Complexity is bounded by the size and numerical resolution of\n the parameter space \\(\\mathcal {O}(|\\theta |)\\)<\/span>, formally measured by VC Dimension or\n Rademacher Complexity. This parameter compression enables a\n degree of geometric generalization.\n <\/li>\n <li class='itemize'>Capacity: <\/span>By the Universal Approximation Theorem (UAT), a\n single hidden layer can approximate any continuous function on a\n compact subset of \\(\\mathbb {R}^n\\)<\/span>. However, achieving sufficient representational\n capacity may require the width of the basis (the dimensionality of\n \\(\\theta \\)<\/span>) to grow exponentially with the input dimension.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Capable of global generalization, including\n limited OOD extrapolation, as always if and only if <\/span>the true\n generative function lies within the span of the fixed hypothesis\n class. Empirically, has weaker inductive bias and sample efficiency\n than Level 3, though with better training dynamics.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Fixed-Basis Convexity):<\/span>\n Highly efficient. If the parameterized basis is fixed and randomized\n (e.g., Random Fourier Features, Reservoir Computing), learning\n is restricted to a final linear readout layer. This reduces the\n problem to convex Ordinary Least Squares, solvable in \\(\\mathcal {O}(N |\\theta |^2)\\)<\/span> time. If the\n parameters are actively trained (e.g., a shallow neural network),\n the landscape becomes non-convex but generally avoids the severe\n vanishing gradient pathologies of deeper architectures.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-deep-compositional-functions-hierarchical-architectures'><a id='x1-5000'><\/a>Level 3: Deep Compositional Functions (Hierarchical Architectures)<\/h3>\nThe introduction of sequential algebraic composition and intermediate\nrepresentations: \\(f(x) = (h_L \\circ h_{L-1} \\circ \\dots \\circ h_1)(x)\\)<\/span>.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>The function permits exponential compression of\n specific representational classes by computing intermediate states,\n reusing sub-functions to build hierarchical features.\n \n \n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>Each layer \\(h_i\\)<\/span> is a piecewise affine map\n that acts to fold and quotient the space. Geometrically, a shallow\n network (Level 2) requires \\(k\\)<\/span> distinct hyperplanes to polygonize a\n circular decision boundary; a deep network can use absolute-value\n folds (e.g., ReLUs) to fold the space such that after 4 folds a single<\/span>\n linear hyperplane cut creates a 16-sided polygon. Furthermore,\n intermediate layers act as quotient maps, identifying structurally\n equivalent points (symmetries and invariances) that may be highly\n distant under the ambient metric \\(d_X\\)<\/span>.\n <\/li>\n <li class='itemize'>\n Mathematical Grounding (Circuit & Approximation Theory):<\/span>\n Deep networks bypass the bottlenecks of shallow networks via Depth\n Separation Theorems<\/span>. <\/p>\n <ul class='itemize2'>\n <li class='itemize'>Discrete space: <\/span>In Boolean circuit complexity, calculating\n the parity of \\(N\\)<\/span> bits requires \\(\\mathcal {O}(2^{N})\\)<\/span> depth-2 gates. However,\n allowing intermediate states (a deeper circuit of XOR gates,\n \\(\\mathsf {NC}^1\\)<\/span> complexity) solves it with \\(\\mathcal {O}(N)\\)<\/span> gates; parity \\(\\notin \\mathsf {AC}^0\\)<\/span> for any constant\n depth; a log-depth\\({NC}^1\\)<\/span> XOR-tree does it in \\(O(N)\\)<\/span>.\n <\/li>\n <li class='itemize'>Continuous space: <\/span><a href='https:\/\/arxiv.org\/abs\/1602.04485'>Telgarsky (2016)<\/a> and <a href='https:\/\/arxiv.org\/abs\/1512.03965'>Eldan & Shamir\n (2016)<\/a> demonstrated that there exist functions computable by\n deep neural networks of polynomial width that require strictly\n exponential <\/span>width to be approximated by shallow networks.<\/li><\/ul>\n <\/li>\n <li class='itemize'>\n Capacity: <\/span>Depth allows the construction of decision boundaries with\n exponentially complex Betti numbers5<\/span><\/sup>5<\/span><\/sup> In topology, Betti numbers\n simply count the number of \u201dholes\u201d of different dimensions in a shape. The\n 0-th Betti number is the number of distinct connected pieces, the 1st\n is the number of circular holes (like a donut), and the 2nd is the\n number of hollow voids (like a balloon). In the context of classification,\n higher Betti numbers mean the decision boundary can separate highly\n fragmented or \u201dswiss-cheese-like\u201d clusters of data.<\/span><\/span><a id='x1-5001r6'><\/a> (topological holes and\n connected components) using \\(\\sim \\)<\/span> linear number of parameters.\n <\/p>\n <ul class='itemize2'>\n <li class='itemize'>Bianchini and Scarselli (2014) showed that the sum of Betti\n numbers of a deep network\u2019s expressible regions can grow\n exponentially with its depth \\(\\mathcal {O}(2^L)\\)<\/span>, while only requiring parameters\n proportional to \\(\\mathcal {O}(L W^2)\\)<\/span> where \\(L\\)<\/span> is depth and \\(W\\)<\/span> is width. A shallow\n \n \n network would require an exponentially wider layer to achieve\n the same topological complexity.<\/li><\/ul>\n <\/li>\n <li class='itemize'>Generalization: <\/span>If <\/span>training succeeds, enables compositional\n generalization<\/span>. Because intermediate representations capture\n structural invariances (e.g. quotienting via nonlinearities), the function\n can extrapolate accurately to OOD data. However, as the folds that\n capture the invariances and symmetries are (almost always) static, in\n struggles to represent higher-order invariances, like parameterized\n manifolds.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Non-Convex Credit Assignment):<\/span>\n The optimization landscape is highly non-convex, riddled with\n saddle points, and computationally demanding. Learning requires\n backpropagation to solve complex credit assignment across hierarchical\n layers. The compute cost scales linearly with depth and quadratically\n with width, necessitating massively parallel hardware. Crucially,\n learning here relies heavily on the geometry of overparameterization<\/span>,\n which acts to smooth the loss landscape and make otherwise\n unnavigable local minima into saddles traversable via stochastic\n gradient descent.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-statebound-sequential-machines-dynamical-systems-and-automata'><a id='x1-6000'><\/a>Level 4: State-Bound Sequential Machines (Dynamical Systems and\nAutomata)<\/h3>\nThe domain shifts from fixed-length vectors to trajectories and sequences:\n\\(f: X^* \\to Y^*\\)<\/span>. This entails temporal recursion and\/or internal state. Levels 0\u20133\nconcern approximation of fixed-arity maps; 4\u20136 concern computation\nover unbounded inputs, where the relevant complexity measure\nchanges from hypothesis-class capacity to computational model\npower.<\/span>\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Computations are defined via the recurrence \\(s_t = \\psi (s_{t-1}, x_t)\\)<\/span>,\n processing inputs along a strictly 1-dimensional metric progression\n (time) via a fixed-size internal memory.6<\/span><\/sup>6<\/span><\/sup> With unbounded precision\n and time, RNNs are Turing-complete (Siegelmann\u2013Sontag) – here we\n assume finite precision. <\/span><\/span><a id='x1-6001r7'><\/a>\n <\/li>\n <li class='itemize'>Topological Mechanism: <\/span>This level bridges the continuous\n and discrete domains. These functions are dynamical systems, so\n evaluation shifts from pointwise distances to trajectory distances\n (e.g., dynamic time warping). If the function map contains distinct\n attractors, it stores information; if it is a contraction, it exhibits\n fading memory. If the state is topologically discrete then it is a\n type of finite automata.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Automata Theory): <\/span>Governed\n formally by the Chomsky Hierarchy and the Myhill-Nerode\n Theorem. Fixed-state sequential machines map perfectly to Finite\n State Machines (bounded \\(\\mathcal {O}(1)\\)<\/span> memory, so cannot solve \\(a^n b^n\\)<\/span>) grammars;\n with augmented fixed-mechanism memory, Push-Down Automata\n (can solve \\(a^n b^n\\)<\/span> but not \\(a^n b^n c^n\\)<\/span>) etc.\n <\/li>\n <li class='itemize'>Capacity: <\/span>Memory and state-transitions are bounded by the\n internal capacity of the transition function \\(\\psi \\)<\/span>, but the temporal\n operations scale linearly with the sequence length.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Introduces systematic length extrapolation<\/span>.\n The model can be trained on trajectories or sequences of length\n \\(N\\)<\/span> and generalize to length \\(N+M\\)<\/span> (OOD), provided the underlying\n generative grammar or dynamic transition rule \\(\\psi \\)<\/span> was correctly\n identified. In practice, this is quite hard: semi-continuous7<\/span><\/sup>7<\/span><\/sup> Floats\n are rationals, not reals<\/span><\/span><a id='x1-6002r8'><\/a> transformers and RNNs struggle with length\n generalization.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Temporal Pathologies):<\/span>\n Dominated by the extreme difficulty of temporal credit assignment.\n Because the mapping \\(s_t = \\psi (s_{t-1}, x_t)\\)<\/span> is iterated recursively, the Jacobian\n of the transition function is multiplied sequentially over time.\n Depending on the spectral radius of this Jacobian, gradients\n will deterministically vanish or explode (Backpropagation\n Through Time). Learning long-term dependencies requires heavy\n architectural interventions\u2014such as gating mechanisms (LSTMs)\n or structured linear state-spaces\u2014to explicitly force the memory\n dynamics to remain stable and differentiable.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-expanding-state-sequential-machines-transformers'><a id='x1-7000'><\/a>Level 4.5: Expanding state sequential machines (Transformers)<\/h3>\n \n \nPolynomially bounded computation with linearly growing state. This\nstate can be appended to, but cannot be modified, which enables parallel\ntraining.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Rather than compressing history into a fixed-capacity\n vector \\(s_t\\)<\/span> (Level 4), computation acts over an explicitly growing\n memory buffer (e.g., the Context Window \/ KV Cache). This\n class is inherently composite: it evaluates sequences by embedding\n a Level 1 kernel smoother (softmax attention) parameterized by\n Level 2 affine maps (FFN layers), stacked into a Level 3 deep\n hierarchy.\n <\/li>\n <li class='itemize'>Topological Mechanism (Dynamic computation graphs):<\/span>\n Replaces the strictly 1-dimensional progression of time with a\n dynamically weighted, fully connected graph. The topological\n distance between the \\(1\\)<\/span>st and \\(N\\)<\/span>-th input token is forcibly collapsed\n to a single \\(\\mathcal {O}(1)\\)<\/span> hop.8<\/span><\/sup>8<\/span><\/sup> This dense routing topology effectively simulates\n the \u201cmultiple heads\u201d of a Level 5 Turing Machine, allowing distant\n structural dependencies to interact directly without physical temporal\n traversal.<\/span><\/span><a id='x1-7001r9'><\/a> The \u201cmetric\u201d determining interactions is not the ambient\n space, but a dynamically computed data-dependent affinity\n (query-key dot products).\n <\/li>\n <li class='itemize'>Mathematical Grounding (Circuit Complexity):<\/span>\n A bounded-depth Transformer operating in a single forward pass\n without recurrence is formally restricted to the complexity class\n \\(\\mathsf {TC}^0\\)<\/span>. It is theoretically incapable of computing inherently sequential\n problems (e.g., evaluating arbitrary deterministic finite automata\n or calculating parity over long strings) purely in the forward\n pass. However, when combined with chain-of-thought, the output\n tape itself serves as an externally expanding state, effectively\n mimicking Level 5 algorithmic indirection and pushing the model\u2019s\n expressivity toward \\(\\mathsf {P}\\)<\/span>-completeness (Merrill & Sabharwal).\n <\/li>\n <li class='itemize'>Capacity: <\/span>State capacity grows linearly \\(\\mathcal {O}(N)\\)<\/span> with the sequence,\n completely eliminating the information bottleneck and fading\n memory limits of Level 4 recurrent systems. This perfect recall\n comes at the cost of computational complexity, which (in standard\n dense attention) scales quadratically \\(\\mathcal {O}(N^2)\\)<\/span>, bounding the maximum\n sequence length by available physical memory bandwidth rather\n than theoretical representational limits.\n \n \n <\/li>\n <li class='itemize'>Generalization: <\/span>Exhibits deeply bifurcated generalization\n properties. Systematic length extrapolation (OOD length) is\n notoriously fragile; because the attention manifold is calibrated\n for a specific maximum \\(N\\)<\/span> during training, longer sequences\n fundamentally distort the softmax entropy and positional\n geometries. Conversely, the explicitly preserved state enables\n profound in-context learning<\/span>: the architecture can act as\n a meta-learner, essentially performing non-parametric Level 1\n interpolation over the novel token state provided at inference time,\n achieving algorithmic generalization without weight updates.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Parallel\n Credit Assignment): <\/span>Exceedingly favorable for gradient descent.\n By unrolling the temporal recurrence into a spatial graph (causal\n masking over a simultaneous batch), it completely bypasses the\n sequential Jacobian multiplications that cause vanishing\/exploding\n gradients in Level 4 (BPTT). The error signal propagates directly\n across all tokens in \\(\\mathcal {O}(1)\\)<\/span> depth per layer. Optimization is therefore\n bottlenecked not by the fragility of sequential temporal dynamics,\n but by the memory limits of large batch, high-dimensional\n non-convex geometry (Level 3).<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-turingcomplete-computation'><a id='x1-8000'><\/a>Level 5: Turing-Complete Computation<\/h3>\nUnbounded computation with unbounded memory. The function is\ninstantiated by an algorithm that dynamically manipulates arbitrary\nstate.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Functions where the mapping from input to output is\n achieved via algorithms capable of navigating an arbitrary amount\n of state over an arbitrary number of steps.\n <\/li>\n <li class='itemize'>\n Topological Mechanism (The Geometry of Indirection):<\/span>\n Computation in Levels 4 and 4.5 are bound to the fixed 1D topology of\n Time. Level 5 escapes this: the order of computation is itself\n computed<\/span>. <\/p>\n <ul class='itemize2'>\n <li class='itemize'>This in turn leads to the natural architectural hierarchy\n within Turing-complete computation. If computation is\n fundamentally the traversal of a directed acyclic dependency\n graph, then a single-head, single-tape Turing Machine forces\n a strict 1-dimensional embedding of this graph. If causally\n linked variables are distant, the machine must physically\n traverse the intervening tape, costing time.\n <\/li>\n <li class='itemize'>Introducing multiple heads <\/span>on a single tape allows concurrent\n access to distant regions, effectively acting as dynamic\n \u201cpointers\u201d that bridge disparate parts of the graph without\n requiring continuous physical traversal.\n <\/li>\n <li class='itemize'>A multi-tape <\/span>Turing Machine extends this further by\n providing parallel, independent 1-dimensional workspaces,\n allowing complex data routing and decoupling previously\n entangled computations.\n <\/li>\n <li class='itemize'>Taking this to the limit, Random Access Memory (RAM)\n induces absolute new locality<\/span>.\n <\/li>\n <li class='itemize'>Memory indirection9<\/span><\/sup>9<\/span><\/sup> An old adage in computer science says\n that all problems can be solved with another level of indirection…<\/span><\/span><a id='x1-8001r10'><\/a>\n acts as a dynamically constructed shortcut edge in the\n dependency graph, collapsing the metric distance between any\n two causally linked states strictly to \\(\\mathcal {O}(1)\\)<\/span>.10<\/span><\/sup>10<\/span><\/sup> In reality, this is <\/span>\\(O(\\log n)\\)\n <\/span>cost due to the cost of communication (speed of light, energy) as\n bits must be in physically different locations. (Compare this with\n the quadratic cost of graph attention in a transformer.)<\/span><\/span><a id='x1-8002r11'><\/a>\n <\/li>\n <li class='itemize'>Example: palindrome recognition requires \\(O(N^2)\\)<\/span> on a single-head\n single-tape TM; can be done in \\(O(N)\\)<\/span> with two heads or two tapes.<\/li><\/ul>\n <\/li>\n <li class='itemize'>Mathematical Grounding (Computability Theory): <\/span>The\n complexity of a function is no longer measured by VC dimension, but\n by Kolmogorov Complexity <\/span>\\(K(x)\\)<\/span> (the length of the shortest program\n that computes the output).\n <\/li>\n <li class='itemize'>Capacity (Time\/Space Complexity): <\/span>Driven by the Time\n Hierarchy Theorem. A multi-tape Turing Machine can solve\n \n \n certain problems in \\(\\mathcal {O}(N \\log N)\\)<\/span> time that a single-tape TM requires \\(\\mathcal {O}(N^2)\\)<\/span> time to\n solve, purely by overcoming the topological constraints of a 1D\n tape.\n <\/li>\n <li class='itemize'>Generalization: <\/span>Algorithmic equivalence. This represents the\n ultimate theoretical ceiling of OOD generalization: if the exact\n algorithmic generator of the data is discovered, generalization is\n perfect.\n <\/li>\n <li class='itemize'>Learnability & Optimization (Combinatorial Discontinuity):<\/span>\n Exceptionally hostile and fundamentally non-differentiable. The search\n space of discrete algorithms and logic is vast, discontinuous, and lacks\n the smooth gradient geometry required for continuous optimization.\n Learning at this level (e.g., Program Synthesis, Inductive Logic\n Programming) requires navigating combinatorial spaces via discrete\n search algorithms (Monte Carlo Tree Search, Evolutionary Algorithms,\n or Reinforcement Learning). Finding the optimal algorithm is\n theoretically uncomputable in the limit, forcing practical learning to\n rely on heuristics.<\/li><\/ul>\n \n <h3 class='likesectionHead' id='level-hypercomputation-the-theoretical-ceiling'><a id='x1-9000'><\/a>Level 6: Hypercomputation (The Theoretical Ceiling)<\/h3>\nFunctions that represent valid mathematical mappings \\(f: X \\to Y\\)<\/span> but cannot be\ninstantiated, evaluated, or learned by any finite physical or algorithmic\ncomputational device.\n<\/p>\n <ul class='itemize1'>\n <li class='itemize'>Concept: <\/span>Mappings that inherently require a Turing Oracle or\n infinite computational steps to resolve. They exist strictly as\n abstract mathematical realities rather than executable procedures.\n <\/li>\n <li class='itemize'>Topological Mechanism (The Limit of Reachability): <\/span>Not\n very meaningful. In the geometric interpretation of computation as\n the traversal of a dependency graph, these functions are analogous\n to disconnected components or paths of infinite length.\n <\/li>\n <li class='itemize'>Mathematical Grounding (Computability & Set Theory):<\/span>\n Governed by the strict limits of uncomputability. Canonical\n examples include the Halting Function (determining if an arbitrary\n Turing machine halts), the Busy Beaver function, and the exact\n calculation of Kolmogorov Complexity itself.\n <\/li>\n <li class='itemize'>Capacity: <\/span>Complete. This level encompasses the entirety of the\n mathematical universe, including the uncountable infinities of\n mappings that transcend Turing computability (demonstrable via\n Cantor\u2019s diagonal argument).\n <\/li>\n <li class='itemize'>Generalization: <\/span>Empirically moot. Because\n these functions cannot be represented by computable architectures\n or approximated to arbitrary precision by finite algorithms, the\n concept of generalization does not apply. Its inclusion in this\n taxonomy serves strictly to establish the absolute upper bound,\n delineating the universe of pure mathematical mappings from the\n infinitely smaller subset of computable representations.\n <\/li>\n <li class='itemize'>Learnability & Optimization : <\/span>Impossible.<\/li><\/ul>\n \n<\/main><\/body> \n<\/html>\n\n","protected":false},"excerpt":{"rendered":"A Taxonomy of Function Representations and Computational Expressivity pdf version of this post 1 Introduction The goal of this document is to better understand what types of functions exist, with the intuition that functions are knowledge, and so a taxonomy of functions is a taxonomy of the ways to represent knowledge. Descriptive categorization is helpful […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-257","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts\/257","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/comments?post=257"}],"version-history":[{"count":2,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts\/257\/revisions"}],"predecessor-version":[{"id":259,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/posts\/257\/revisions\/259"}],"wp:attachment":[{"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/media?parent=257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/categories?post=257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/springtail.ai\/wp\/wp-json\/wp\/v2\/tags?post=257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}