Are humans computable?

I picked up Read Monatgue's book on decision making - Why Choose This Book?: How We Make Decisions, this evening at Barne's and Noble and read the epilogue with the provacative title: Are Humans Computable? In this chapter, Montague puts forward the argument that protein-protein interactions are not computable and hence neither is the brain or physics for that matter. He argues that proteins and worldly stuff have physical properties that are not computable but can be strung together algorithmically to achieve an end, such as the brain. As an example, he suggests that writing down the equations that govern a nuclear reactor do not suddenly create energy because the equations lack the "physical properties" necessary for a chain reaction. His final point is that our intuitions are based on a brain that is only designed to survive and reproduce and thus physics is ineluctably intertwined with psychology. He proposes that the next frontier is to incorporate the limitations of human perception into new physical theories.

I have been reading and thinking about the theory of computation lately. I have a host of incomplete and inchoate ideas on the topic that are not ready for prime time but after reading Montague's chapter I thought it would be useful to put some things down before I forget them. Montague has touched on some interesting and deep questions but I believe his particular point of view is flawed. He incorrectly conflates intractability with uncomputability and an algorithm with a computation. This post will only touch briefly on the very many issues related to this topic.

On protein-protein interactions, Montague writes that the totality of possible interactions is unimaginably large and thus could never fit on a realizable computer. He equates this with being uncomputable. Protein-protein interactions may not be computable but not because it can't fit on a computer. A problem is deemed uncomputable or undecidable if a computer (i.e. Turing machine) cannot solve (decide) it. This means that the problem cannot be solved by any algorithm. Perhaps Montague knows this but his editor forced him to tone down the technical details. The most famous undecidable problem is the halting problem, which says that there is no algorithm that can tell if a computation will ever stop. Hilbert's tenth problem on the solvability of diophantine equations with integers is also undecidable. It is not known if protein-protein interactions and by implication all of physics is decidable but almost everyone in physics and applied math believes it is so, whether they know this or not. One notable exception is Roger Penrose who believe that quantum gravity is uncomputable, but that is another story for another post.

The question is not as trivial as it sounds. Kurt Godel, Alonzo Church, Alan Turing, and many other twentieth century mathematicians established the criteria for computability and I hope to get to their ideas in more depth in future posts. However, for now in a nutshell, the question of computability comes down to the cardinality of the set you are trying to compute. If the set of possible outcomes of a problem is countable, then the problem is computable. If it is not countable, then it is not. Now to physics: If we believed that space-time were a true continuum (i.e. described by real numbers) then the set of all possible configurations of two proteins would be uncountable and Montague would be correct that the dynamics are uncomputable.

However, there are two very plausible responses to this problem. The first is that although real numbers are uncomputable, they can be approximated arbitrarily closely by countable rational numbers. This is the foundation of numerical analysis, which shows that any continuous dynamics can be approximated arbitrarily well with a discretized system. That's how we do numerical simulations for weather prediction, airflow over a an airplane wing, and even protein-protein interactions. The reason that numerical simulations work is that there is an underlying smoothness to the dynamics so we can approximate it by a finite set of points. In essence, we can predict what will happen next for short enough times and distances. Now, this need not be true. It could be that space-time is chaotic at small scales so that no discretization can approximate it. This is proposed in theories of quantum gravity. However, even if that were the case there is probably some averaging over larger scales that effectively smooths the underlying turbulence, (think the uncertainty principle), to make physics effectively computable and that is what we deal with on a day to day basis.

The second way to argue for the computability of the universe is that the entropy of the observable universe is finite. Entropy is basically the logarithm of the number of microstates. Thus if entropy is finite then the number of possible configurations of the universe is countable (actually finite) so again physics is computable. Why is the entropy of the universe finite? Again, think quantum mechanics. If space-time is quantized then there will be a smallest scale, namely the Planck length which is about 10^-35 metres.

However, Montague does have a point that a simulation of the interactions of two or more proteins could be intractable in that it would take an immense amount of memory or time to do a computation. The field of algorithmic complexity examines questions of intractability of which the most famous problem is whether or not P = NP. I don't have time to go into that one but I hope to post more on that later as well. So, while we may never be able to simulate the brain, that doesn't mean the brain is not computable, it's just intractable. However, intractability doesn't imply that we couldn't build an artificial brain.

I think I'll save my comments on Montague's other points in a future post.