TLDR: Researchers have successfully implemented a complete Lisp programming language using a Vector-Symbolic Architecture (VSA), demonstrating that VSAs are Turing-complete and capable of general computation. This work highlights the critical role of cleanup memories in VSA design and opens new avenues for understanding cognitive processes and developing artificial general intelligence by representing programs as brain-like vector states.
A groundbreaking research paper titled “Hey Pentti, We Did It!: A Fully Vector-Symbolic Lisp” by Eilene Tomkins-Flanagan and Mary Alexandria Kelly from Carleton University presents a significant step in bridging the gap between brain-inspired computing and universal programming languages. The paper details the successful implementation of a complete Lisp programming language using a Vector-Symbolic Architecture (VSA), an approach that has long been theorized but rarely fully realized.
What is a Vector-Symbolic Architecture?
At its core, a VSA is an algebraic system designed to represent and manipulate information using high-dimensional vectors. Unlike traditional computer systems that use discrete symbols, VSAs encode symbols and their relationships as continuous vectors. Imagine representing words or concepts not as distinct entries in a dictionary, but as points in a vast, multi-dimensional space, where similar concepts are closer together. Key properties of VSAs include the ability to combine vectors (like adding or multiplying them) to form new representations, an approximate inverse operation to retrieve components from a combined vector, a method for selecting atomic symbols, a memory system to store and retrieve these symbols, and a way to measure the similarity between any two vectors. This framework offers a compelling model for how the brain might handle both distributed information and symbolic thought.
Lisp and the Concept of Universal Computation
Lisp, one of the oldest programming languages, is renowned for its simplicity and mathematical elegance. The researchers focused on Lisp 1.5, a version known for its minimal set of elementary functions: CONS, CAR, CDR, EQ, ATOM, LAMBDA, COND, and LABEL. These functions, when combined, are sufficient to create any computable program, making Lisp a Turing-complete language. In mathematical terms, Lisp is considered a Cartesian closed category, which is a generalization of what it means to compute. Demonstrating that a VSA can implement Lisp effectively proves that VSAs are also Turing-complete, meaning they can perform any computation that a traditional computer can.
Implementing Lisp in a VSA
The core of this research lies in mapping Lisp’s elementary functions to operations within a VSA. Instead of manipulating bits and bytes, the VSA Lisp manipulates high-dimensional vectors. For instance, the CONS function, which combines two Lisp expressions into a pair, is implemented as a VSA operation that creates a single vector representing the combined pair. Similarly, CAR and CDR, which extract elements from a pair, are VSA operations that retrieve the corresponding components from the combined vector. The implementation uses holographic reduced representations (HRRs), a specific type of VSA that employs circular convolution for its product operation and cosine for similarity measurement. Atomic symbols are sampled from a Gaussian distribution, allowing for a vast number of nearly linearly independent symbols even in high-dimensional spaces.
The Crucial Role of Cleanup Memories
A significant insight from this work is the fundamental importance of “cleanup memories” in VSAs. These memory systems are essential for retrieving precise symbols after potentially lossy VSA operations. The paper highlights that while every VSA has a cleanup memory, their computational properties (speed, capacity, information loss) vary greatly and are critical for achieving Turing-completeness and practical performance. The researchers discuss various types of cleanup memories, including traditional matrix-based approaches, Hopfield networks, and MINERVA2. They identify the Modern Hopfield Network (MHN) as a promising candidate due to its exponential storage capacity and efficient lookup times, despite challenges related to encoding and avoiding retroactive interference.
Also Read:
- Compiling Knowledge for Smarter AI Agents: The NeSyPr Framework
- Unlocking the Free Energy Principle: A New Neural Architecture for Self-Organizing Intelligence
Implications for Cognitive Science and AI
This research has profound implications for both cognitive science and the development of artificial general intelligence (AGI). For cognitive scientists, VSAs offer a compelling model for how the brain might represent and manipulate symbolic structures using distributed neural activity. The ability to implement a Turing-complete language like Lisp within a VSA strengthens the argument that brain states could indeed possess a combinatorial syntax. Furthermore, the paper touches upon the AIXI model, a theoretical framework for universally optimal reinforcement learning, which suggests that intelligent agents might represent observations as shortest-length programs. If human cognition approximates this optimal rationality, then mental representations would necessarily be interpretable as programs. By demonstrating that VSAs can encode and evaluate arbitrary programs, this work opens a pathway for exploring how such “mental programs” could operate within brain-like architectures, potentially even leading to insights into machine consciousness.
