Genetic Algorithm + Brainfsck

First: Genetic Algorithms. A GA is a program designed to find the solution to a problem via iterative searching - that is, the algorithm itself searches for a solution to a problem. GAs in particular use biologically-inspired methods to perform the search.

The analogy with biological systems is like so: a GA spawns multiple search 'organisms,' which 'live' in the algorithmic environment. With each generation, each organism is tested against a 'fitness' function, which determines how well the organism solves the problem we're looking for a solution for. Only the fittest of each generation survive, passing on their genes (parameters) to the next generation. Each of the survivors randomly selects a mate and mixes the genes (with some random mutation factors), with the expected outcome of iteratively evolving toward the best possible solution to the problem.

I've built a couple small GA systems in the past - nothing for anything in production, but mostly just to toy with - and I find them particularly interesting, especially given how very small changes in how the organisms select mates, mix genes, and mutate can result in large-scale changes in the search behavior.


Now the second part: Brainfsck (which is actually spelled with a 'u' instead of an 's', but I want to maintain some civility here) is a programming language in which there are only 8 legal characters - '>' '<' '+' '-' '.' ',' '[' and ']'. Each of these characters performs some function in the program, usually with regards to manipulating 8-bit memory locations called cells. Wikipedia has more information - but suffice it to say that Brainfsck has been proven to be Turing complete, which means it can be used to perform any computable function (provided it has infinite memory).


Here's how Genetic Algorithms and Brainfsck can come together: I mentioned earlier that GAs use digital organisms and 'genetic' parameters to evolve toward a solution. What if those parameters were snippets of Brainfsck programs, and the fitness function ran the Brainfsck programs to see what their output is, and check that output against an expected output? Wouldn't it, in theory, be possible to iteratively evolve toward the solution of any computation problem that way?

Just a random thought that's been plaguing me for the past couple of days. Don't think anything particularly interesting would come of this.