Surprising emergent behavior of sorting algorithms | Michael Levin and Lex Fridman

Quick Overview

The research paper "Classical Sorting Algorithms as a Model of Morphogenesis" demonstrates that simple sorting algorithms, when run with a minimal set of rules analogous to biological processes, exhibit complex, emergent behaviors like 'Delayed Gratification' and 'Clustering' that are typically associated with more sophisticated systems, suggesting that basal forms of intelligence can arise from simple, local interactions.

Key Points: The study models morphogenesis using classical sorting algorithms (Bubble, Insertion, Selection) where each element (cell) follows a fixed 'Algotyipe' (sorting rule). When these simple algorithms operate with local interactions, they surprisingly exhibit emergent competencies like memory, decision-making, and problem-solving, which are usually not expected from such minimal systems. The concept of 'Delayed Gratification Index' is introduced, derived from the trade-off between initial back-tracking (regression in sortedness) and subsequent gains in order. In mixed populations of sorting types (e.g., Bubble and Selection sorts), clustering occurs where cells with the same Algotyipe tend to group together, even if the sorting itself is not complete. The authors suggest that physical laws (like those in biology) do not inherently forbid these complex behaviors, contrasting with traditional programming where algorithms strictly follow explicit, global instructions. The research aims to define the minimal requirements for basal intelligence by observing these complex patterns in simple, non-AI substrates.

Context: This discussion is an interview on the Lex Fridman Podcast featuring a guest, likely one of the paper's authors (Taining Zhang, Adam Goldstein, or Michael Levin), exploring their recent research paper titled "Classical Sorting Algorithms as a Model of Morphogenesis: self-sorting arrays reveal unexpected competencies in a minimal model of basal intelligence." The core concept involves treating elements in an array not as abstract data points, but as autonomous agents ('cells') that follow specific, fixed local rules ('Algotyipes') to sort themselves, drawing parallels between algorithmic behavior and biological development (morphogenesis).