How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?

Question

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?

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.