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

Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures

Opened Access Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures

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: 2013
Publicado en: Computability, 2 (2), 125-140.
Tipo de documento: Artículo
Resumen: We show that real-value approximations of Kolmogorov-Chaitin complexity K(s) using the algorithmic coding theorem, as calculated from the output frequency of a large set of small deterministic Turing machines with up to 5 states (and 2 symbols), is consistent with the number of instructions used by the Turing machines producing s, which in turn is consistent with strict integer-value program-size complexity (based on our knowledge of the smallest machine in terms of the number of instructions used). We also show that neither K(s) nor the number of instructions used manifests any correlation with Bennett's Logical Depth LD(s), other than what's predicted by the theory (shallow and non-random strings have low complexity under both measures). The agreement between the theory and the numerical calculations shows that despite the undecidability of these theoretical measures, the rate of convergence of approximations is stable enough to devise some applications. We announce a Beta version o...
[Ver más]
Cita: Soler Toscano, F., Zenil, H., Delahaye, J. y Gauvrit, N. (2013). Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures. Computability, 2 (2), 125-140.
Tamaño: 672.0Kb
Formato: PDF

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

DOI: 10.3233/COM-13019

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Atribución-NoComercial-SinDerivar 4.0 Internacional

Este registro aparece en las siguientes colecciones