Hey Pentti, We Did It Again!: Differentiable vector-symbolic types that prove polynomial termination
Eilene Tomkins-Flanagan ([email protected]) · 2025
Read Hey Pentti, We Did It Again!: Differentiable vector-symbolic types that prove polynomial termination by Eilene Tomkins-Flanagan ([email protected]) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16533.txt.
Introduction
Eilene Tomkins-Flanagan, Connor Hanley, and Mary A. Kelly present a new coding tongue in a 2025 paper. Their tongue, Doug, makes each typed program halt in polynomial time. Polynomial time means run time grows in a tame, power-like way. Doug's types and terms are coded as points in a learned space. That space comes from vector-symbolic codes, which pack facts into long number lists.
Doug reworks a known light linear tongue with strict use rules. Its slot-value code lets near points hold near types in sense. Types can thus be learned by a neural net, not just set by hand. The team links skill gains to program search in this tongue. Fast skill gains, at a human pace, are the long goal.
Catalog record
| CREATOR | Eilene Tomkins-Flanagan ([email protected]) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16533
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hey Pentti, We Did It Again!: Differentiable vector-symbolic types that prove polynomial termination Eilene Tomkins-Flanagan ([email protected]) Abstract We present a typed computer language, Doug, in which all typed programs may be proved to halt in polynomial time, encoded in a vector-symbolic architecture (VSA). Doug is just an encoding of the light linear functional programming language (LLFPL) described by Schimanski (2009) . The types of Doug are encoded using a slot-value encoding scheme based on holographic declarative memory (HDM; Kelly et al. (2020) ). The terms of Doug are encoded using a variant of the Lisp VSA defined by Tomkins-Flanagan & Kelly (2024) . Doug allows for some points on the embedding space of a neural network to be interpreted as types, where the types of nearby points are similar both in structure and content. Types in Doug are therefore learnable by a neural network. Following Chollet (2019) , Card et al. (1983) , and Newell & Rosenbloom (1981) , we view skill as the application of a procedure, or program of action, that causes a goal to be satisfied. Skill acquisition may therefore be expressed as program synthesis . Using Doug, we hope to describe a form of learning of skilled behaviour that follows a human-like pace of skill acquisition ( Heathcote et al. (2000) , i.e., substantially faster than brute force ;) , exceeding the efficiency of all currently existing approaches Kaplan et al. (2020) ; A.L. Jones (2021) ; Chollet (2024) . Our approach brings us one step closer to modeling human mental representations, as they must actually exist in the brain, and those representations’ acquisition, as they are actually learned. Keywords: polynomial time type system; representation learning; vector-symbolic architecture Chollet (2019) proposed a novel model for intelligence: an intelligent agent does not just solve problems in its environment in service to its goals (as we might infer it does in the Markov decision process model found in reinforcement learning , Sutton & Barto (2018) , pp. 46-53). Instead, an intelligent agent acquires the skills necessary to the task , and uses its acquired skills to solve problems in service to its goals. Chollet’s model of “skill” is an extremely general one. In his view, a skill is a program : a procedure made up of well-defined steps, which, when followed, will transform the environment from an initial state into a desired state. By separating the intelligent agent into an intelligent system that generates skills, and skill programs that realize the agent’s competencies, Chollet frames the problem of intelligence as one of an ability to acquire skills from sparse examples in a great variety of problem types. Following Chollet, a greater intelligence within some scope of problems is one that can acquire the skills to solve problems in that scope with a minimum of foreknowledge and training, and a more general intelligence is intelligent, up to some degree, in a greater variety of scopes, more exhaustive of the space of possible problems. The Chollet model may have a familiar ring for cognitive modelers, however. The Goals, Operators, Methods, and Selection rules (GOMS; Card et al. (1983) , ch. 5) model describes skilled behaviour as a deployment of procedures that will tend to satisfy an agent’s goals. In GOMS, an agent with some goal G uses its selection rules to choose a method that, the agent expects, will cause G to be satisfied, if followed. A method is a procedure in the sense we used above: a sequence of well-defined steps. In the case of GOMS, the steps are operators , discrete actions the agent can take that transform the state of the environment, or the agent’s internal state. Following the procedure laid out by the selected method, the environment is transformed into a state whereby the goal G is satisfied. Newell (1990) situates GOMS within the Soar cognitive architecture, stating that GOMS “posits a set of mechanisms and structures” (p. 285) that can be formalized with the Soar architecture, and goes on to express skill acquisition in Soar (ch. 6.5) as a kind of search for increasingly efficient procedures that satisfy goals. Chollet refers to the problem of acquiring skills as “program synthesis” (p. 30), that is, search for a procedure, with some given effect. Hutter (2005) showed that synthesizing an optimal program that predicts or represents the environment allows an agent to behave in an optimally goal-directed (i.e., rational) way, with minimal extra machinery. In this way, the problems of skill acquisition and representation learning can be thought of as transformable into one another. Hutter, unfortunately, also finds (ch. 1.7), that program synthesis is profoundly nontrivial. In fact, finding a program that optimally predicts an arbitrary environment is incomputable, because it involves comparing programs in light of their computational effects, and some programs cannot be proven either to eventually halt or run forever Turing (1936) , so their computational effects cannot be known either until they halt or until the end of time, whichever comes first. Even if we restrict ourselves to considering only programs up to some maximum finite length, if we are to be certain we have found the optimal representation, we must do an ugly exhaustive search through all possible programs up to our maximum length (which is intractable, in the sense of taking an exponentially long amount of time as a function of the maximum length) and, for each program, find its shortest representation that halts within some maximum time (which is also intractable). Hutter’s finding of a doubly-exponential rate of skill acquisition is consistent with the “power law” described by Newell & Rosenbloom (1981) , however, Heathcote et al. (2000) show that their law is an artifact of population averaging, and humans in fact acquire skill exponentially faster than Newell & Rosenbloom (1981) believed. Unsurprisingly so, as Newell & Rosenbloom (1981) modeled skill acquisition as a simple, heuristic-informed (but in the worst case, like Hutter’s model, brute-force) search, and managed to satisfy their power law. It seems obvious that, in order to be useful, a method of program synthesis that exhibits intelligence should be substantially better than this sort of brute-force approach. Chollet (2019) ’s ARC task was designed to demonstrate the efficiency of human intelligence relative to existing AI approaches, and the importance of efficient program synthesis. A model approaching the ARC task that showed some early success was DreamCoder Ellis et al. (2021) , which used a similar method to Hutter’s, albeit synthesizing programs using a form of heuristic informed search involving a neural network. DreamCoder has since been surpassed by the GPT o-series models Chollet (2024) , but Chollet (2025) notes that both approaches seem to behave like exhaustive search: It’s always possible to … logarithmically improve your performance by throwing more compute at the problem. And of course this is true for o1, but even before that it was also true for brute force program search systems. Assuming you have the right [domain-specific language], then extremely crude, basic, brute-force program iteration can solve ARC at human level. (49:55) We would like to constrain program synthesis so that search is restricted only to programs likely to be useful to solving a given problem. If we make good assumptions about