Computers are useless; they can only give you answers

[pozorvlak]

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

Comments

[pozorvlak]

*fires off a quick email to an actual analyst to make sure*

Intuitively, it's basically for the same reason that 0.999999.... is equal to 1. Suppose they're not equal: then set e = 1 - 0.999... . By our assumption, e > 0. So e > 10^(-n) for some sufficiently large n. But 10^(-n) = 1 - 0.{n 9s}, which is greater than e, since 0.9999... has more than n nines. So e must be equal to zero. You can play a similar game and show that the probability has to be smaller than any positive number, and thus must be zero. Maybe we'd be better off if we allowed infinitesimals...

In a bit more detail: to talk meaningfully about probabilities over some space of possibilities (here, the subsets of N), you need to have a notion of measure on the space. I think (and have just sent an email to check) that there's a general theorem that if the space is infinite a subset of cardinality less than the whole space must have measure zero - you can deduce this from the axioms for a measure, which you need for probability theory to make sense. I'm not an expert in this stuff, though.

[pozorvlak]

OK, looks like I was wrong about that bit. Hopefully there's some true statement in that vicinity, though...

[pozorvlak]

OK, it's possible to define a probability measure on P(N) which makes it work, but there are other sensible probability measures for which it doesn't work. The one for which it works is a bit more natural than the others, I think, but it doesn't exactly leap out at you.

Stick with something handwavey, like "the computable ones are only a tiny fraction of the whole" :-)

[pozorvlak]

Actually, if you wanted, you could say "exponentially more": the number of subsets of N is 2 to the power of the number of computable subsets :-)