Wim Hordijk is a computer scientist working in the areas of computational biology and origin of life. He was a graduate fellow at the Santa Fe Institute for several years, and has worked on many research and computing projects all over the world since then. He currently works as an independent scientist, based in Lausanne, Switzerland.

In a recent paper in this journal, a claim is made that the mind is not algorithmic. The supporting argument for this claim is that humans frequently solve certain problems which can supposedly not be solved by a computer. However, this argument is based on a fundamental misunderstanding of what it means to solve a problem. Here, I will argue that the provided argument for the claim that the mind is not algorithmic confuses two different meanings of the phrase “to solve a problem”: its formal meaning and its colloquial meaning. As a result, the argument is not logically consistent, and thus does not support the original claim.

In a recent paper in this journal, a claim is made that the mind is not algorithmic (Zia

To explain the difference between the two meanings of the phrase “to solve a problem”, it is necessary to explain its formal meaning in a concise and clear way. Below, I will provide a non-technical explanation of this formal meaning. First, the difference between “easy” problems and “hard” problems in computer science is explained. Then the notion of approximate solutions is addressed, which relates to the alternative, or colloquial meaning and the way humans tend to solve problems. Finally, the difference between the two meanings is highlighted. With that in place, I will argue that the original argument provided by Zia

In theoretical computer science, a distinction is made between “easy” problems and “hard” problems. An example of an easy problem is finding the shortest path between two points in a road network. Every time you turn on the navigation system of your car and type in a destination, it invokes an

The shortest path algorithm takes as input a given road network, a starting point and a destination, and computes the shortest route between these two points given the provided road network. The nice thing about this particular algorithm is that it can be shown mathematically that it is an ^{2} steps to return the answer. This (worst-case) running time is written as ^{2}^{2} steps.

Now, an algorithm that has a worst-case running time that is ^{2}^{x})^{ }. Finally, a given problem is considered “easy” if an algorithm can be constructed for it that will (provably) always return the most optimal solution and that has a worst-case running time that is polynomial in the size of the input. The “easy” problems together make up what is known as problem class

Unfortunately, not all problems encountered in real life are easy. Consider the following extension of the shortest path problem. Instead of wanting to go from point A to B in the shortest possible way, imagine you need to visit several cities and then return to your starting place, but in such a way that the total travel distance is as short as possible. So, the question is in which order to visit the given cities so that the total length of the tour is minimal. This problem is known as the

If there are ^{n})

To appreciate what this means, assume we have 10 cities to visit. With an exponential running time, we can expect the optimal answer in, roughly, 2^{10}=1024 steps. That is actually not bad. However, now imagine there are 100 cities. That means the algorithm needs on the order of 2^{100}≈1.27x10^{30} steps. Considering that the age of the universe is estimated to be about 4.4x10^{17} seconds, even if we could perform thousands of computing steps in one second, the lifetime of the universe would still be several orders of magnitude too short to wait for the optimal answer! Given that modern-day networks (such as mobile communication networks or high-performance computer chips) easily have thousands of nodes, there is no hope to find the most optimal solution for TSP or equivalently hard problems on such networks.

Problems for which the only known algorithms to always find the most optimal solution all have a worst-case running time that is exponential in the size of the input, are (appropriately) called

Note that it is not only the fact that there are an exponential number of potential solutions that make these problems hard. For example, in principle there could also be an exponential number of possible paths between any two given points in a road network. However, for the shortest path problem it is possible to construct an efficient algorithm to find the optimal solution. For the TSP problem this is not possible, or at least nobody has been able to find one so far (although many very smart computer scientists and mathematicians have tried).

As a technical aside, theoretically it is not known whether it is, in principle, impossible to construct an efficient (polynomial-time) algorithm for NP-complete problems. In other words, it is still an open problem in theoretical computer science whether

Unfortunately, it turns out that there are many real-world optimization problems that are NP-complete. Such problems occur for example in engineering, economics, logistics, communication networks, and also in science, to name just a few. However, for many of these problems it is not always necessary to find the

This happens in nature as well. The human brain continuously comes up with approximate solutions to the problems we face in daily life. We may not always be able to calculate the absolute shortest path from A to B, but as long as we get where we want to be without too much delay, things are fine. Evolution can also be viewed as an optimization process, generating solutions (different species) to the problem of survival and reproduction, which is a basic requirement for all of life. However, most of these solutions are not perfect or optimal. But in evolution, any trait (whether physiological or behavioral) that provides an increase in an organism's chances for survival and reproduction, will have a selective advantage.

Obviously computers can also be used to find approximate solutions to hard problems. Even if a problem is intractable, or NP-complete, it is often still possible to construct efficient algorithms (with a polynomial worst-case running time) that return approximate solutions which, although not necessarily the most optimal, are usually “good enough” for practical purposes. Neural networks and genetic algorithms are examples of such approximation algorithms. A neural network (Lippmann, 1987; Haykin, 1999) is a computer algorithm that mimics the workings of the brain, and that can be trained to, for example, recognize patterns such as your fingerprints. Just as our own brain, it may not always perform flawlessly, but it can achieve a high level of accuracy which, for most practical applications, is acceptable. Similarly, a genetic algorithm (Holland, 1975; Goldberg, 1989, Mitchell, 1996) tries to find approximate solutions to difficult problems by mimicking an evolutionary process, literally evolving better and better solutions over time. In practice, these approximate solutions are often adequate enough.

So what does it mean to solve a problem? As the above explanation of hard problems and approximate solutions already indicates, there are actually two meanings of the phrase “to solve a problem”. The first, a formal definition from theoretical computer science, is “to find the

The second, colloquial meaning is “to find an

The argument used by Zia

But then they go on to say: “Yet people solve such problems all the time. This is, we claim, a powerful line of evidence that the human mind is not algorithmic.” (Zia

In short, the argument of Zia

Such a misunderstanding when there are multiple meanings of a particular phrase, a formal one and a colloquial one, unfortunately happens more often (see e.g. Szathmáry (2013) for an example in biochemistry). Of course this does not necessarily mean that the mind

Note that for a very large value of

I would like to thank Stuart Kauffman for many inspiring discussions, even if we do not always agree. Thanks also go to my colleague Mike Steel for helpful comments on an earlier version of this note.