# Synthesizing Algorithms

Want an algorithm?

No need to program.

Just give a few keywords — elements the algorithm should contain:

0 10 i j for for ifless swap

(We’re searching for some simple number sort algorithm here.) We want to sort 10 items, so 0 and 10 will probably have to show up in the algorithm which is why we list them. We also expect 2 variables (i, j), 2 nested for loops, a comparison and a swap.

Note we don’t say what’s to be compared and what’s to be swapped, and also from where to where the loops range. That is all for the computer to figure out.

Then we finally define what task is to be accomplished so there can be validation:

..and just run our synthesizer which will try anything under the sun that matches our criteria above.

After a number of computation rounds, a result will come up, like this one that is actually machine-made:

i = 0
j = 0
for i = i, 10-1 do
for j = 0, i-1 do
if get(i) < get(j) then
swap(i, j)
end
end
end

It’s Lua code invented by machine. And it works.

(Technical note: I’m using Lua embedded in JavaX which is based on Java.)

Funny story: I was expecting some variation of “Bubblesort” to come out of this, but the computer did something else — which turns out to work perfectly.

To run a simpler example yourself, run this file: tinybrain.de/x30.jar and enter the number “1003166”. Sources: tinybrain.de/1003166

Let’s make a universe of these programs.

Slides

Stefan believes in a Good Future and making robots. More on: http://ai1.lol

## More from Stefan Reich

Stefan believes in a Good Future and making robots. More on: http://ai1.lol