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