Metabiology: how to randomly mutate an algorithm trying to ensure that the new version will be valid and will stop?

I'm trying to hack a simulation of evolution according to Gregory Chaitin's metabiology model.

Given an algorithm that returns an integer, i need to mutate it randomly trying to get another algorithm that is syntactically right and eventually stops. If the mutation is truly random is impossible to ensure that what you obtain is a valid algorithm that will stop.

My questions are:

• What is the best turing complete language to do this?
• Is there any technic from genetic-programming that already attacked this problem?

Thanks in advance

I was thinking in something like:

x <- x + 1
x <- x - 1
y <- x
if x != 0 开发者_开发知识库goto label

this is turing complete and is very easy to modify. What do you think?

If the mutation is truly random is impossible to ensure that what you obtain is a valid algorithm that will stop.

As Robert B pointed out, a set of Turing-complete functions will satisfy your first part but there is no solution for the problem where you allow the possibility of loops. However, if you remove loops as a possibility then you can generate an expression tree that can provide you with outputs every time you feed it some inputs. The expression tree has finite size and guaranteed termination, or to think of it in another way: to get an expression tree with infinite running time would require that the expression tree has infinite nodes (which would require you to have infinite RAM or disk).

There are strategies for pruning expression trees in order to provide minimal solutions to the problem and some of those strategies involve making the size of the tree part of the fitness function. In other words, when computing fitness, take into account the size of the expression tree: smaller solutions are preferred over larger solutions when everything else is equal (i.e. both solutions have the same accuracy).

LISP. Well, any homoiconic language. But LISP. Read Koza's books http://www.genetic-programming.com/

What you are looking for here is "Grammatical Evolution", that would be the application of Genetic Programming to evolving working computer programs. This is a good site: http://www.grammatical-evolution.com/. Also, you could look into evolution of more basic computing mechanisms like FPGA by typing "FPGA genetic programming" into Google.

Well, the first part of your question is about algorithms that are valid. If you define as many functions as you need to ensure Turing-completeness (for example, +, -, *, /, X, Y, Retval, loop, if) then you have satisfied the first part. I recommend using higher-level functions because there are certain structures which will keep evolving again and again, and you'll speed up evolution if you just put it in the list of functions to begin with. For example, loop can be decomposed into if and goto, but with loop you'll save valuable evolution energy, and also ensure validity.

However, your second part is about algorithms that eventually stop. This known to have no solution. One alternative is to set a limit to the number of instructions that a program can execute, and abort the program if it violates that restriction, giving it a high penalty. Or, if you have a terminal which the program needs to load with an answer (e.g. Retval), you can just halt the program and check that terminal.