Complexidade de Kolmogorov

A complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade, profunda e sofisticada, que trata da quantidade de informação de objetos individuais, medida através do tamanho de sua menor descrição algorítmica. Ela é uma noção moderna de aleatoriedade, e refere-se a um conceito pontual de aleatoriedade, ao invés de uma aleatoriedade média como o faz a teoria das probabilidades. Ela é um ramo derivado da teoria da informação de Claude Shannon, embora hoje possa ser considerada uma área de pesquisa madura e autônoma.

Complexidade de Kolmogorov define uma nova teoria da informação, chamada teoria algorítmica da informação (por tratar com algoritmos). A Máquina de Turing é usada como mecanismo para descrever os objetos (para definir os algoritmos).