pozorvlak (pozorvlak) wrote,
pozorvlak
pozorvlak

Computers are useless; they can only give you answers

Here's something that's been bugging me for a while: why are computers useful?

A bit of an odd question, you might think, and I'm going to need to explain some background. First, you need to know that there are problems that computers can't solve, even in principle. A classic example is the halting problem: given a program and its input, can you predict whether or not the program will terminate? Alan Turing showed that it's impossible to write a program that will do this correctly in all cases. A co-worker of mine was once asked to do precisely this by a client...

Next, you need to know a bit about infinity, and the surprising behaviour of infinite sets. The first surprising fact is that infinite sets that you would expect to be different sizes are often the same size. For instance, there are exactly as many even numbers as there are whole numbers. But one includes all the odd numbers, and the other doesn't - what's going on? To understand this, you have to think a bit more about what "counting" means. When we count, say, apples, what do we do? We point at the first one, and say "one", we point at the second one and say "two", and so on, making sure that each apple gets counted once and no apple gets counted more than once. When we run out of apples to count, we stop. Mathematically speaking, we've set up a one-to-one correspondence between the set of apples and some finite set {1,2,3,...n}.

The trouble with applying this procedure to infinite sets is the "when we run out..." bit. But the "one-to-one correspondence" bit works fine, so we apply Sliding Definition Ploy, and define two sets to be the same size if they can be in put in one-to-one correspondence with each other. Then the set of even numbers is the same size as the set of natural numbers, because they can be put in one-to-one correspondence, like so:
0 1 2 3 4 5  6  ...
0 2 4 6 8 10 12 ...
Similarly, the integers (positive and negative whole numbers) can be put in one-to-one correspondence with the natural numbers: list them in the order
0 1 -1 2 -2 3 -3 ...
. We say that a set which is the same size as the set of natural numbers is "countable", or "countably infinite". Surprisingly, the set of rational numbers (fractions) is countable! Write the positive ones down in a grid, like so
0   1   2   3   ...
1/2 1/3 1/4 1/5 ...
2/2 2/3 2/4 2/5 ...
3/2 3/3 3/4 3/5 ...
4/2 4/3 4/4 4/5 ...
5/2 5/3 5/4 5/5 ...
 .   .   .   .
 .   .   .   .
Then start zig-zagging back and forth, listing them in the order 0 1 1/2 2/2 1/3 2 3 1/4 2/3 3/2 ... Every time you get to a number which you haven't seen before, add that (and its negative) to your list: if you get to a number you've seen before, throw it away.

"OK," you might be thinking (well, I hope you're thinking "Woah!" in a Keanuesque manner, but I digress), "so some infinite sets that you'd expect to be very different sizes are actually the same size. So, are all infinite sets the same size?" No, they aren't, and that's the second surprising thing (though arguably it's only surprising in light of the first surprising thing). For instance, the set of real numbers between 0 and 1 is larger than the set of all natural numbers!

What does that mean? We didn't actually define "larger than" for all sets above, so let's think what it means for finite sets. Observe that a finite set A is larger than a finite set B when every attempt to pair off A-things with B-things leaves us with some A-things left over. Let's call an assignment of an A-thing to every B-thing a "map from B to A". Then, A is larger than B if every map from B to A fails to hit some A-thing. This doesn't make any mention of B and A being finite any more, so let's apply Sliding Definition Ploy again and define A to be "larger" than B if this condition holds. OK. So we want to show that any map from the natural numbers to the real numbers between 0 and 1 fails to hit some real number: equivalently, that any list of such real numbers leaves one out.

This may seem like a tall order - there are infinitely many such lists, how can we prove that every one of them has this property? We need a recipe, that takes a map from N to [0,1] (call it f) and produces a number that f doesn't hit. Let's think about what f is: it's an assignment of some real number (infinite decimal) to 0, another to 1, another to 2... in other words, it's an infinite list of infinite decimals.
0.a11a12a13a14a15a16...
0.a21a22a23a24a25a26...
0.a31a32a33a34a35a36...
0.a41a42a43a44a45a46...
0.a51a52a53a54a55a56...
0.a61a62a63a64a65a66...
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .
Now, let's form a decimal x as follows: the first digit after the decimal point is something other than a11. The second number is something other than a22. The third number is something other than a33. You get the idea, I'm sure. Then x is not equal to f(0), because it differs at the first decimal place; it's not equal to f(1), because it differs at the second decimal place; it's not equal to f(2), because... in short, x is not equal to any f(n), so it's not hit by f. You need to be a bit more cautious than that to make the argument really watertight (you need to get round the fact that 0.99999... = 1), but it can be done without too much difficulty. So, we've constructed a number that's not hit by f, and it didn't depend on the detail of f: any other map would have such a number, which we could construct in the same way. So, by our definition, the set [0,1] of real numbers between 0 and 1 is larger than the entire set N of natural numbers.

[Having trouble getting your head around that? Don't worry, you're in good company. You've just come across the famous Diagonalization Argument of Cantor, one of the most brilliant and infuriating in all of mathematics.]

Armed with this knowledge, we can see that Turing didn't need to exhibit an actual example of an uncomputable problem: he could have shown that some problems are uncomputable much more easily. Consider the following problem: you have some subset X of the natural numbers. X might be the set of even numbers, or the set of prime numbers, or the set of perfect numbers, or the set of Fibonacci numbers, or something like that. You want to write a program which will accept a number as input, and output "Yes!" if the number is in X, and "No!" if not. Now, by a close relative of Cantor's diagonal argument, there are uncountably many subsets of the natural numbers. But every program in your favourite programming language is a finite sequence chosen from an alphabet of finitely many symbols, so there can only be countably many programs! Hence, there must be some subsets X for which there is no such program. [I'd like to thank Jeff Egger for introducing me to this argument]. In fact, it's much worse than that - if you were to pick a subset at random, the probability that it would be computable would be 0. Not 1%, or 0.01%, or 0.000000001%, but actually zero. You need to be quite careful about how you define probability for this statement to make sense, but it's true. [Edit: having discussed this with an actual analyst, it turns out the truth is more complicated than I'd thought. There may be reasonable ways to define the probability measure on the space such that the probability of computability is non-zero. However, there is at least one way of defining a probability measure such that my statement is true - see my reply to benparker below.]

This seems like quite a contrived and artificial problem, but it's not really: lots and lots of useful problems can be re-stated in this form, with a judicious choice of X. We're not worried about how efficient the solution would be, only that one exists; hence, if the "subset of N" form of the problem is incomputable, so was the original form.

Hence my original question: why are computers useful? If the probability of a computer being able to answer our questions is zero in theory, how come they are so useful in practice? My former colleague aside, most of us don't need to worry about computability in our day-to-day coding: we can pretty much assume that there is a solution to our problem, and that finding it is the hard part.

I don't really know the answer, but it seems to me that it must have something to do with approximations. We're finite creatures, and we're usually happy with finite answers - we'll approximate an infinite decimal to one with ten (or thirty, or five hundred, or at most a few billion) decimal places, we'll just ask for the first few elements of an infinite sequence, we'll approximate the movement of continuous fluids by thousands of discrete chunks, and so on. This can lead to errors and problems, but usually these can be dealt with or lived with. Also, since we're finite, we're only capable of creating a finite amount of data for our computers to search through and manipulate. If we restrict the problem above to finite subsets of the natural numbers, the picture becomes a lot better: now there are only countably many subsets to choose from. We might still have probability zero, but it's not enforced in the way it was before.

In practice, as I said, the probability of their being a useful computable approximation to our original problem seems to be near to 100%. This strikes me as something close to miraculous. Is this just a mirage? Do we not encounter uncomputability because we subconsciously shy away from it, just as 19th-century scientists largely failed to notice the ocean of nonlinearity that they were swimming in? Or are the computable functions somehow dense in the uncomputable ones, in the way that the (countable) rational numbers are dense in the (uncountable) real numbers?
Tags: computers, ideas, maths, philosophy
Subscribe

  • PSA: Working Effectively With Legacy Code by Michael Feathers

    I am only about a hundred pages into this book, but it had paid for itself after fifty. I wish I'd read it ten years ago. Actually, I wish I'd read…

  • Srelipmoc ni esruoc tsrif a

    If I ever design a first course in compilers, I'll do it backwards: we'll start with code generation, move on to static analysis, then parse a token…

  • Commuting

    Quaffing the last of my quickening cup, I chuck fair Josie, my predatory protégée, behind her ear. Into my knapsack I place fell Destruction, my…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 30 comments

  • PSA: Working Effectively With Legacy Code by Michael Feathers

    I am only about a hundred pages into this book, but it had paid for itself after fifty. I wish I'd read it ten years ago. Actually, I wish I'd read…

  • Srelipmoc ni esruoc tsrif a

    If I ever design a first course in compilers, I'll do it backwards: we'll start with code generation, move on to static analysis, then parse a token…

  • Commuting

    Quaffing the last of my quickening cup, I chuck fair Josie, my predatory protégée, behind her ear. Into my knapsack I place fell Destruction, my…