It is notable that completeness and incomputability are complementary properties: It is easy to prove that any complete prediction method must be incomputable. Moreover, any computable prediction method cannot be complete — there will always be a large space of regularities for which the predictions are catastrophically poor.
— Ray Solomonoff, “Algorithmic Probability — Its Discovery — Its Properties and Application to Strong AI”
This quote is a paragraph from the book Randomness Through Computation, an amazing work I was reading this morning.
The idea that any computable prediction method can’t be complete is profound for those of us that work with machine learning; it implies we always have to deal with trade-offs. Explicitly considering this makes for a better thought process when designing applications.