Simple algorithms

Notes on Michael Levin’s article What do algorithms want? A new paper on the emergence of surprising behavior in the most unexpected places.

The spectrum of persuadability

The axis of persuadability: “A proposed way to visualize a continuum of agency, which frames the problem in a way that is testable and drives empirical progress, is via an ‘axis of persuadability’: to what level of control (ranging from brute force micromanagement to persuasion by rational argument) is any given system amenable, given the sophistication of its cognitive apparatus?”¹

Examples given (with some interpretation by me):

• a physical clock (at the far left of the spectrum) can’t be persuaded, argued with, etc. To change its behavior you’d need to alter its hardware. To do that, you’d need to understand its hardware.

• a human being (at the far right of the spectrum) can be persuaded with rational arguments (also threats, etc). This can be done without understanding the details of a human’s hardware.

The field of diverse intelligence

Recognizing systems that have “degrees of intelligence”, with degrees of intelligence defined as “competencies at solving problems in some space.”²

Basal cognition

Minimal systems that exhibit intelligent behavior. See [Basal cognition]

Why study sorting algorithms?

• they are simple and transparent
• they’ve been studied a lot (we assume we know what they can do)
• they’re entirely deterministic
• the process of sorting scrambled elements bears a resemblance to “morphogenetic remodeling” (the repair of biological systems(?))

They’re looking for systems that have “goal-seeking behavior”. What does the system do when presented with barriers?

Typical bubble sort

Essentially, consider the list as pairs of numbers, starting from the left. As indexes (starting with index 0), the pairs are: (0, 1), (1, 2), (2, 3),...(n-1, n). If the first number of a pair is larger than the second number, swap the values.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # optimization
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # if no swaps occurred in a pass through j, the list is sorted:
        if not swapped:
            break

    return arr


nums = [12, -4, 0, 14268, 5, 14268, 8, 9, 2]
print("nums:", nums)

sorted = bubble_sort(nums)
print("sorted:", sorted)

For clarity, here’s a simpler version:

def simpler_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

The modifications made by Levin’s team to the algorithm

They made two changes to the algorithm. Instead of the top-down approach outlined above, each number (they call them “cells”) has its own ability to carry out the algorithm. They also introduced “unreliable computing” (disturbances). I’ll try to get bottom-up cell based algorithm working first.

The code is on GitHub: https://github.com/Zhangtaining/cell_research. Cloning the repo, I didn’t have much luck running the code. It looks like the kind of code I end up with when I’m messing around with something interesting, trying things out.

I’m ignoring the original code’s multithread code for now. Here’s a basic working implementation of its Cell module, without introducing the concept of “unreliable computing”:

• Original code
• My/Claude’s implementation

Unreliable computing

Based on my implementation code that I linked to above:

class CellWithStubborn:
    def __init__(self, value: float, stubborn: bool = False):
        self.value: float = value
        self.stubborn = stubborn
        self.prev: CellWithStubborn | None = None
        self.next: CellWithStubborn | None = None

    def should_swap_next(self) -> bool:
        if not self.next:
            return False
        if self.stubborn:
            return False  # guessing here
        return self.value > self.next.value

  # ...

def demo():
    values = [3, 1, 12, 9, 8, 100, 6, 111, 2, 10, 7, -4, -100, 5, 4, -1000, 17]
    print(f"len(values): {len(values)}")
    print(f"Initial values: {values}")
    tissue = CellTissue(values)
    cell1 = tissue.get_cell_at(5)
    cell2 = tissue.get_cell_at(11)
    if cell1 and cell2:
        print(f"stubborn cell.values: {cell1.value}, {cell2.value}")
        cell1.stubborn = True
        cell2.stubborn = True
    tissue.sort(verbose=True)

This might be demonstrating some of what Levin is getting at:

Initial:[3, 1, 12, 9, 8, 100, 6, 111, 2, 10, 7, -4, -100, 5, 4, -1000, 17]
stubborn cell.values: 100, -4
Step 0: [1, 3, 9, 8, 12, 100, 6, 2, 10, 7, -4, -100, 5, 4, -1000, 17, 111]
Step 1: [1, 3, 8, 9, 12, 100, 2, 6, 7, -4, -100, 5, 4, -1000, 10, 17, 111]
Step 2: [1, 3, 8, 9, 12, 100, 2, 6, -4, -100, 5, 4, -1000, 7, 10, 17, 111]
Step 3: [1, 3, 8, 9, 12, 100, 2, -4, -100, 5, 4, -1000, 6, 7, 10, 17, 111]
Step 4: [1, 3, 8, 9, 12, 100, -4, -100, 2, 4, -1000, 5, 6, 7, 10, 17, 111]
Step 5: [1, 3, 8, 9, 12, 100, -4, -100, 2, -1000, 4, 5, 6, 7, 10, 17, 111]
Step 6: [1, 3, 8, 9, 12, 100, -4, -100, -1000, 2, 4, 5, 6, 7, 10, 17, 111]
Step 7: [1, 3, 8, 9, 12, 100, -4, -1000, -100, 2, 4, 5, 6, 7, 10, 17, 111]
Final:  [1, 3, 8, 9, 12, 100, -4, -1000, -100, 2, 4, 5, 6, 7, 10, 17, 111]
Sorted in 8 iterations

I need to step through this, similar to what I did in Cell bubble sort.

References

Levin, Michael. “What do algorithms want? A new paper on he emergence of surprising behavior in the most unexpected places.” December 17, 2023. https://thoughtforms.life/what-do-algorithms-want-a-new-paper-on-the-emergence-of-surprising-behavior-in-the-most-unexpected-places/.

Levin, Michael. “Technological Approach to Mind Everywhere: An Experimentally-Grounded Framework for Understanding Diverse Bodies and Minds.” March 23, 2022. https://www.frontiersin.org/journals/systems-neuroscience/articles/10.3389/fnsys.2022.768201/.