Diferenzas entre revisións de «Complexidade de Kolmogorov»

m
Robot: Reemplazo automático de texto (-conceito +concepto)
m (Bot:formateando categorías en maíuscula)
m (Robot: Reemplazo automático de texto (-conceito +concepto))
 
== Secuencias Aleatorias de Martin-Löf ==
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).
 
== Aplicacións ==
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).
 
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.
 
Chaitin construíu un paradoxo co tamaño dos programas que constituise nunha proba alternativa ao que ficou coñecido como proba de [[Kurt Gödel|Gödel]] (ou [[Teorema da incompletude de Gödel]]). Chaitin baseouse no paradoxo de Berry que supón considerar o menor número enteiro positivo que non pode ser definido por unha frase con menos de 1.000.000.000 de caracteres. Sen embargo, a propria definición do problema define o número e ten menos de 1.000.000.000 de caracteres, o que é unha contradicción. Isto resulta que as cadeas non se poden producir por programas que teñan menos complexidade que a propria cadea, sendo isto un limite dos sistemas formais.
505

edicións