Relationship With Kolmogorov Complexity
It is not possible in general to unambiguously define what is the minimal number of symbols required to describe a given string (given a specific description mechanism). In this context, the terms string and number may be used interchangeably, since a number is actually a string of symbols, i.e. an English word (like the word "eleven" used in the paradox) while, on the other hand, it is possible to refer to any word with a number, e.g. by the number of its position in a given dictionary, or by suitable encoding. Some long strings can be described exactly using fewer symbols than those required by their full representation, as is often experienced using data compression. The complexity of a given string is then defined as the minimal length that a description requires in order to (unambiguously) refer to the full representation of that string.
The Kolmogorov complexity is defined using formal languages, or Turing machines which avoids ambiguities about which string results from a given description. It can be proven that the Kolmogorov complexity is not computable. The proof by contradiction shows that if it were possible to compute the Kolmogorov complexity, then it would also be possible to systematically generate paradoxes similar to this one, i.e. descriptions shorter than what the complexity of the described string implies. That is to say, the definition of the Berry number is paradoxical because it is not actually possible to compute how many words are required to define a number, and we know that such computation is not feasible because of the paradox.
Read more about this topic: Berry Paradox
Famous quotes containing the words relationship with, relationship and/or complexity:
“Guilty, guilty, guilty is the chant divorced parents repeat in their heads. This constant reminder remains just below our consciousness. Nevertheless, its presence clouds our judgment, inhibits our actions, and interferes in our relationship with our children. Guilt is a major roadblock to building a new life for yourself and to being an effective parent.”
—Stephanie Marston (20th century)
“Whatever may be our just grievances in the southern states, it is fitting that we acknowledge that, considering their poverty and past relationship to the Negro race, they have done remarkably well for the cause of education among us. That the whole South should commit itself to the principle that the colored people have a right to be educated is an immense acquisition to the cause of popular education.”
—Fannie Barrier Williams (1855–1944)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)