>>17
It's ok as long as the lisp program always happens to terminate within a reasonable amount of time. This wont work if the lisp program has an infinite loop in it of course. It is unfortunate that this cannot be determined in advance, as it will cripple the compilation process, but it's ok. When running a binary sequence, its execution can be terminated if it reaches a certain timeout, which can be determined using the parameters of the score method. There would be a problem if every candidate exhausted the time out, but in that case, all you have to do is double the time out and run them all again. If at least one of them terminates within a finite amount of time on all inputs, it will be found eventually, and it wouldn't take many trials to rule out ones that take so much longer that they could never obtain a comparable score.
>>18
No, I don't think I can solve the halting problem. It can be solved for a variety of classes of programs, but to do it for all would lead to a contradiction. I am merely enumerating through all possible 2^N programs that can exist in N bits of memory, and running them on all possible 2^M inputs, that can exist in M bits of memory. It's quite simple you know.