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

A computable measure of algorithmic probability by finite approximations with an application to integer sequences

Opened Access A computable measure of algorithmic probability by finite approximations with an application to integer sequences

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Soler Toscano, Fernando
Zenil, Hector
Departamento: Universidad de Sevilla. Departamento de Filosofía y Lógica y Filosofía de la Ciencia
Fecha: 2017
Publicado en: Complexity, 2017
Tipo de documento: Artículo
Resumen: Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity, and that lossless compression algorithms fall short at characterizing patterns other than statistical ones not different to entropy estimations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure m calculated from the output distribution of small Turing machines. We introduce and justify finite approximations mk that have been used in some applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both m and mk and compare them to Levin's Universal Distribution. We provide error estimations of mk with respect to m. Finally, we present an application to integer sequences from the Online Encyclopedia of Integer Sequences which suggests that our AP-based measures may characterize non-statisti...
[Ver más]
Cita: Soler Toscano, F. y Zenil, H. (2017). A computable measure of algorithmic probability by finite approximations with an application to integer sequences. Complexity, 2017
Tamaño: 2.791Mb
Formato: PDF

URI: https://hdl.handle.net/11441/70884

DOI: 10.1155/2017/7208216

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