Journal article icon

Journal article

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

Abstract:

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 all Σ11n=1 2n binary strings o...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Public Library of Science
Journal:
PLoS ONE More from this journal
Volume:
9
Issue:
5
Article number:
e96223
Publication date:
2014-01-01
DOI:
EISSN:
1932-6203
ISSN:
1932-6203
UUID:
uuid:f8a05f5d-429a-4f19-b491-4a1800cce1af
Local pid:
cs:9297
Deposit date:
2015-03-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP