\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of a sidewalk
Show Question

Richard–Berry paradox

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