Estoy buscando un algoritmo que pueda calcular una aproximación de la complejidad de Kolmogorov de la cadena de entrada dada. Así que si K es la complejidad de Kolmogorov de una cadena S, y T representa el tiempo, entonces la función se comportaría algo como esto .. límite (t-> inf) [K_approx (t, S)] = K.Kolmogorov Complejity Approximation Algorithm
En teoría, un programa podría converger en la complejidad de Kolmogorov de su cadena de entrada a medida que el tiempo de ejecución se aproxima al infinito. Podría funcionar ejecutando todos los programas posibles en paralelo que sean la longitud de la cadena de entrada o más corta. Cuando se encuentra un programa de una longitud determinada, esa longitud se identifica como la longitud mínima conocida por el momento, se imprime y no se intentan más programas> = esa longitud. Este algoritmo (probablemente) se ejecutará para siempre, imprimiendo longitudes más cortas y más cortas, convergiendo en la complejidad exacta de Kolmogorov en un tiempo infinito.
Por supuesto, ejecutar un número exponencial de programas es altamente inutilizable. Un algoritmo más eficiente es publicar un code golf on StackOverflow. Algunos inconvenientes:
O pronto tocará un solo programa que se ejecuta para siempre, y no puede decidir si detenerlo o dejarlo funcionar unos segundos más (décadas). – rwong
@rwong: Correcto, es por eso que los ejecuta en paralelo. Para los muchos programas que parecen ejecutarse para siempre, se les permite seguir funcionando hasta que se encuentre una solución más corta (si es que alguna vez). –
Supongo que sería razonable agregar otro parámetro a la función que especifica la longitud máxima de la máquina de Turing ... ¿ entonces podríamos tener una función que tenga una propiedad como esta? límite (t-> inf) [límite (T_max-> inf) [K_approx (t, S, T_max)]] = K – Tony
Creo que esto podría funcionar? Si alguien ve un error, por favor indíquelo.
function KApprox(S:string,t:integer,TapeSizeMax:integer) : Turing Machine of size k
begin
// An abstract data type that represents a turing machine of size k
var TM(k:integer) : Turing Machine of size k;
var TMSmallest(k:integer) : Turing Machine of size k;
var j : integer;
var i : integer;
for (j = t to 0 step -1) // reduce the time counter by 1
begin
for (i = TMax to 1 step -1) // go to the next smaller size of TM
begin
foreach (TM(i)) // enumerate each TM of size i
begin
if (TM(i).halt(TapeSizeMax) == true) and (TM(i).output() == S) then
begin
if (sizeof(TM(i)) < sizeof(TMSmallest(i))) then
TMSmallest(i): = TM(i);
end;
end;
end;
end;
return TMSmallest;
end;
El wikipedia page de la complejidad de Kolmogorov tiene una subsección titulada "incomputabilidad de la complejidad de Kolmogorov", en la sección "Resultados básicos". Esto no pretende ser una medida básica que pueda calcular, o incluso aproximarse productivamente.
Hay mejores formas de lograr lo que quiere, sin lugar a dudas. Si lo que quieres es una medida de aleatoriedad, puedes probar la función de entropía binaria. La compresibilidad por uno de los algoritmos estándar también podría ajustarse a la factura.
El artículo de Wiki ni siquiera menciona la frase "aproximada productivamente" en ninguna parte. La cuestión de calcular el KC de una cadena no se está preguntando. Es indecidible ... fin de la historia. Todo lo que busco es una función que conduzca a mejores y mejores aproximaciones al darle más tiempo y recursos espaciales. – Tony
@Tony: su algoritmo no está completamente especificado. No estoy seguro de cómo planeas probar todas las máquinas de Turing posibles hasta cierto tamaño con cada cadena de entrada posible, pero incluso si pudieras hacer esto de alguna manera significativa, el costo de tiempo sería exponencial en la entrada. Por agradable que parezca la teoría, simplemente no es algo que funcione en la práctica. –
@Rob, la función solo toma 1 cadena como entrada "S: String", y solo probará máquinas turing de tamaño TMax. entonces no estamos probando todas las máquinas de turing, y por lo tanto no podemos obtener el KC exacto de la cadena de entrada. – Tony
Parece que Ray Solomonoff hizo un gran trabajo en este campo.
Publications of Ray Solomonoff
Does Algorithmic Probability Solve the Problem of Induction?
La primera cuestión que noto es que "la complejidad de Kolmogorov" no está bien definido. Depende hasta cierto punto de la elección de cómo representar los programas. Entonces, lo primero que tendría que hacer es corregir algunas codificaciones de programas (por ejemplo, la especificación de Joey Adams de que los programas se escriban en J).
Una vez que tiene la codificación, el algoritmo que está buscando es bastante simple. Vea la respuesta de Joey para eso.
Pero la situación es aún peor que tener que ejecutar de forma exponencial muchos programas. Cada uno de esos programas podría ejecutarse tanto como te puedas imaginar (técnicamente: el tiempo de ejecución como un tamaño de entrada de función podría crecer más rápido que cualquier función recursiva).Además, podría darse el caso de que algunos de los programas más cortos sean los que se ejecuten más tiempo. Entonces, mientras que el enfoque paralelo se acercará al valor correcto a medida que el tiempo vaya al infinito, lo hará de manera inimaginablemente lenta.
Puede detener el programa prematuramente, pensando que la aproximación en ese punto es suficiente. Sin embargo, no tienes idea en general de lo buena que es esa aproximación. De hecho, hay teoremas que muestran que nunca se puede saber.
Así que la respuesta corta es "fácil, solo usa el algoritmo de Joey", pero por cualquier medida de practicidad, la respuesta es "no tienes oportunidad". Como ha recomendado Rwong, es mejor que simplemente use un algoritmo de compresión de alta resistencia.
Para quienes no estén familiarizados con el tema, la complejidad de Kolmogorov de una cadena es, en esencia, "la longitud del programa más corto que genera la cadena". Por ejemplo, se puede producir una tabla de multiplicar de 9x9 en 8 caracteres ('*/~ 1 + i.9') con el lenguaje de programación J ([ver aquí] (http://stackoverflow.com/questions/3412730/code- golf-output-multiplication-table-to-the-console)). A partir de esto, podría decirse que una tabla de multiplicar de 9x9 tiene una complejidad de Kolmogorov de 8 o menos con respecto al lenguaje de programación J. –
Si está intentando probar algo formalmente, tendrá que escribir su prueba independientemente de (sin tener en cuenta) el método utilizado para aproximarlo. Si solo buscas diversión, ¿qué tal si pruebas un algoritmo de compresión de datos? – rwong
No, no estoy buscando una prueba. Estoy buscando un algoritmo que satisfaga las propiedades mencionadas anteriormente. No he podido encontrar uno, y quería saber si alguien ya lo ha hecho. No conozco algoritmos de compresión de datos que, en principio, puedan encontrar la Complejidad de Kolmogorov exacta con tiempo suficiente. Supongo que a primera vista, ya que siempre está trabajando con cadenas finitas, podría funcionar una búsqueda de enumeración de todas las posibles máquinas de Turing ... Pero el problema podría ser indecidible. Estoy buscando un algoritmo como este para aplicaciones de aprendizaje automático. – Tony