Sorry multiple threads will not get you around the halting problem. The brute-force genetic algorithm you describe also suffers from the halting problem. Just look at the algorithm as a whole. Say you are searching for a program P and you have some criteria for recognizing it, including a maximum run-time. There is no way to know if the genetic algorithm will ever find P or will itself just run indefinitely.
In general, you will not be able to easily find P using a genetic algorithm (which amounts to a random walk through the space of all programs) even with many threads. The problem is that the algorithm is exponential in the length of P. It only works if you only consider a very limited set of possible programs. E.g. very short programs or programs which are only slight variations on a known program.
In general, you will not be able to easily find P using a genetic algorithm (which amounts to a random walk through the space of all programs) even with many threads. The problem is that the algorithm is exponential in the length of P. It only works if you only consider a very limited set of possible programs. E.g. very short programs or programs which are only slight variations on a known program.