In the late eighties and early nineties, Roger Penrose in two books, presented an argument that the brain cannot be algorithmic and thus the AI program is doomed to failure. Unfortunately, he also proposed that a new theory of quantum gravity may be necessary to understand the brain and consciousness and so his ideas were largely ignored by the neuroscience community. However, I think his argument for the noncomputational aspect of brain function was actually well thought out and deserved more attention. I personally believe the argument is flawed but it does stir up some interesting questions.
Penrose's argument is essentially based on the theorems of Godel, Turing and Church. Godel showed that for any formal system, there will be statements that are true but not provable within that system. Hence, formal systems are incomplete in that there will always be undecidable statements. Turing then showed that for any computer (or any algorithmic system), there exist programs that we know and can prove will not stop but no computation on that computer can ever determine this fact. Penrose then argued that since we (at least Turing and Godel) can determine the truth of such undecidable statements, then we (they) could not be doing that computationally or algorithmically.
The implications are quite profound. It means more than just the futility of traditional AI. It also means the brain cannot even be simulated on a computer because any simulation on an algorithmic machine implies the outputs are also algorithmic. Pushing it further, if the brain is based on physical principles, then this implies that physics itself (or at least aspects of it) can't be simulated on a computer either. This is why Penrose was led to postulate that there must be some new physics out there that is beyond computation. The idea is really not that crazy if you think about it. However, it is definitely not air tight.
I think the hole in Penrose's argument is that he believes that we actually can circumvent Godel's theorem and decide undecidable problems. However, I don't think that this is necessarily true. We don't know what formal system our brain happens to be using so don't know which undecidable statements happen to be true but we can't prove. The ability to prove Godel's theorem and to decide truths for other formal systems that are not ours could be implemented computationally. So, the existence of Godel's and Turing's theorems does not necessarily imply that the brain is noncomputational.
Furthermore, it is doubtful that the formal system of our brains are even constant in time or conserved between individuals. More likely, our brain and hence formal system is constantly changing because of random environmental inputs. Thus, Penrose's argument for the futility of traditional AI may be correct. A truly human-like intelligent machine couldn't be built from a fixed formal system that is knowable. It may need to arise from a massively parallel learning system that constantly changes its axioms. Thus even if you could measure the formal system at some point in time, it would be changed before you could use this knowledge. This would be the equivalent of an uncertainty principle for the brain.
Penrose also rules out the role of randomness in breaking algorithmicity. He argues that randomness can be mimicked by an algorithmic pseudo-random number generator. I don't see why this is the case. Perhaps, true randomness is beyond computation. This then leads to the question of where randomness actually comes from. Perhaps it is a vestige of the initial conditions of the universe. And where did that come from? Well we may need a theory of quantum gravity to figure that one out. Hmm, maybe Penrose was right afterall:).