It’s worse than that. Programs you can examine without running are measure zero. Just like most numbers are non-computable. Constructing a program that can only be fully examined by running it is trivial. Constructing a program that does what you want 99% of the time and fails horribly 1% of the time is the default for a decent programmer really trying to hit that “measure zero”, and the whole discipline of software engineering is devoted to minimizing the odds of failing horribly.
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.
Programs you can examine without running are measure zero.
If you know of a proof of that, then I believe it, but it has no relevance to my argument because programmers do not choose programs at random from the space of possible programs: they very tightly limit their attention to those prospective programs that makes their job (of ensuring that the program has the properties they want it to have) as easy as possible.
I am not a mathematician, but a sketch of a proof would be like this: A program can be mapped into a string of symbols, and a random string of symbols is known to be incompressible. A syntactically valid program in a given language out to be mappable to a string, one valid syntactic statement at a time. Thus a random syntactically valid program is mappable to a random string and so is incompressible.
programmers do not choose programs at random from the space of possible programs: they very tightly limit their attention to those prospective programs that makes their job (of ensuring that the program has the properties they want them to have) as easy as possible.
Indeed we do. However, hitting a measure zero set is not easy, and any deviation from it lands you back in the poorly compressible or incompressible space, hence the pervasive bugs in all code, without exception, bugs you can only find by actually running the code. An ambitious program of only writing correct code (e.g. https://dl.acm.org/doi/10.1145/800027.808459) remains an elusive goal, probably because the aim is not achievable, though one can certainly reduce the odds of a program taking off into unintended and incompressible directions quite a lot, by employing good software development techniques.
Often a comment thread will wander to a topic that has no bearing on the OP. Has that happened here?
Does your most recent comment have any relevance to how much hope we humans should put in the fact that an AI cannot know for sure whether its sensory data has been faked?
It’s worse than that. Programs you can examine without running are measure zero. Just like most numbers are non-computable. Constructing a program that can only be fully examined by running it is trivial. Constructing a program that does what you want 99% of the time and fails horribly 1% of the time is the default for a decent programmer really trying to hit that “measure zero”, and the whole discipline of software engineering is devoted to minimizing the odds of failing horribly.
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.
If you know of a proof of that, then I believe it, but it has no relevance to my argument because programmers do not choose programs at random from the space of possible programs: they very tightly limit their attention to those prospective programs that makes their job (of ensuring that the program has the properties they want it to have) as easy as possible.
I am not a mathematician, but a sketch of a proof would be like this: A program can be mapped into a string of symbols, and a random string of symbols is known to be incompressible. A syntactically valid program in a given language out to be mappable to a string, one valid syntactic statement at a time. Thus a random syntactically valid program is mappable to a random string and so is incompressible.
Indeed we do. However, hitting a measure zero set is not easy, and any deviation from it lands you back in the poorly compressible or incompressible space, hence the pervasive bugs in all code, without exception, bugs you can only find by actually running the code. An ambitious program of only writing correct code (e.g. https://dl.acm.org/doi/10.1145/800027.808459) remains an elusive goal, probably because the aim is not achievable, though one can certainly reduce the odds of a program taking off into unintended and incompressible directions quite a lot, by employing good software development techniques.
Often a comment thread will wander to a topic that has no bearing on the OP. Has that happened here?
Does your most recent comment have any relevance to how much hope we humans should put in the fact that an AI cannot know for sure whether its sensory data has been faked?