In the philosophy of computer science, there is a problem sometimes called the “waterfall problem”: properly interpreted, isn’t everything doing computation?

Suppose we have a waterfall, and we compare the positions of the atoms at the start of the waterfall to their positions at the bottom (which we will assume are randomly but deterministically, changed). Now, suppose we want to argue that this waterfall is implementing a chess-playing algorithm. Then all we have to do is provide some mapping from a chess position to the “input” of the waterfall, and some mapping from the “output” to a legal move, and we’re done. And, of course, we can always do this, provided we’re willing to spend enough time gerrymandering our mappings!

Scott Aaronson argues that all the real work is going into producing the mapping - in practice, computing the mapping would require solving the chess-playing problem! We could show this by producing a program that solves the problem without access to the waterfall as quickly (in complexity terms) as one with access to the waterfall.

The epistemic question

There’s a related question, though, which is: given a waterfall, how can we tell if it is computing something (or some particular computation)? We might think that we can at least answer negatively in some cases. If the action of the waterfall is indistinguishable from a random function (that is, it is a pseudorandom function), then surely it cannot be computing anything.

But pseudorandom functions are an integral building block of encryption systems. In particular, we would like the function “encrypt m with key k” to be a pseudorandom function for any given k - that means that an attacker gets no information about m from the ciphertext. So an encryption function looks like a “waterfall”, but it is definitely doing computation, even under Scott’s constraints (we can’t get rid of the waterfall without adding work).

This makes it essentially impossible to distinguish waterfalls that aren’t doing computation from those that are, at least by just looking at inputs and outputs. Perhaps we could do better if we look at the implementation of the waterfall, but that’s a much harder problem.

Homomorphic encryption

We can go even further. We know that homomorphic encryption is possible, wherein we can perform arbitrary computations on encrypted data. That means that we can encrypt the initial state of a Turing machine, and then run it in an encrypted state, such that at all points the state is indistinguishable from randomness, but at the end we can extract the result by “merely” decrypting it.

So homomorphic encryption means that we can turn any computation into a “waterfall”, and hence for any waterfall it could be implementing any computation, as far as we know.

Philosophical implications

The waterfall problem is often used to attack computationalism in the theory of mind. The epistemic version can also be used for this purpose. If we can’t tell whether a waterfall is implementing any given computation, and certain computations give rise to minds, then we can’t tell whether waterfalls have minds. But we can tell that waterfalls don’t have minds, reductio.

I think that the computationalist can just bite the bullet here. If a waterfall really is implementing a encrypted mind, then it does have a mind! But that is very unlikely. We can still argue that most waterfalls aren’t doing any computational work, in Scott’s sense. What was particularly damaging about the original argument was that it implied that all waterfalls were implementing all computations (including those giving rise to minds). Here, even if we could argue that all waterfalls implement some (possibly encrypted) computation, it seems very unlikely that they implement all computations.