Complexidade de Kolmogorov: Diferenzas entre revisións

A complexidade de Kolmogorov ten súa orixe nos anos [[1960]], cando [[Kolmogorov|Andrei Kolmogorov]], [[Ray Solomonoff]] e [[Gregory Chaitin]] desenvolveron, de forma independente, unha teoría da información baseada no tamaño dos programas para a [[Máquina de Turing]]. Acordouse chamar a área xenericamente como "complexidade de Kolmogorov" en homenaxe ao famoso matemático [[Rusia|ruso]], e fundador da área, [[Kolmogorov|Andrei Nikolaevich Kolmogorov]] ([[1903]]-[[1987]]).

 

A complexidade de Kolmogorov está definida sobre o conxunto de cadeas binarias (secuencias de ceros e uns). Ela asocia a cada cadea binaria un valor numérico que é súa "complexidade".

 

É importante que se fundamente ben o concepto de descripción (ou sexa, formalmente definido como un programa para a máquina de Turing) para evitar paradoxos. Os paradoxos (ou antinomias) son bastante frecuentes na historia da matemática. Podemos citar o famoso "paradoxo do barbeiro", de [[Bertrand Russel]], que di que "o barbeiro é aquel que afeita aos homes que non se afeitan a si mesmos". O paradoxo é obtido ao perguntar se o barbeiro se barbea a si mesmo.

 

{{Ver artigo principal|[[Máquina de Turing]]}}

A Máquina de Turing é un dispositivo que foi proposto en [[1936]] por [[Alan Turing]] co obxectivo de formalizar matematicamente o que entendemos por "computador". Ela está formada basicamente por unha fita (cinta) na cal un cabezallo pode escribir símbolos dun conxunto predefinido, e así cálculos de diversos tipos poden ser feitos apenas cos movimentos deste cabezal sobre a fita.

Unha resposta consistente ao problema de definir o concepto de secuencia aleatoria foi dada por [[Martin-Löf]]. A definición de Martin-Löf basease na [[teoría da medida]], e na existencia dun conxunto efetivo nulo máximo, no conxunto das cadeas binarias. Isto significa a existencia dun conxunto nulo (con baixa probabilidade de ocorrencia) que contén todos os conxuntos nulos cuxas cadeas poden ser algoritmicamente xeradas. Esta definición equivale a afirmar a existencia dun teste de aleatoriedade universal. Interesante observar que a definición de Martin-Löf é equivalente á definición de secuencia aleatoria dada pola complexidade de Kolmogorov (via incompresividade das cadeas).

 

Solomonoff propuxo o uso da regra de Bayes para obter previsión inductiva, ou sexa, para prever a secuencia dunha cadea binaria. Para isto el usou como probabilidade previa a probabilidade universal, que pode ser definida como <math>2^{-K(x)}</math>, porque ela domina toda probabilidade previa semi-computable concebible. Isto constituise no núcleo dos métodos de intelixencia artificial MDL (minimum description length) e MML (minimum message length).

 

* [[Máquina de Turing]]

 

 

* [http://www.hutter1.de/kolmo.htm Kolmogorov Complexity Resources]