In 1936, Alan Turing invented the Turing machine, an abstract model of a computing machine that turned out to be universal enough to encompass all methods of computation we know today. On a high level, a Turing machine is a computer with unlimited memory, that starts with some data in the memory (i.e. the input) and follows a pre-defined, finite set of instructions (i.e. the program) to manipulate and perform computations on the data. It can, of course, write arbitrary data (such as the result of some computation) in its infinite memory, and there is no time limit on how long the the machine can run.

It is widely believed that this relatively simple model of computation is universal, which means that anything that can be computed by an algorithm (a step-by-step procedure) can be computed by a Turing machine. This is known as the Church–Turing thesis, and as it is not a theorem or law, we do not know with full certainty if it is true (in fact, sometimes it is called the Church–Turing conjecture to make this point explicitly clear). What’s more remarkable is that this formal formulation of an abstract computer led to the discovery of a slew of problems that are not computable by such machines, as universal as they are. This set of problems are called non-Turing computable, and actually contains almost all problems, in the grand scheme of things. The most iconic of such a problem, and the first to be proven to be so, is the halting problem: given an arbitrary program, determine, when run, whether this program will stop after some time, or run forever.

So how do our brains compare to such a universal model of computation? This is a question that’s received very little formal research, which I think is in large part due to the fact that we don’t have a good understanding of how our brains work¹. Nevertheless, it is still very interesting to think about.

One thing we will realize is that in practice, humans are very limited. Turing machines have unlimited memory and time, and still they cannot solve many problems! To make the comparison more fair, I’ll take a hypothetical human instead, one that has the aid of an unlimited memory (in the form of pen and paper perhaps), and one that can live forever². It’s easy to see that such an enhanced human brain is at least as powerful as a Turing machine, since we have the capacity to follow algorithms. But is that all? Can it somehow surpass Turing machines, and be able to solve non-Turing computable problems?

Many theoretical computer scientists are strict materialists, and believe in the physical Church-Turing thesis. This is a related conjecture to the Church-Turing thesis that connects it to physics and reality. It simply states that physical computability is equivalent to Turing computability, or in other words, physical computers (i.e. computers that can exist in our physical reality) can at best match the capabilities of the abstract Turing machine, and not surpass it. If you subscribe to this view, then the answer to the above question is no: we (even the enhanced version) are no more powerful than a Turing machine. As we are physical beings made of atoms, our brains can only solve physically computable problems, same as a Turing machine³.

On the other hand, if you do not believe in the physical Church-Turing thesis, then there is a chance that our brains can surpass Turing machines. The ability to solve non-Turing computable problem is generally called hypercomputation, and the interesting question to ask here is how can our brains do this. Almost all theoretically known models of hypercomputation rely on the general idea of “performing an infinite number of actions in a finite amount of time” (which makes the halting problem trivially solvable). These models are mostly thought experiments because they cannot be practically realized in any way⁴. It seems unlikely that our brains are capable of doing this, but if not, then our brains must be relying on some other yet-unknown method to perform hypercomputation. One potential candidate is something related to the quantum nature of our brains. This implies that there is some yet-to-be-discovered fundamental nature of reality that is different from everything else we know, because as far as we know, quantum mechanics, probabilistic as they may be, are still Turing computable. Even quantum computers cannot compute anything beyond what a classical Turing machine can (however they are faster at certain computations).

In the end, even though we don’t know the answer to the question, it seems that either answer yields remarkable results. A negative answer means that there are many problems that we simply cannot solve, in a physically-forbidden way⁵, even if we were immortal and had unlimited pen and paper for aid. And an affirmative answer means that we are truly special in some way, that transcends the rest of our physical reality. I am usually already attracted to unsolved problems or questions without a definitive answer, but this type question, where all possible results are profound in their unique ways, are undoubtedly my favorites.