skip to main content
Idioma:
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

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

Soler-Toscano, Fernando ; Zenil, Hector ; Delahaye, Jean-Paul ; Gauvrit, Nicolas Dehmer, Matthias

PloS one, 2014-05, Vol.9 (5), p.e96223-e96223 [Periódico revisado por pares]

United States: Public Library of Science

Texto completo disponível

Citações Citado por
  • Título:
    Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines
  • Autor: Soler-Toscano, Fernando ; Zenil, Hector ; Delahaye, Jean-Paul ; Gauvrit, Nicolas
  • Dehmer, Matthias
  • Assuntos: Algorithms ; Analysis ; Applied mathematics ; Complexity ; Compression ; Computer and Information Sciences ; Computer science ; Data processing ; Error detection ; Lossless ; Mathematical analysis ; Medicin och hälsovetenskap ; Physical Sciences ; Probability ; Research methodology ; Robustness (mathematics) ; Social Sciences ; Statistical analysis ; Statistical Distributions ; Strings ; Turing machines
  • É parte de: PloS one, 2014-05, Vol.9 (5), p.e96223-e96223
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
    Competing Interests: The authors have declared that no competing interests exist.
    Conceived and designed the experiments: HZ FS JPD. Performed the experiments: FS HZ NG. Analyzed the data: HZ NG FS JPD. Contributed reagents/materials/analysis tools: HZ FS NG. Wrote the paper: HZ FS JPD NG.
  • Descrição: 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 Σ(n=1)(11) 2(n) binary strings of length n<12 and for most strings of length 12≤n≤16 by running all ~2.5 x 10(13) Turing machines with 5 states and 2 symbols (8 x 22(9) 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 range of applications, and to provide insight into the question of complexity calculation of finite (and short) strings. Additional material can be found at the Algorithmic Nature Group website at http://www.algorithmicnature.org. An Online Algorithmic Complexity Calculator implementing this technique and making the data available to the research community is accessible at http://www.complexitycalculator.com.
  • Editor: United States: Public Library of Science
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.