Research Task: Structural Description Complexity and Incremental Learning by Extensional Transformations I want you to investigate a nonstandard notion of function complexity and, if feasible, develop a search algorithm for learning functions under this notion from partial data. The most important instruction is conceptual: Do not turn this into ordinary program synthesis over expressions that compute `Goal(x)` pointwise. The object whose complexity matters is the extensional function itself, and a description is a sequence of structurally defined transformations that turns a constant function into that extension. Equally important: look for simple, elegant, generative principles. If the formalism begins accumulating many independently maintained objects, auxiliary states, special cases, or bookkeeping mechanisms, treat that as evidence that the underlying abstraction has not yet been found. The goal is not merely to make something work. The goal is to discover the smallest set of mechanisms from which the observed phenomena follow naturally. 1. Running problem Use tic-tac-toe as the principal finite example: ```text OuterCoor = {A, C} InnerCoor = {B} Coor = OuterCoor + InnerCoor Axis = {X, Y} Coor2 = Coor^Axis Player = {X, O} Cell = Player + {Empty} Field = Coor2 -> Cell Result = {XWon, OWon, Draw, Illegal} Goal = Field -> Result ``` There are [ 3^9 = 19683 ] possible fields. Assume the intended task concerns terminal fields. Any nonterminal field can simply be classified as `Illegal`; do not introduce `NonTerminal` as an additional output class unless there is a compelling structural reason. Initially focus on structure induced by the input type rather than exploiting shared structure between `Player` in the input and winner labels in the output. 2. Central notion of complexity Start with a constant extensional function [ g_0 : Field \to Result, ] for example [ g_0(F)=Illegal. ] The target is produced by transformations [ g_0\to g_1\to\cdots\to g_k=Goal. ] There should ideally be one fundamental kind of transformation. A transformation does two things: 1. structurally specifies a subset (S\subseteq X) of the input domain; 2. changes the output on exactly that subset to a chosen output value. Schematically, [ T_{S,y}(g)(x) \begin{cases} y,&x\in S, g(x),&x\notin S. \end{cases} ] The substantive question is therefore: How cheaply can the subset (S) be specified using structure available on the input domain? Do not regard pointwise modification as a separate escape hatch. A singleton [ S={x} ] is simply the least structurally compressed instance of the same operation. Likewise, an orbit, a multiplicity class, a higher-order structural fiber, a union of related fibers, or some recursively defined subset are all instances of exactly the same operation if they are simply different ways of structurally specifying (S). This unification is important. Ideally the theory should not contain separate primitives such as: ```text change one point change one orbit change one multiplicity class change a threshold region ``` unless there is a genuine mathematical reason to distinguish them. Instead, seek a general language of structural subset descriptions, after which output replacement is uniform. 3. Description cost is fundamentally the cost of specifying a subset Certificate complexity should be measured in bits, not merely in number of transformations. A certificate might have the form [ (S_1,y_1),\ldots,(S_k,y_k) ] and cost approximately [ L(C) \sum_i \left( L(S_i\mid \text{input structure}) + L(y_i) \right), ] possibly with reuse/composition discounts if structure derived earlier can be referenced economically. The central object is therefore something like [ L(S\mid X,\mathcal S), ] the description cost of a subset of (X) relative to its structural organization. For example, specifying one object among nine should ordinarily require more information than specifying one among three. But do not hard-code this particular formula too early. Derive the coding scheme from the structural language if possible. The essential behavior should be: - a highly canonical structural subset is cheap; - a subset requiring several symmetry-breaking choices costs more; - an arbitrary subset ultimately approaches ordinary extensional specification cost. Thus universality should arise naturally: every finite subset is describable because, in the worst case, it can be structurally specified down to individual points. Singleton selection is not external to the theory. It is the limiting case of structural subset selection after all useful sharing has disappeared. 4. Structure should generate more structure A major part of the research is determining what "using structure" actually means. The type expression ```text Field = Coor2 -> Cell ``` already induces automorphisms, equivalence relations, quotient spaces, multiplicities, and relations between those quotients. Do not stop at first-order group orbits. I suspect the important phenomenon is that quotienting by one symmetry naturally produces new objects that themselves carry additional structure. For example, if (n) interchangeable positions contain values from a finite set (K), the quotient [ K^n/S_n ] is naturally represented by multiplicity vectors [ (m_k)_{k\in K}, \qquad \sum_k m_k=n. ] This object is not merely a flat collection of equivalence classes. It has relations such as [ m\to m-e_i+e_j, ] corresponding to moving one occurrence from one category to another. It has boundaries, multiplicities, adjacency, possibly order-like structure, and perhaps further symmetries. This is an example of what I informally mean by higher-order structure. Please investigate what mathematical language describes this most naturally. Candidates may include: - symmetric powers; - quotient structures; - configuration spaces; - orbit spaces; - combinatorial species; - association schemes; - coherent configurations; - relational quotients; - simplicial or cell complexes; - graphs induced on multiplicity vectors; - something else entirely. Do not force terminology. Prefer whichever formulation makes structural subset specification and search simplest. 5. Tic-tac-toe as a structural derivation The type itself contains considerable geometry. From ```text Coor = {A,C} + {B} Axis = {X,Y} Coor2 = Coor^Axis ``` one can derive the ordinary square symmetries. Winning lines need not necessarily be listed individually. For example: - axial lines arise by varying one axis while fixing the other coordinate; - the diagonals can be related to automorphisms of `Coor`. For a line (\ell), restriction of a field gives a three-cell object. Quotienting by the interchangeable positions on that line produces a profile [ (#X,#O,#Empty), ] an element of something like [ \operatorname{Sym}^3(Cell). ] Then one can form higher-level multiplicities over the structural family of lines, such as [ W_X(F) #{ \ell: \text{profile}(F|_\ell)=(3,0,0) }. ] Likewise for O. The number of empty cells is another multiplicity: [ E(F)=#Empty(F). ] A simple hand-written extensional derivation might then be: ```text START: every field -> Illegal SELECT structurally: fields with E = 0 and no winning line SET: -> Draw SELECT structurally: fields with positive O winning-line multiplicity SET: -> OWon SELECT structurally: fields with positive X winning-line multiplicity SET: -> XWon ``` Do not take this exact certificate as canonical. Investigate whether the same function has a substantially cleaner structural derivation. The important thing is that each step is still conceptually identical: specify a subset of fields structurally, then assign one output to that subset. 6. Learning from partial data The ambitious target is to learn such a certificate from only part of the extensional table. Suppose labels are revealed for roughly 5000 of the 19683 fields. Sampling should not necessarily be IID random. Ensure that important structural fibers/classes are represented adequately, perhaps using orbit-aware or multiplicity-aware sampling. Given [ D={(x_i,y_i)}, ] seek a minimum-description certificate (C) satisfying [ f_C(x_i)=y_i ] for every observed example. Its values on the remaining fields are then predictions. The learning principle is: [ \text{generalization} \text{extension induced by the cheapest structural construction consistent with data}. ] This resembles MDL at the outermost optimization level, but the hypothesis language is deliberately not ordinary evaluator programs. 7. Main algorithmic hypothesis: incremental structural repair I suspect there is a significantly better way to search these certificates than globally enumerating complete programs. Investigate the following possibility seriously. Process observations incrementally. After seeing [ D_t={(x_1,y_1),\ldots,(x_t,y_t)}, ] maintain some minimal or near-minimal structural description compatible with them. A new observation [ (x_{t+1},y_{t+1}) ] then imposes one additional constraint. If the current extension is wrong at (x*{t+1}), the question is: What is the cheapest structurally describable subset containing the new point on which an output change can be made while preserving all previously required labels? This sounds potentially much smaller than synthesizing an entirely new certificate. If the current function already gives the correct output at (x*{t+1}), the example is still not irrelevant. It removes hypotheses that would modify that point incorrectly later. So the observation changes the allowable future transformations even if it does not change the current extensional function. Try to characterize this without introducing a large amount of independent bookkeeping. There may be a more fundamental object in which: - the current prediction, - the constraints imposed by observations, - and the allowed structural modifications are simply different aspects of the same mathematical state. Finding that object would be more valuable than engineering separate data structures for each role. 8. Proto-geometric intuition There is an intuition that these incremental updates are local movements in a discrete structured space. Do not interpret "geometry" too literally. A Cartesian embedding is natural in some binary cases but can introduce arbitrary orderings when bare sets have size greater than two. The desired idea is invariant: functions related by a cheap structural subset transformation should be close. Thus the language of transformations induces some kind of discrete geometry or metric on extensional functions. If transformations have bit costs, one may imagine an edge [ g\to T_{S,y}(g) ] with weight [ L(S)+L(y). ] The complexity of (f) is then related to shortest weighted distance from a constant function. But this graph is astronomically large, so the research question is whether its structure admits a much more compressed representation. Potential connections include: - Cayley or Schreier graphs; - transformation monoids; - weighted word metrics; - quotient graphs; - refinement lattices; - symmetric-power graphs; - discrete configuration spaces; - shortest paths in implicit state spaces. Use these only if they simplify the actual problem. 9. Seek the smallest ontology possible This is a central methodological requirement. Do not respond to every difficulty by introducing another independent concept. For example, if a proposed solution requires separately maintaining: ```text a current function a partition a quotient hierarchy a symmetry group a version space a set of frozen observations a certificate graph a freedom counter a constraint system ... ``` do not immediately implement all of them. First ask: Why do these objects all seem necessary? Perhaps several are merely projections of one deeper object. Try to find that deeper object. Likewise, if the transformation language starts acquiring many primitive rule types, look for a more general construction of which they are instances. The ideal outcome would have very few fundamental notions, perhaps something like: 1. a structured space; 2. a way of deriving structured quotient/subset descriptions; 3. one weighted operation that changes the output on such a subset. This exact decomposition is only a hypothesis, but the desired level of conceptual compression is approximately this. Prefer a small elegant formalism that explains several phenomena simultaneously over a larger framework that handles them through unrelated machinery. 10. Avoid syntax-first program enumeration Do not begin from a grammar such as ```text Expr := Count(...) | GreaterThan(...) | And(...) | Or(...) | ... ``` and simply enumerate syntax trees until something fits. Such a system may be useful as an implementation backend, but it risks reproducing ordinary program synthesis. Instead ask whether the search can operate directly on structural objects: - fibers; - quotients; - orbit unions; - multiplicity regions; - relations in quotient spaces; - structurally generated subset families. If many syntactically different expressions identify the same subset of fields, ideally they should collapse to one semantic object. The search target is fundamentally a cheap subset of the domain, not a pretty Boolean formula describing it. 11. Canonical subset families may be the key search object Investigate whether the essential search space can be organized around a hierarchy [ \mathcal P_0(X) \subseteq \mathcal P_1(X) \subseteq \mathcal P_2(X) \subseteq\cdots \subseteq 2^X, ] where (\mathcal P*k(X)) contains subsets describable using structural constructions up to some cost or depth. The singleton case should arise naturally somewhere in this hierarchy. A potentially useful objective for repairing an error at (x) is then: [ \min*{S} L(S) ] subject to constraints such as [ x\in S ] and [ S\cap F_{\text{protected}}=\varnothing, ] or more generally that applying the transformation to (S) preserves all observed labels. But do not assume that explicitly storing a set of "protected points" is the best formulation. Look for a structural equivalent. The main question is whether finding the cheapest admissible (S) can be much easier than finding an entire certificate. 12. Description length of structural choices Develop a principled bit-cost model. Important distinctions include: - a canonical construction with no arbitrary choice; - selecting one object among an orbit of size (n); - selecting one quotient class among (k); - specifying a multiplicity value; - specifying an interval or region in a structured count space; - composing already derived structures; - reusing a previously described structural object; - describing a singleton through successive refinements. A likely principle is that a symmetry-breaking choice among (n) indistinguishable alternatives costs approximately [ \log_2 n ] bits. But investigate whether a more general information-theoretic formulation arises naturally. In particular, the cost should depend on how many alternatives remain structurally indistinguishable at the point of choice, not merely on the raw size of the original domain. This may connect description length directly to successive symmetry breaking. 13. Search algorithms to investigate The final search algorithm need not be exact initially. However, search for methods adapted to the structural nature of the hypothesis class. Possibilities include: - shortest-path search over implicitly represented transformations; - dynamic programming on quotient structures; - minimum-cost refinement; - branch-and-bound; - A\* with structural lower bounds; - beam search over subset refinements; - incremental minimum-cost repair; - orbit/stabilizer methods; - canonical augmentation; - memoization by semantic subset rather than syntax; - constraint solving over structural subset families; - local moves with occasional global restructuring. A particularly interesting possibility is that each inconsistent new example triggers a small search centered around that example: 1. identify progressively larger or more abstract structural subsets containing it; 2. reject those that would violate existing observations; 3. find the cheapest admissible subset modification; 4. modify the certificate locally; 5. simplify/recompress if the modification creates a more general structural pattern. Do not assume this greedy procedure is correct. Test when it succeeds and when global restructuring is necessary. 14. Exact tiny models first Before attacking the full tic-tac-toe problem, build tiny systems in which exhaustive optimization is possible. For a small structured domain: 1. enumerate every extensional function; 2. compute the true minimum structural description cost; 3. compare that result to an incremental algorithm; 4. inspect failures. This can reveal whether local updates approximate global optimum and whether the proposed subset language behaves sensibly. Especially test: - highly symmetric functions; - mildly symmetry-breaking functions; - random functions; - functions generated from known short structural certificates. For random functions, complexity should approach extensional description cost. If random labels routinely get very short certificates, the structural language or coding scheme is probably leaking arbitrary information. 15. Full tic-tac-toe experiment After validating the framework on tiny domains: 1. construct all 19683 fields; 2. define the intended four-way classification; 3. choose a structurally sensible training subset, perhaps around 5000 fields; 4. learn a certificate using only those labels; 5. predict the remaining labels; 6. evaluate both prediction quality and certificate bit cost. Compare at minimum against: - trivial extensional memorization; - a random-label control; - perhaps one conventional learner as a sanity baseline. The interesting outcome is not merely high accuracy. The desired result is that the natural tic-tac-toe function is reconstructed by a very low-cost structural sequence of subset transformations, while random labelings are expensive. Inspect the learned certificate semantically. If it achieves good compression through obscure accidental predicates, that is not success. 16. Important questions Try to answer these as concretely as possible. 1. What is the minimal mathematical definition of a structured subset description? 2. Can singleton selection, orbit selection, multiplicity classes, threshold regions, etc. really be unified as instances of one subset-selection mechanism? 3. What structures are canonically induced by the input type? 4. How should higher-order structure be generated from quotient objects? 5. What is the natural description length of a structurally specified subset? 6. Can this cost be related systematically to residual symmetry / numbers of equivalent alternatives? 7. What object simultaneously captures enough information for incremental consistency and future structural transformations without requiring large auxiliary state? 8. Is incremental repair fundamentally a shortest-path problem, a refinement problem, or something else? 9. When a new correctly predicted point is observed, what changes mathematically even though the extensional function does not change? 10. Can this change be represented without explicitly attaching special bookkeeping to every observed point? 11. When an incorrectly predicted point arrives, can the cheapest consistent update be found by a local search over structural subsets containing it? 12. When does greedy/local repair fail and require global recompression? 13. Can structural subset descriptions be canonicalized so the search does not enumerate many equivalent programs? 14. What lower bounds can be placed on the number of additional bits required to accommodate a new observation? 15. What is the right mathematical account of the multiplicity spaces arising in `Field`? 16. Does the natural tic-tac-toe classifier receive a dramatically shorter description than random functions? 17. Does the framework smoothly converge to singleton/extensional specification as structure becomes useless? 18. Can the full complexity be interpreted as weighted distance from a constant function in some naturally induced discrete geometry? 19. Can the same few mechanisms explain both structural compression and symmetry breaking? 20. What existing literature comes closest to this exact construction? 21. Literature search Search broadly, but maintain the distinction between this problem and ordinary program synthesis. Potentially relevant areas include: - MDL and restricted description languages; - algorithmic statistics; - group actions and symmetry reduction; - orbit/stabilizer algorithms; - equivariant learning; - transformation semigroups/monoids; - Cayley and Schreier graphs; - symmetric powers of graphs or structures; - configuration spaces; - combinatorial species; - coherent configurations / association schemes; - partition refinement; - canonical augmentation; - version spaces; - incremental concept learning; - minimum consistent hypothesis learning; - relational learning; - discrete geometry of function spaces. For any close prior work, determine what its primitive object actually is. Does it optimize: - a program computing (f(x))? - a partition of the domain? - an invariant/equivariant predictor? - a sequence of transformations of an extensional function? - a shortest path through structurally defined subsets? I care about those distinctions. 18. Deliverables Produce the following. A. Minimal formalism Give the smallest formulation you can find for: - structured input domain; - structural subset descriptions; - subset-description bit cost; - extensional overwrite transformation; - certificate; - consistency with partial observations; - certificate complexity. Prefer fewer primitives. B. Working prototype Implement enough of the formalism to run finite experiments. Python is preferred unless another language provides a substantial advantage. Keep the implementation understandable and expose the structural objects directly. C. Exact tiny experiments Compute true optimal certificates where exhaustive search is possible. Use these to evaluate any heuristic/incremental algorithm. D. Incremental learner Implement at least one algorithm that consumes examples sequentially and updates a structural certificate. Investigate whether inconsistent observations can usually be repaired by inexpensive local structural changes. E. Tic-tac-toe experiment Learn from a partial labeled table and test on unseen fields. Report both predictive behavior and description length. F. Research memo Explain: - the cleanest abstraction you found; - which initially distinct concepts turned out to be instances of the same mechanism; - where the proposed unification failed; - whether incremental local repair appears viable; - whether a useful discrete geometry emerged; - which parts required global search; - the strongest connection to existing work; - the next experiment that would most reduce uncertainty. 19. Research taste / decision criterion When choosing between two approaches, prefer the one that explains more with less machinery. A good sign is discovering that several seemingly distinct mechanisms are manifestations of one construction. A bad sign is repeatedly adding state variables, rule categories, exception cases, or layers of bookkeeping. Do not confuse implementation modularity with conceptual fundamentality: code may naturally have several classes, while the theory underneath should ideally remain small. In particular, keep returning to this question: What is the minimal structure needed to specify a subset of the input domain cheaply? and then: Given such a subset, how much information does it cost to change the function on it? Everything else should, if possible, emerge from those questions. The hoped-for end state is a theory in which: [ \text{function simplicity} ] means [ \text{short weighted path from a constant extension} ] where each move selects a subset using the intrinsic and recursively induced structure of the input domain and changes its output uniformly. The singleton is not an exception to this picture. It is simply what structural subset specification degenerates to when there is no useful regularity left.