Comment by nwah1
10 years ago
If we take the simple case of genetic algorithms, we already know that it is possible to brute-force the problem of programming.
The halting problem doesn't really matter that much in this context. Just spawn up a bunch of threads that churn away at the problem, using random mutations, and any that go on too long can just be considered flawed, regardless of whether they have any redeeming qualities.
Then you select the winners, based on the selection criteria, and churn away on some more mutations of those new variants.
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.