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 )

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?