Mostrar el registro sencillo del ítem

Artículo

dc.creatorSoler Toscano, Fernandoes
dc.creatorZenil, Hectores
dc.date.accessioned2018-03-09T08:05:11Z
dc.date.available2018-03-09T08:05:11Z
dc.date.issued2017
dc.identifier.citationSoler Toscano, F. y Zenil, H. (2017). A computable measure of algorithmic probability by finite approximations with an application to integer sequences. Complexity, 2017
dc.identifier.issn1076-2787 (impreso)es
dc.identifier.issn1099-0526 (electrónico)es
dc.identifier.urihttps://hdl.handle.net/11441/70884
dc.description.abstractGiven 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-statistical patterns, and we report interesting correlations with textual, function and program description lengths of the said sequences.es
dc.description.sponsorshipSwedish Research Council 2015-05299es
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherHindawi/Wileyes
dc.relation.ispartofComplexity, 2017
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectInteger sequenceses
dc.subjectAlgorithmic probabilityes
dc.titleA computable measure of algorithmic probability by finite approximations with an application to integer sequenceses
dc.typeinfo:eu-repo/semantics/articlees
dcterms.identifierhttps://ror.org/03yxnpp24
dc.type.versioninfo:eu-repo/semantics/publishedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Filosofía y Lógica y Filosofía de la Cienciaes
dc.relation.projectID2015-05299es
dc.relation.publisherversionhttps://doi.org/10.1155/2017/7208216es
dc.identifier.doi10.1155/2017/7208216es
dc.contributor.groupUniversidad de Sevilla. HUM609: Grupo de Lógica, Lenguaje e Informaciónes
idus.format.extent10 p.es
dc.journaltitleComplexityes
dc.publication.volumen2017es

FicherosTamañoFormatoVerDescripción
computable_measure_soler.pdf2.791MbIcon   [PDF] Ver/Abrir  

Este registro aparece en las siguientes colecciones

Mostrar el registro sencillo del ítem

http://creativecommons.org/licenses/by-nc-nd/4.0/
Excepto si se señala otra cosa, la licencia del ítem se describe como: http://creativecommons.org/licenses/by-nc-nd/4.0/