One of my favorite moments at RIT was when Rhys Price Jones proved, mathematically, that computer science is wholly useless. Perhaps this is quasi-overstated, but please, keep reading.
To put this more mathematically, the whole point of the proof was two things. First, the cardinality of the set of all “problems”, i.e. all questions with a yes/no answer, is aleph-one, or the size of the set of real numbers. Following this, the cardinality of the set of all programs that we can produce in a discrete setting is aleph-null, or the same size as the set of countable numbers.
Just for the sake of intellectual masturbation, I’ll place the theory here as best I can:
First, let us consider the set of all programs we can produce, say, in Java. Assuming a finite sized set of characters (alphabet), we will write out every program, ordered by length and by character ordering (”a”, “b”, “c”, …, “aa”, “ab”, etc.). Note that most of these programs are not really valid programs, but that isn’t really important to the proof. The point is that you can place these programs in order, by length and character, and thus they are countable, and the cardinality of a countable set is, at most, aleph-null.
Now, let us consider the set of all “problems”. This requires a bit of an intermediary “proof”, which I will do a huge disservice to by not actually proving. Maybe an example will be enough, though. The first thing to note is that any question can be replaced by a boolean problem (answer is yes/no, true/false, etc.). To give an example, let’s say you have the question:
“Who is Brandy’s mother?”
This can be replaced by a set of questions, one for each person in the entire world, that says:
“Is this person Brandy’s mother?”
To which we can answer yes or no. Again, this is a quick glossing over of what is happening, but that is the premise.
With that being said, we also need to consider inputs to these boolean “functions”. In the above problem, the input would be the person we are asking about. Any such input, for the sake of this proof, we will encode as a natural number. This means that we have a countably infinite set of inputs for our boolean functions.
Here we go: now let’s try and figure out the cardinality of the set of these boolean functions, or problems. Here’s the story, as best as I remember from Rhys (my apologies for any misquotations):
Let’s say Arnold Schwarzenegger is standing outside, and I call down to him, “Hey, Arnie, give me a list of all of the boolean functions there are!” And Arnie tells me, one by one. Since Arnie is so amazing, the cardinality of the problems he tells me is countable, since he did list them one by one. Now, I write each on the board, on my countably infinitely sized board. Now I need to make a little mapping of inputs to functions, so across the top of the board, I write all of the functions, and moving down the board, I write down the set of all inputs. Now, I go through for each mapping of problem to input and write a 0 or 1 for each (true/false). Arnie has listed every problem, and we have listed every input, right?
Just to make sure, I add another input. To do this, I work my way along the diagonal of the mapping. Basically, starting with problem 1 and input 1, my new boolean function will return the opposite of what problem 1 does for input 1 (false for true, true for false). I continue doing this for each problem/input along the diagonal, until I have gone through every input/problem. Now, we ask, “Have I already written down this boolean function?” The answer is no: because of how we created this new function, it differs from every existing function in at least one place. We made sure of this.
So how do we get around this? You can add as many more problems as you wish, and I can still create a new one through diagonalization that differs from all functions in exactly one place. So the answer is this: we can’t. You cannot list the set of all boolean functions, of all problems, because they cannot be listed. That set is not countable, and therefore has the cardinality of aleph-one, the same as the size of real numbers.
So what does this mean? Mathematically, it means that the set of problems we can solve is beyond miniscule in reference to all of the problems that exist. Most computer scientists who have heard this proof generally come up with one of two conclusions:
- So what? Who cares?
- Just because it is relatively small doesn’t mean that it is actually “small” in the sense of what we traditionally mean by the word. The fact is, it is still infinitely (countably) large, and will remain a vast area of unknown for us. Also, how do we judge the relative value of each exclusive set? Perhaps the problems that we can solve are all “meaningful” problems, and the problems we can’t are entirely useless. Who knows?
So there you go. Think about it a bit. See what you decide.