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

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

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 compre...

書目詳細資料
Main Authors:	Soler−Toscano, F, Zenil, H, Delahaye, J, Gauvrit, N
格式:	Journal article
出版:	Public Library of Science 2014

相似書籍

Fractal Dimension of Space−time Diagrams and the Runtime Complexity of Small Turing Machines
由: Joosten, J, et al.
出版: (2013)

On the Kolmogorov−Chaitin Complexity for short sequences
由: Delahaye, J, et al.
出版: (2007)

The second quantized quantum Turing machine and Kolmogorov complexity
由: Rogers, C, et al.
出版: (2008)

Algorithmic complexity for short binary strings applied to psychology: a primer
由: Gauvrit, N, et al.
出版: (2013)

Program−size versus Time complexity‚ Slowdown and speed−up phenomena in the micro−cosmos of small Turing machines
由: Soler−Toscano, H
出版: (2010)

Natural Scene Statistics Mediate the Perception of Image Complexity
由: Gauvrit, N, et al.
出版: (2014)

Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
由: Soler−Toscano, F, et al.
出版: (2013)

Turing patterns with Turing machines: emergence and low−level structure formation
由: Zenil, H
出版: (2013)

Algorithmic complexity for psychology: A user−friendly implementation of the coding theorem method
由: Gauvrit, N, et al.
出版: (2015)

Second quantized Kolmogorov complexity
由: Rogers, C, et al.
出版: (2008)

An introduction to kolmogorov complexity and its applications /
由: 221728 Li, Ming, et al.
出版: (2008)

Kolmogorov in perspective /
由: American Mathematical Society, et al.
出版: (2000)

On Kolmogorov complexity and the costs of carrying out strategies
出版: (2000)

Beyond Turing's Machines
由: Hodges, A
出版: (2012)

Turing machines [filem]
出版: (1972)

Turing machines [kasetvideo]
出版: (1972)

Kolmogorov basic graphs and their application in network complexity analysis
由: Farzaneh, A, et al.
出版: (2021)

Generalist predator dynamics under Kolmogorov versus non-Kolmogorov models
由: Xu, Y, et al.
出版: (2019)

Kolmogorov's heritage in mathematics /
由: Charpentier, Eric, et al.
出版: (2007)

Correlation of automorphism group size and topological properties with program−size complexity evaluations of graphs and complex networks
由: Zenil, H, et al.
出版: (2014)

Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks
由: Zenil, H, et al.
出版: (2014)

REPRESENTING THE KNOWLEDGE OF TURING-MACHINES
由: Shin, H, et al.
出版: (1994)

Turing machines and functions [kasetvideo]
出版: (1973)

Turing machines and functions [filem]
出版: (1973)

The annotated turing : a guided tour through alan turing's historic paper on computability and the turing machine /
由: 451378 Petzold, Charles
出版: (2008)

Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness
由: Delahaye, J, et al.
出版: (2012)

Image characterization and classification by physical complexity
由: Zenil, H, et al.
出版: (2012)

A relatively small turing machine whose behavior is independent of set theory
由: Yedidia, Adam
出版: (2016)

Turing Machine / Nordin Abu Bakar
出版: (1992)

Simulations Amond Multidimensional Turing Machines
由: Loui, Michael Conrad
出版: (2023)

Turing machines and post systems [filem]
出版: (1973)

Differential Kolmogorov equations for transiting processes
由: Désilles, Gaël, 1971-
出版: (2009)

Kolmogorov-Smirnov like test for time-frequency Fourier spectrogram analysis in LISA Pathfinder
由: Ferraioli, L, et al.
出版: (2015)

Turing pattern outside of the Turing domain
由: Flach, E, et al.
出版: (2006)

How to Run Turing Machines on Encrypted Data
由: Goldwasser, Shafi, et al.
出版: (2014)

Space-Bounded Simulation of Multitape Turing Machines
由: Adleman, Leonard M., et al.
出版: (2023)

Hypercomputation: computing more than the Turing machine
由: Ord, T
出版: (2021)

On metric temporal logic and faulty turing machines
由: Ouaknine, J, et al.
出版: (2006)

Global stability and repulsion in autonomous Kolmogorov systems
由: Hou, Zhanyuan, et al.
出版: (2015)

Uji Kolmogorov-Smirnov dua sampel tersensor
由: , DWIDAYATI, Nurkaromah, et al.
出版: (1999)