Reductionism: to computer science from philosophy

A biologist and a mathematician walk together into their joint office to find the rubbish bin on top of the desk and on fire. The biologist rushes out, grabs a fire extinguisher, puts out the blaze, returns the bin to the floor and they both start their workday.

The next day, the same pair return to their office to find the rubbish bin in its correct place on the floor but again on fire. This time the mathematician springs to action. She takes the burning bin, puts it on the table, and starts her workday.

The biologist is confused.

Mathematician: “don’t worry, I’ve reduced the problem to a previously solved case.”

What’s the moral of the story? Clearly, it’s that reductionism is “[o]ne of the most used and abused terms in the philosophical lexicon.” At least it is abused enough for this sentiment to make the opening line of Ruse’s (2005) entry in the Oxford Companion to Philosophy.

All of this was not apparent to me.

I underestimated the extent of disagreement about the meaning of reductionism among people who are saying serious things. A disagreement that goes deeper than the opening joke or the distinction between ontological, epistemological, methodological, and theoretical reductionism. Given how much I’ve written about the relationship between reductive and effective theories, it seems important for me to sort out how people read ‘reductive’.

Let me paint the difference that I want to discuss in the broadest stroke with reference to the mind-body problem. Both of the examples I use are purely illustrative and I do not aim to endorse either. There is one sense in which reductionism uses reduce in the same way as ‘reduce, reuse, and recycle’: i.e. reduce = use less, eliminate. It is in this way that behaviourism is a reductive account of the mind, since it (aspires to) eliminate the need to refer to hidden mental, rather than just behavioural, states. There is a second sense in which reductionism uses reducere, or literally from Latin: to bring back. It is in this way that the mind can be reduced to the brain; i.e. discussions of the mind can be brought back to discussions of the brain, and the mind can be taken as fully dependent on the brain. I’ll expand more on this sense throughout the post.

In practice, the two senses above are often conflated and intertwined. For example, instead of saying that the mind is fully dependent on the brain, people will often say that the mind is nothing but the brain, or nothing over and above the brain. When doing this, they’re doing at least two different things. First, they’re claiming to have eliminated something. And second, conflating reduce and reducere. This observation of conflation is similar to my claim that Galileo conflated idealization and abstraction in his book-keeping analogy.

And just like with my distinction between idealization and abstraction, to avoid confusion, the two senses of reductionism should be kept conceptually separate. As before, I’ll make this clear by looking at how theoretical computer science handles reductions. A study in algorithmic philosophy!

In my typical arrogance, I will rename the reduce-concept as eliminativism. And based on its agreement with theoretical computer science, I will keep the reducere-concept as reductionism.

Reductions in theoretical computer science

Let us return to the opening joke and explain all the funny away: in what way did the mathematician use ‘reduce’? She certainly didn’t eliminate anything. Instead, what she did was transform the problem to show that it relates to something else that is already known. The joke was that this was clearly an equally difficult problem and nothing of use came from the transformation. The reason she was a mathematician — although computer scientists or programmers would have worked almost equivalently — was in part due to mathematics’ perceived detachment from reality, but more-so due to the fact that this reflects has mathematicians use the term ‘reduce’.

In theoretical computer science, a yes-no problem X is (many-one) reduced to a yes-no problem Y by reduction R if for every input x to X, the reduction produces an input y = R(x) to Y such that the answer to x in X is the same as the answer to y in Y for all possible x. We are usually interested in the case where the algorithm for R is particularly simple, such that if we used the reduction to solve our problem X, it would actually be the algorithm for Y that does the ‘heavy lifting’. In this way, for computer scientists, if X is reduced to Y then Y is the ‘harder’ problem.

From this perspective, the reduction was the easy task of lifting the bin onto the table.

Of course, we don’t have to limit ourselves to yes-no problems or many-one reductions. We could also consider general problems X and Y with an algorithm B for Y, and say that X is reduced to Y if we can solve X by doing some simple computations with occasional calls to B as a subroutine. This is a bit more obscure since on the surface it makes it a bit more difficult to spot the part of the computation due to the reduction and the part due to B. But the two notions are not fundamentally different.

Note that this notion of reduction did not make any claims about X or Y being more or less real than the other. Just as with the Church-Turing thesis, we can choose to make these claims in any direction that we want: idealist, physicalist, or cognitivist. But that discussion is for another post.

In not making claims about the real, the reductions of computer science could be interpreted as a precise statement of theoretical reductionism: given a physical theory X and Y, if all the phenomena of X can be expressed and explained by Y then X reduces to Y. In general, this means that we would expect Y to be ‘more complicated’ than X and even though X reduces to Y, Y can “do more” than X. So right there we’ve thrown out the reduce-concept and focused on just the reducere-concept. Nothing is being eliminated by this view of reductionism.

Reducing 3-SAT to SAT and SAT to 3-SAT

At least eliminativism is not an essential feature. To see this, let us consider a trivial reduction.

The boolean satisfiability problem (SAT) considers a domain of variables that can each be assigned as true or false and a particular problem instance is represented by a boolean expression that is built from (potentially repeated instances of the) variables, operators AND, OR, NOT, and parentheses. Given such a boolean expression, the answer to SAT is ‘yes’ if there exists some assignment of True/False to each of the variables such that the expression evaluates to True. The answer to SAT is ‘no’ if there does not exist any assignment of True/False to the variables such that the expression evaluates to True (i.e. either the expression is malformed or all assignments evaluate to False).

Now consider a different problem called 3-SAT. It is just like SAT except that the boolean expressions are limited to only those that are in conjuctive normal form with at most 3 literals per clause. Since this is a subset of boolean expressions, we can simply consider them as instances of our original SAT problem. Thus 3-SAT is reducible to SAT.

This would be considered a trivial reduction. Trivial to the point that most people wouldn’t bother to mention it. Mostly because you clearly just ‘added more things’ to get from 3-SAT to SAT.

A much more interesting, and surprising, reduction is in the other direction: every problem of SAT can be relatively easily parsed for being malformed or not and if not malformed then expressed as an instance of 3-SAT. In proper math form, I’ll leave finding this reduction as an exercise to the reader.

This reduction uses both the reducere-concept and (since it has a more restrictive language of instances) the reduce-concept. It is also non-trivial and I think why people associate reductionism with eliminating things (since reductions are usually trivial when you add things).

Vitalism and materialism in biology

To make this more closely related to the philosophy of science, let’s turn to biology. At some point, living things were explained in terms of vitalistic theories. Theories that posited that “living organisms are fundamentally different from non-living entities because they contain some non-physical element or are governed by different principles than are inanimate things” (Bechtel & Richardson, 1998) — an elan vital. These vitalistic theories can be a reasonable reductive theory since they aim to explain all biological phenomena in terms of material properties and the properties of elan vital. In fact, we could take our existing theories of biology, add elan vital to them, and thus reduce them to a vitalistic theory. Material biology reduces to vitalistic biology in the same kind of (boring) way as 3-SAT reduces to SAT.

But if you’re interacting with a non-mathematician then you might expect them to put the burning rubbish bin out instead of on the table. You would expect to see vitalism as a classic example of what reductionism lets us avoid. The classic presentation is that vitalistic biology reduces to material biology in the same kind of (more interesting) way as SAT reduces to 3-SAT. This is very interesting, but it doesn’t establish material biology as more reductive than vitalistic biology; rather it establishes that the two are theoretically equivalent. But we should prefer materialistic biology to vitalistic biology because the extra expressiveness of vitalistic biology is superficial and not useful for our investigations.

Omnicompetence of science

But this Occam’s razor aspect is, I think, less important than the will to generality or the imperialistic tendency in thought. We want to explain many things by the same sort of thing. We want science to be omnicompetent: able to answer every kind of question. Finding that many apparently different theories reduce to the same theory is more satisfying than having a special theory for every special science.

We can see this in theoretical computer science, too.

Even if you’re not a cstheorist, you might have heard that 3-SAT is an important problem before this post. However, you might not have heard of all (but surely some) of the following: protein folding, traveling-salesman problem, vertex colouring, max clique, quadratic programming, integer linear optimization, flight scheduling, etc. The reason that 3-SAT is exciting is that all of these problems are reducible to it (and it to them). Thus, if you gain a deep understanding of 3-SAT then you can also gain a deep understanding of these other problems. If you find an algorithm to solve 3-SAT instances significantly faster then you can also solve these other problems much faster.

With physicalism, science has a similar aim. The hope is that if we can find workable theoretical reductions from all aspects of science to physics then a deep understanding of physics (which we like to assume that we have) will translate to a deep understanding of all of these other fields. But in science, this is an ontological claim, not a formal demonstration.

Now, if you aren’t familiar with the reduction from SAT (or the various other problems I name-dropped) to 3-SAT, you might have felt cheated by my assertion that the former can be reduced to the latter. Fortunately in computer science, there are actually proofs of that reduction that you can look up and analyze. It isn’t just a vague ontological claim. This is not so in most sciences where the reduction is unknown but assumed to exist by fiat, analogy or limits of imagination (“everything else is super-natural”). This is the motte-and-bailey of reductionism: praising the strengths of formal reductions but only having ontological reductions.

To return back to the philosophy of mind, we can look at a reduction like: all thought is reducible to electric currents in the nerves that constitute the brain. This might seem as exciting as SAT being reduced to 3-SAT, but we should dig deeper. All activation of refrigerators and air conditioners around the county can also be reduced to electric currents in the wires that constitute the electric network. Yet, most of us, imagine ourselves as conscious and the electric grid as not. So just knowing that thought is reducible to neural activity doesn’t really get us anything on its own.

Algorithm design as inspiration for good reductions

To get good reductions, we can turn to algorithm design. In algorithm design, we care about efficient reductions to problems where we already have good general algorithms. Further, we want these reductions to be concrete and not doing too much work; not just ‘expected to exist’. In the context of theories in science instead of problems in CS, we would expect ‘good general algorithms’ to mean something like good ways of doing experiments and making measurements. In this way, reducing health to molecular biology rather than elan vital is a good choice since we have more ways to run experiments and manipulate molecular biology than we do for elan vital. Reducing psychology to neuroscience, on the other hand, can be hit or miss when we don’t have better ways to run neuroscience experiments than we do to run psychology experiments.

Also, and this is essential to the power of reductions in computer science, we need to know how handle arbitrary instances of the theory we are reducing to. Not just simple cases. This is where reductionism fails most often in science. When we attempt to reduce something to physics and end up with a complex adaptive system that we can’t understand or analyze. This is where the urge to simplify appears, and we start throwing away essential details to get workable reductive theories. In the process we embrace reduce and throw away reducere. We switch from reductionism to eliminativism.

Of course, there are many gaps in my computer science account of philosophical reductivism. I will have to deal with these gaps in the new year. The important things to understand is how the complexity of phenomena is distributed between the reduction and the subroutine calls, and where people most often make simplifications (I assume in the interactions, as with game theoretic models). A fun thing to understand would be what the flipped perspective of computational complexity (rather than algorithm design) would mean in the context of science. What does a reduction from an intractable problem to the problem under analysis mean when we replace problems by theories? So, dear reader, come back next year and we can explore these points.