Is the human brain a computer (i.e. a Turing Machine)?
That's the question we looked at in our final Logic lecture this year. I'm inclined to say "yes, it must be", because I can understand (roughly) how computers can work things out, but I can't imagine how a non-computational process could do the same. That might just be ignorance on my part - if anyone else out there has an explanation of non-computational 'thinking', do tell me about it!
Anyway, our logic lecture was about the implications of the Halting Theorem, that is, the proven fact that no Turing Machine can possibly solve the Halting problem. In brief, the Halting problem is: given any Turing Machine's instruction table and initial input, tell whether that machine will eventually halt, or whether it will run forever (i.e. get stuck in an infinite loop). No computer can solve that for the general case (though of course they can solve specific instances).
Yet there seems no reason to doubt that the human mind is capable of solving the Halting problem. It seems possible that there could be some human uber-Einstein such that you could give him any Turing Machine whatsoever, and he could (eventually) work out whether it would halt on a given input. (Of course, if it's an excessively complicated program, he might require a million years to solve it, but if we allow for such idealised conditions, there seems no reason to think that anything is in principle impossible for our uber-Einstein.)
So, since we know that some mathematic problems cannot be solved computationally, yet there seems no reason to think that they cannot be solved by humans, it would seem to follow that the human mind must not be a computer. At least, that's the argument our lecturer gave, and apparently it's quite a popular one, made most recently by Roger Penrose (though I haven't read him yet).
I don't think it's a very good argument though. It strikes me as entirely question-begging. I would dispute that there is "no reason" to doubt that humans can solve any mathematical problem. I think the Halting Theorem provides us with good reason to doubt it. If something cannot possibly be achieved (even in principle) by computational processes, then that provides us with reason to think that humans cannot do it either. After all, there seems no reason to doubt that the human brain could be simulated by a computer! (I guess it's the old case of "one man's modus ponens is another man's modus tollens".)
I did suggest that counterargument to my lecturer, and he wasn't convinced. He assumed the anti-computationalists had the more intuitive position, so the "burden of proof" rested on us. I disagree, of course. What we have here is an inconsistent triad, and all that is agreed upon is the first claim: that a Turing Machine cannot solve the Halting problem. Of the other two, either humans also cannot solve it, or the human brain is not a Turing Machine; but I don't think that either of these positions is more intuitive than (or priveleged above) the other. So I don't think you can use either to argue against the other - not without begging the question.
But could it be computers, plural?
Here's the really interesting part. Even if we accept that the Halting Problem shows that the human brain is not a (individual) Turing Machine, that still leaves upon the possibility that it could be several Turing Machines (in sequence). Indeed, this is the position Turing himself advocated.
Mathematicians cast out for new methods of proof when necessary. Perhaps a Turing Machine could do the same thing? That is, faced by a problem it cannot solve, it might rewrite its own code to become a new Turing Machine. Such a sequence of TMs could (in principle) solve the Halting problem, so long as the sequence could not be generated by a single TM (since otherwise that single TM could solve the Halting problem itself, and we know no single TM can do that). In other words, the sequence must be uncomputable; the transformation from one TM into another must be partly random.
So we can overcome the inconsistent triad by suggesting that the human mind could be an uncomputable sequence of Turing Machines. This would seem to require that the world be indeterministic on some fundamental level (in order to yield the 'randomness' necessary to ensure that the sequence is uncomputable). Given quantum physics, this is likely the case. But it does seem an interesting consequence of this view that if determinism is true, then human mathematicians can only ever hope to solve that which is computable. If the world is indeterministic, however, we may be able to transcend such constraints.