Show Question

A paradox highlighting an issue with using description length as a measure of complexity.

Define a specific natural number as "the least natural number that cannot be described in fewer than 20 words".

If such a number does exist, then we have just described it in 13 words, contradicting its definition. If such a number doesn't exist, then all natural numbers can be described in fewer than 20 words.

Thus, there is a need for the meaning of 'description' to be inspected closely.

#### Source

M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and ItsApplications.
Chapter 1
p 1