The set of all programs is countable, and so unlike the set of real numbers there is no uniform probability measure over them. We can’t conclude that the set of predictable programs has measure zero, except by choosing a measure in which they have measure zero.
Then we’re left with the task of trying to convince people why that choice of measure is better or more natural than any other of the infinitely many choices we could have made. This may be difficult since some quite natural measures result in the set of predictable programs having nonzero measure, such as Chaitin’s measure for programs written in a prefix-free language. This is strongly related to the types of prior we consider in Solomonoff induction.
We could consider things that are related to probability but aren’t actually measures, such as asymptotic density. However this too runs into problems since in all current programming languages, there is a nonzero bound on the fraction of programs of every length with predictable results.
I do agree that in practice humans suck at completely bounding the behaviour of their programs, but there’s no fundamental theorem in computer science that requires this. It is true that any given predictor program must fail to predict the runtime behaviour of some programs, but it is also true that given any particular program, there exists a predictor that works.
The set of all programs is countable, and so unlike the set of real numbers there is no uniform probability measure over them. We can’t conclude that the set of predictable programs has measure zero, except by choosing a measure in which they have measure zero.
Then we’re left with the task of trying to convince people why that choice of measure is better or more natural than any other of the infinitely many choices we could have made. This may be difficult since some quite natural measures result in the set of predictable programs having nonzero measure, such as Chaitin’s measure for programs written in a prefix-free language. This is strongly related to the types of prior we consider in Solomonoff induction.
We could consider things that are related to probability but aren’t actually measures, such as asymptotic density. However this too runs into problems since in all current programming languages, there is a nonzero bound on the fraction of programs of every length with predictable results.
I do agree that in practice humans suck at completely bounding the behaviour of their programs, but there’s no fundamental theorem in computer science that requires this. It is true that any given predictor program must fail to predict the runtime behaviour of some programs, but it is also true that given any particular program, there exists a predictor that works.