Completeness and incomputability

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.


  1. Ray Solomonoff — Wikipedia.
  2. Solomonoff’s Lightsaber — Wikipedia, LessWrong

Leave a Reply