Any result which predicts that human intelligence cannot exist.. has to have an error somewhere. Perhaps the error here is in assuming that a learning algorithm able to fit any function in polynomial time is needed in the first place.
People are too ready to leap at results that say, "Well, machines can never do X, and I can do X, therefore human-level AI is impossible."
In general, my counter to that would be "you probably can't do X either". It's just that you can do it well enough. You don't encounter the weird cases where your ability fails. But if that's allowed as an argument, then of course machines are more powerful too. I can absolutely solve the halting problem if "solve" can be interpreted as "almost always come up with the correct answer for the kinds of problems people encounter in the real world".
Also, don't forget what Terry Pratchett said, about how thousand-to-one odds crop up one time out of ten. The problems with AI in the past started when people tried to attempt to solve anything beyond the trivial, toy-problems they could demonstrate were solvable "in the lab". Like SHRDLU, which solved blocks world, but could not really scale. The same goes with machine learning today: some problems are solvable in restricted settings, or in a lab environment, under controlled conditions and with safe assumptions etc, but once you try to do the same thing in the wild...
You can even look at the big success of Deep nets for examples of that: image processing and speech recognition. Whereas it's possible to get really good results in both fields, image processing still relies very much on having good quality images to work with, and speech recognition is really crap if you have a bit of an accent, or a speech impediment etc. (at least that's what I gather- these are not my specialties).
Dana Angluin, Inductive inference of formal languages from positive data. [http://www-personal.umich.edu/~yinw/papers/Angluin80.pdf]
Dana Angluin, Learning regular sets from queries and counterexamples. [https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape...]
Mark E. Gold, Complexity of automaton identification from given data. [http://sebastian.doc.gold.ac.uk/papers/Language_Learning/gol...]
Mark E. Gold, Language Identification in the Limit.[http://web.mit.edu/6.863/www/spring2010/readings/gold67limit...]
Pitt, L., & Pitt, L. (1989). Inductive Inference, DFAs and Computational Complexity. 2ND INT. WORKSHOP ON ANALOGICAL AND INDUCTIVE INFERENCE (AII, 18--44. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.187....
Leonard Pitt & Manfred K. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86....]
Also see below for a gentle introduction to PAC-Learning, which actually allows for learning several concepts in restricted (but non-trivial) settings:
http://web.cs.iastate.edu/~honavar/pac.pdf
There is a lot more bibliography on both Inductive Inference tractability and PAC-Learnability. You'll have to follow the trail of references :)
Yes, it's entirely possible that we have missed something really important and when we figure that thing out we'll end up with a completely different Theory of Computation than we have now, and that may allow us to progress in learning concept classes that, today, are not learnable. That however, would be a revolution on par with Einstein's in physics.
Another thing that might save our collective ass, in terms of learnability, is that many of those results are assuming that P != NP. If that turns to be wrong, then those results will be off.
However, all this is very unlikely and in any case a) we can hardly expect such a profound re-interpretation of all that we know to happen within the next couple of generations and b) even if it does it remains the case that at this point in time everything we know suggests that there are some concept classes that we can simply not learn efficiently, at least not with computers.
Edit: what I'm really trying to say is that we may not understand human minds, but we're talking about computers here, so basically I agree with what you say, but with an added flourish :)
See deong's comment below. We may not understand how our minds work, but we do understand how computers work and that's where the learnability results come in: because they pertain to computers, not human minds.
Also, it may be that we don't need to learn every single thing we know. See Chomsky's Universal Grammar, etc.
I've been looking for work in this area without much success since publication is dominated by the opposite movement. I'd be grateful for any references you can dig up.
Even worse, we have some strong theoretical results suggesting that none of the techniques we have developed so far can ever lead to AGI, and that refers very much to machine learning primarily.
I'm talking about the work that was done on inductive inference, and then PAC-learning, in decades past (starting in the 1960's). There are many negative results and very few positive ones.
I wouldn't say I've reviewed the bibliography extensively (it's a huge area spanning a couple of fields), but from the little I've read I'm getting the feeling that, if you want to be able to learn any function in polynomial time, with a polynomial number of training examples, and with arbitrary error, you're basically stuck with the easiest classes of concept to learn. And if you want to learn specific distributions or representations (like DFAs or PCFGs) then you can just forget about it.
Which reminds me of something that Andrew Ng has said, about how recent results in machine learning and deep learning only reached the "low hanging fruit" and further progress is going to be much harder. No references to all this- I'll dig 'em up if required.