Diferenzas entre revisións de «Complexidade de Kolmogorov»

Unha resposta consistente ao problema de definir o conceitoconcepto 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).

A complexidade <math>K(x|y)</math> induce un conceitoconcepto de distancia (ou similaridade), chamada distancia de información, que é unha medida a priori e absoluta sobre o conxunto das cadeas binarias. Esta distancia pode ser aplicada en diversos e diferentes contextos de forma moito similar a outras medidas de distancia definidas na matemática. O interesante é que podemos aproximar esta medida usando un programa compresor de dados e efetuar medicións empíricas. Destácanse como aplicacións desta distancia o recoñecimento dos xenomas, a clasificación automática de música, e o establecimento dunha hierarquía de linguaxes humanas.