On a meta-note: I deeply enjoy that linking to Wikipedia articles is part of HN culture. If that which is timely cannot be timeless, then it is of supreme importance that what is News to us, individually, consists of more than what is New at the time of posting.
It's unclear what this has to do with A.I. Even humans are limited by the halting problem or other undecidable questions.
So why is this called a "theorem"? There is yet no proof that there are classes of problems inherently better solvable by the human mind. Or otherwise, that the human is something extra, computationally-wise, than a Turing machine.
I think the point is that, for some problems, no computation can perform better than human beings. A strong AI would perform equally as well as humans on these problems, but not better.
Of course, a "strong AI" in this usage would probably have to not only be computationally equivalent to the human mind, but also be provided with the same insanely complex and chaotic input that the human mind operates on.
To truly mimic human "creativity," this strong AI would probably need all the qualitative experience and memories that human beings have. It would probably need to undergo development in a dynamic social environment, or at least have the memory of doing so.
It doesn't seem like this is really an AI vs. Humans issue. Rather, it's saying, regardless if you have some optimal algorithm X for a class of "Full Employment" problems, it is always possible to have an algorithm that performs better for a specific case at the cost of worse performance for other cases.
It states that some problems will never have a perfect solution. It would be possible, I guess, for a strong AI to pump out stronger and stronger AI, so that humans will be unlikely to solve any problem before the stronger and stronger AI solve it.
Until that happens, it will always be possible to write a better space-optimizing compiler. Afterwards, it will still be possible, but the strong AI will beat you to the punch.
The trick is that perfection is usually overrated. Just like human experts, you can be the best at what you do, but you don't need to be the best ever (especially considering future experts).
That's also the key difference between science and engineering. In engineering, you need a good-enough solution, but you are not so concerned with proving that there is possible better implementation.
I agree, but the wording is poor. "no algorithm can optimally perform a particular task done by some class of professionals" implies that general intelligence is not an algorithm.
