This is almost comical :p The brain is not a turing machine. You can't make these kind of analysis because the brain isn't just a huge von neumann computer.
It is hard to prove a negative (it is easier to prove the brain is something else). As much as Turing completeness seems to emerge relatively easy, given how the analog complexity of our nervous system contrasts with the deterministic simplicity of digital computers, it is a bit naive to make parallels about how they work unless you are making some kind of metaphor.
It is necessarily constrained by asymptotic computational complexity. With or without the memory bottleneck implied by the Von Neumann architecture. That it is a turing machine is not merely a pedantic fact. It has both implications and relevance here. At best a different architecture would exploit more concurrency. I don't think it does though; Language processing is extremely recursive. Noam Chomsky suspects our brains have an adaptation specifically for it. Nim Chimpsky implies he's right. I suspect this adaptation has all sorts of parallels with digital turing machines.
That... is a pretty interesting thought. I'm gonna go into hand wavy mode here. Noam Chomsky also argued [0] that the "language faculty" evolved as a spandrel. Meaning loosely (teleologically) that it wasn't it's own "motivation". This implies that the "language module" [1] may not exist as a distinct structure. Noam Chomsky's deviation from canonical terminology is revealing. He's a very meticulous person; It's not an accident. He specifically disavows a full theory of it's evolution. Other's assert that the idiosyncratic structure of the world's various languages is evidence against this. That the nature of grammar is too complex to have piggybacked on another adaptation. As an accident. It must have been naturally selected for over time. Maybe it was both?
The brain had 4 seconds of echoic memory that it was already pattern matching against; For various "reasons" in the environment. Using this neurology, without further adaptation, we could have learned to identify generic structures in sounds. Languages are just trees encoded as sequences. For example, "the small brown fox ate the white rabbit" is the tree (ate (the (fox small brown)) (the (rabbit white))). The structural recognizer produces a simple hash-like value corresponding to a generic structure. The brain learns to calculate it from the meaning of words. It's the introspective association of these structures with brain states that's ultimately novel. Sequential processing and the state it requires evolved for other reasons. We can use this loose bundle of state for the individual "chunks" we hear. All we needed was the ability to manipulate and maintain recursively structured state. This is just a new meta-state for the generic tree superimposed on these "chunks". Notably, Nim Chimpsky can sign three word sentences. Nim apparently understands the tree (relationship this that). Though he can only form very simple structures; He seems to be utilizing his self awareness. Perhaps the spandrel is piggybacking on the ego. This works great for (eat Nim Banana) but ventures near deranged ambitions like (eat Nim Nim). His environment punishes anything exceeding basic executive function. He is actually extremely conscious when not compared to humans.
The first brains (Planarians) were sort of like jellyfish "brains". They were hardly more than nervous systems and produced no internally sequential cognition. Neural connections formed directed acyclic graphs. They computed referentially transparent functions over sensory input. Their construction was similar to combinational logic circuits. Concurrency was expressed in parallel structure's and not execution steps. Aside from neuroplasticity these brains didn't maintain state. In order for the brain to maintain state it needs a neurological cycle. Evolving such a thing is a very risky endeavor. Simple cyclical structures are liable to produce dangerous feedback; Like Nim's ambitions above. Every cycle takes a developmental and cognitive toll on the brain. It has to learn how to cope with each of them. New cycles must overcome this cost, by producing novel and sufficiently rewarding behavior, otherwise they die.
A stateless brain has a significant limitation. It can easily become stuck. Sensation (input) causes action (output) which reproduces identical sensation. Fixed points persist indefinitely without external intervention. This creates selective pressures for the adaptation of state cycles. The brain can instrument the body for signals like hunger and fatigue. This gives the brain more "external" interventions. But this won't relieve much pressure. The body's state is just the body's state. It isn't a general indication of when you ought to exit a fixed point. The brain can still become stuck and it's terribly expensive. Behaviors, regardless of potential reward, cannot risk entering a fixed point. Lets say a coconut might fall out a tree if you kick it. You can't try it or you'll just stand around kicking the same tree forever. State and sequential processing solve this problem. As an intermediate solution, behavior could be randomized using a noisy feedback loop. Carefully avoiding the brain's distaste for cycles it could then go on to become proper state. This can produce emotional states like boredom. Also basic executive functions like: kick it if you didn't just kick it. It takes a long time to evolve something as self directed as Nim. Then just a bit longer for Eve to bite the apple. Once invented, language would have imposed tremendous evolutionary pressure on the development of introspective state with increasingly sophisticated structure. Simple operational languages co-evolved into the sophisticated cultural languages we know today. This could explain most of what distinguishes our variety of intelligence from the other animal's.
The brain would need to leverage quantum effects to achieve hyper-computation. Otherwise it follows the same rules as other turing machines. Here's a quote from Scott Arronson:
"Indeed, I see no evidence, from neuroscience or any other field, that the cognitive information processing done by the brain is anything but classical." -- http://www.scottaaronson.com/blog/?p=1951
Notably this is from a post discussing quantum effects as a potential explanation for consciousness. There's still no evidence for that either. Also, if true, it would only sit atop a classical cognitive process which acted as a turing machine. That or a horde of tiny turing machines.
