I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as abstract syntax trees.

However, one of the functors is the while loop. Of course, in assesting a tree's fitness, I have to evaluate the program: but the halting problem is unsolvable. How can I tell if a given tree stops? Of course I can't, so what are some practicals ways to approach this problem?

Should I make my simple tree-language not turing complete? Or maybe give a timeout to each tree?


1 Answer 1


It is very unlikely indeed that finiteness is truly what you are looking for. Would you really be happy with a program that takes $10^{10^{40}}$ steps to complete?

If I am right, "non-haltingness" is not the real quality you are looking for. It is "halting within a reasonable time".

The best way to express this is not as a pure timeout, but by defining a measure of utility which declines with an increasing number of steps. That will give your evolutionary mechanism a steady "push" in the right direction. As for whether it is $1/n$, $1/\sqrt n$, $2^{-n/c}$, that is something you can decide.

Of course in practice a program that takes more than a certain number of steps is going to carry on going for ever. But you can encapsulate this intuition into the algorithm by saying that if, after $n$ steps, the overall utility has declined to a point when it is too low to be worth considering and it is never going to increase if you carry on stepping. Thus the timeout is still there, but as an implementation detail and not as a primary principle-in-itself.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.