How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?
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.