Bubble sort displays emergentdelayed gratification that is not explicitly in the algorithm.
→ We underestimate the competencies of even the most basic algorithms, and do not know the full extent of their capabilities.
→ It does not take cells, life, or huge complexity to have emergent goal-directed competencies.
Key Findings
Cell-view (distributed) versions of sorting algorithms can work as efficiently as traditional centralized versions
The algorithms show unexpected robustness and problem-solving abilities not explicitly coded into them
When different “algotypes” (cells using different sorting algorithms) are mixed, they show emergent clustering behavior
The algorithms demonstrate “delayed gratification” - temporarily moving away from their goal to achieve better results
Algotype Clustering
The unexpected clustering of similar algotypes (elements using the same sorting algorithm) emerges despite:
No explicit programming for this behavior
No ability for elements to detect others’ algotypes
No direct communication about algorithm types
The clustering occurs during the sorting process before elements reach their final positions, with aggregation values reaching about 60-70% (significantly above the random 50%). When the authors allowed duplicate numbers, the clustering became even more pronounced since elements weren’t forced apart by the final sorting requirement.
There's a deterministic start and end point, but inbetween we have emergent complexity, interesting stuff happens.
Traditional vs Multi-Agent (Cell-View) Algorithms
Traditional sorting: A single top-down controller sees the entire array and decides which elements to swap. Operations happen sequentially - the controller examines pairs or elements one at a time.
Multi-agent sorting: Each element is an independent agent (implemented as a thread) that can only see its local neighbors. All agents run in parallel, making decisions simultaneously based on local rules. No central authority coordinates their actions.
The cell-view versions work as follows: Cell-View Bubble Sort: Each cell compares itself with immediate neighbors. Moves left if smaller than left neighbor, right if bigger than right neighbor.
Cell-View Insertion Sort: Each cell can see all cells to its left. Moves left only if the left side is already sorted AND it’s smaller than its left neighbor.
Cell-View Selection Sort: Each cell has an “ideal” target position (initially leftmost). Tries to swap with whoever occupies that position if it has a smaller value. If swap fails, shifts ideal position right.
Movement constraints:
Elements can only swap with adjacent neighbors (no jumping)
Array is strictly 1D with only left/right movement through swaps
All cells execute their algorithms continuously in parallel
Cell Thread→⎩⎨⎧check neighbors according to algorithmrequest swap if conditions metwait for response/mutexperform swap if allowed
Frozen Cells: Simulating Damage
The researchers introduced “frozen cells” to simulate damaged or defective elements that can’t follow the algorithm properly:
Movable Frozen Cells (“lack of initiative”):
Cannot initiate swaps themselves
CAN be moved by other active cells
Act like passive obstacles that others can push around
Immovable Frozen Cells (“lack of motility”):
Cannot initiate swaps
CANNOT be moved by others either
Complete roadblocks in the array
Key findings with frozen cells:
Cell-view algorithms show better error tolerance than traditional versions
Bubble sort handles movable frozen cells best
Selection sort handles immovable frozen cells best
Algorithms demonstrate emergent “delayed gratification” - temporarily decreasing sortedness to navigate around obstacles
Code a proper reimplementation + visualization (Saved instructions from a visualization vibe code attempt, for future reference with a better model / time for deeper investigation:)
read classical-sorting-algorithms-as-a-model-of-morphogenesis-self-sorting-arrays-reveal-un
expected-competencies-in-a-minimal-model-of-basal-intelligence, including all figures,
clone the
original implementation https://github.com/Zhangtaining/cell_research
reproduce it, then work on this:
Here's a detailed specification for the ideal cell-view sorting visualization: Cell-View Sorting Algorithm Visualization Requirements Core Concept Visualize how distributed sorting algorithms work when each element is an autonomous agent making local decisions in parallel, compared to traditional centralized control. Key Features to Illustrate 1. Parallel Decision Making - Show ALL cells evaluating their local situation simultaneously - Clearly distinguish between "decision phase" (all cells thinking) and "execution phase" (resolving conflicts) - Visual indicators for each cell's desired action (arrows, highlighting, etc.) 2. Local vs Global Knowledge - Bubble sort: Each cell only sees immediate neighbors - Insertion sort: Cells can see all elements to their left - Selection sort: Cells know their "ideal" position but must navigate locally - Visual representation of each cell's "field of view" 3. Frozen Cell Mechanics - Immovable frozen cells: Complete roadblocks (dark color, lock icon) - Movable frozen cells: Passive obstacles that can be pushed (lighter color, different icon) - Show how algorithms navigate around or push through obstacles Visualization Layout 4. Three-Algorithm Comparison View - 3 rows (one per algorithm) showing same initial array - Each row has: - Sorting animation (bar chart) - Sortedness graph (line chart showing progress) - Algorithm-specific indicators 5. Animation Phases Per Step - Phase 1: "Scanning" - highlight all cells evaluating their situation - Phase 2: "Decision" - show all cells that want to move (arrows/highlights) - Phase 3: "Conflict Resolution" - indicate which moves will execute - Phase 4: "Execution" - animate the actual swaps - Phase 5: "Result" - show new state with sortedness update 6. Visual Encoding - Cell colors by algorithm type (blue/green/red) - Frozen cell states (dark gray locked, light gray movable) - Active/thinking cells (glowing or pulsing effect) - Movement desires (arrows showing intended direction) - Conflicts (crossing arrows, red highlights) Metrics and Information 7. Live Statistics - Current sortedness percentage - Step counter - Number of swaps executed - Number of cells that wanted to move vs actually moved 8. Sortedness Graph - X-axis: Step number - Y-axis: Sortedness percentage (0-100%) - Show all three algorithms on same scale for comparison - Highlight "delayed gratification" dips 9. Action Log - Text description of current phase - Which cells are active - What decisions were made - How conflicts were resolved Interactive Elements (if possible) 10. Playback Controls - Play/pause - Step forward/backward - Speed control - Jump to specific step 11. Configuration - Array size - Number and placement of frozen cells - Initial array configuration (random, reverse sorted, partially sorted) - Algorithm parameters Technical Implementation Notes 12. True Parallelism Simulation - Each cell should have a thread-like representation - Show race conditions and how they're resolved - Make it clear that execution order affects outcome 13. Emergent Behaviors to Highlight - Delayed gratification (sortedness temporarily decreasing) - Different efficiency patterns - How frozen cells create different challenges for each algorithm - Unexpected clustering in mixed-algorithm scenarios 14. Educational Annotations - Callout boxes explaining key concepts - Pseudocode for each algorithm's local rules - Comparison to traditional implementations Output Formats - GIF for easy embedding in documents - MP4 for presentations with playback control - Interactive HTML5 for web viewing - Static frames for paper figures This visualization should make it immediately clear how these algorithms differ from traditional sorting, why parallel execution matters, and how simple local rules lead to complex global behaviors.
you may very well deviate in how you finally end up implementing the visualization, if
you think there are better ways — the plan was generated with a much earlier, much dumber model the final implementation code and artefacts you can dump into Downloads on host. oh and yh prlly to verify tings visually ofc good if you can like make snapshosts yourself etc. I think the task / goal of understanding and explanation and so on is quite clear - so I will let you work autonomously and only review the end result.
no need to read the vault note - it adds no info.