Resumen

Dada la amplia utilización de algoritmos de compresión sin pérdida para aproximar la complejidad algorítmica (Kolmogorov-Chaitin) y que, por lo general, los algoritmos de compresión sin pérdida genéricos no son suficientes para caracterizar características distintas a las estadísticas no diferentes de las evaluaciones de entropía, aquí exploramos un enfoque alternativo y complementario. Estudiamos propiedades formales de una medida inspirada en Levin calculada a partir de la distribución de salida de pequeñas máquinas de Turing. Introducimos y justificamos aproximaciones finitas que se han utilizado en algunas aplicaciones como alternativa a los algoritmos de compresión sin pérdida para aproximar la complejidad algorítmica (Kolmogorov-Chaitin). Proporcionamos demostraciones de las propiedades relevantes de ambos y los comparamos con la Distribución Universal de Levin. Proporcionamos estimaciones de error de con respecto a . Finalmente, presentamos una aplicación a secuencias de enteros de la Enciclopedia

• Materias:Simulación dinámica Toma de decisiones Regresión lineal Cargas controladas Seguridad multimedia
• Subjects:Dynamic simulation Decision making Linear regression Controlled loads Multimedia safety
• Palabras claves:Algoritmos de compresión; Complejidad algorítmica; Medida inspirada en Levin; Máquinas de Turing; Estimaciones de errores; Secuencias de enteros
• Keywords:Compression algorithms; Algorithmic complexity; Levin-inspired measure; Turing machines; Error estimations; Integer sequences