Thinking (WIP)...

AGI may be achievable (or steps-toward) via a combination of mini-programs run on a simple virtual machine combined with efficient input signal signatures. Signals are routed to specific program sets that execute on a virtual machine (VM).

Brute-force Reductionism

Brute-force reductionism: reduce the search space by breaking down input/output matrices into subsets of problems.

In this example: if an unfilled block is surrounded by filled blocks above, below, left, and right, then set the unfilled block color to yellow. See ARC prize puzzle 0062c1b

To break down the problem for brute-force reductionism, the input X will be used in a loop against each y value. X:

[
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0],
]
    

where 1 represents green and 0 unfilled.

The accompanying y output:

[
    [0, 1, 0],
    [1, 2, 1],
    [0, 1, 0],
]
    

where the 2 represents orange.

Both X and y are then flattened to 1-dimension like so:

X = [0, 1, 0, 1, 0, 1, 0, 1, 0]
y = [0, 1, 0, 1, 2, 1, 0, 1, 0]
    

X is then fed to a program generator that finds operations to calculate y[n]. Let's walk through this:

With each step, 0 through 8, a set of virtual machine operations will be generated for X to y[n]. Once completed, we now have a set of programs that can take input X and solve each y[n] individually. You can think of this programatically like this (Python):

    X = [...]
    y = [...]
    programs = []
    for y_item in y:
        program = bruteforce(x=x, y=[y_item])
        programs.append(program)
    

The programs list is simply a set of opcodes that the virtual machine can run.

       programs[0] solves for y[0]
       programs[1] solves for y[1]
        ... and so on ...
    

Virtual Machine Operations

The idea behind the virtual machine is very basic: it knows a predefined set of operations it can execute against X to generate an output for y. For example:

    class Ops(Enum):
        NEXT = auto()  # move to next x index
        PREV = auto()  # move to prev x index
        INC = auto()  # increment current x
        DEC = auto()  # decrement current x
        SWAP = auto()  # swap x[index1] with x[index2]
        INSERT_LEFT = auto()  # insert 0 to x and 0 index, growing the list
        INSERT_RIGHT = auto()  # append 0 to x, extending the list
        SHRINK_LEFT = auto()  # delete first value of x (e.g. x = x[1:])
        SHRINK_RIGHT = auto()  # delete last value of x (e.g. x.pop())
        DELETE = auto()  # delete at current index
        DELETE_ADJACENT = auto()  # delete all adjacent of value at current index
        SUM_SET = auto()  # set all to sum of x
        SUM_ADJACENT = auto()  # set all adjacent to cur x to sum of adjacent
        JUMP_LT = auto()
        JUMP_GT = auto()
        PUSH = auto()
        POP = auto()
        ...
    

Early Observations

I have been testing against the ARC-AGI dataset found here.

Notable observations:

• The number of programs generated for the entire dataset averaged around ~130. Meaning, only 130 programs were needed to solve all of the problems. Note that these are individual programs which are grouped, used in different configurations (ordering and length) depending on the problem.
• The average brute-force time per X -> y[n] is 0.6 seconds.
• The entire dataset was brute-forced in under 12 minutes on single-core CPU only. Using multiprocessing can greatly reduce this time.
• Attempting to brute-force X against the entirety of y (not y[n] subset), as expected, took forever (never finished in a reasonable time or ever in some cases).

More to Come

...