Repositorio de producción científica de la Universidad de Sevilla

Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines

Opened Access Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Soler Toscano, Fernando
Zenil, Hector
Delahaye, Jean-Paul
Gauvrit, Nicolas
Departamento: Universidad de Sevilla. Departamento de Filosofía y Lógica y Filosofía de la Ciencia
Fecha: 2014
Publicado en: PLoS ONE, 9 (5), 1-18.
Tipo de documento: Artículo
Resumen: Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings. The method is an alternative to the traditional lossless compression algorithms, which it may complement, the two being serviceable for different string lengths. We provide a thorough analysis for allP11 n~1 2n binary strings of length nv12 and for most strings of length 12ƒnƒ16 by running all *2:5|1013 Turing machines with 5 states and 2 symbols (8|229 with reduction techniques) using the most standard formalism of Turing machines, used in for example the Busy Beaver problem. We address the question of stability and error estimation, the sensitivity of the continued application of the method for wider coverage and better accuracy, and provide statistical evidence suggesting robustness. As with compression algorithms, this work promises to deliver a ra...
[Ver más]
Cita: Soler Toscano, F., Zenil, H., Delahaye, J. y Gauvrit, N. (2014). Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines. PLoS ONE, 9 (5), 1-18.
Tamaño: 1.968Mb
Formato: PDF

URI: http://hdl.handle.net/11441/64191

DOI: 10.1371/journal.pone.0096223

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones