Humans can't solve the halting problem either, there is no contradiction. The halting problem is a theoretical problem that needn't apply in real life. If you for example restrict your AI to be able to generate optimal assembly for all programs that don't require more than 100PB of source code to write down, the halting problem no longer applies (in fact you can now implement this AI using a regular expression).