speaking, defined as the Kolmogorov complexity of x given y as an auxiliary input to the procedure. There is also a length-conditional complexity , which is the complexity of x given the length of x'' as known/input. See also Berry paradox Code golf Data compression Descriptive complexity theory Grammar induction Inductive inference Kolmogorov structure function Levenshtein distance Solomonoff's theory of inductive inference Sample entropy Notes References Further reading External links The Legacy of Andrei Nikolaevich Kolmogorov Chaitin's online publications Solomonoff's IDSIA page Generalizations of algorithmic information by J. Schmidhuber Tromp's lambda calculus computer model offers a concrete definition of K()] Universal AI based on Kolmogorov Complexity by M. Hutter: David Dowe's Minimum Message Length (MML) and Occam's razor pages. Computability theory Descriptive complexity Measures of complexity Computational complexity theory