Coding Theorem Method API

H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit

This is a Mathematica notebook that allows access to the Algorithmic Nature group API that provides approximations to Kolmogorov complexity by means of approximations to Levin’s universal distribution through frequency distribution of small Turing machines. (see citation info at the bottom)

Main functions

AlgorithmicProbabilityApproximation[s_String, D_: "d5"] := If[DigitQ[StringTake[#,1]],ToExpression[#],#] &@Import["http://complexitycalculator.com/k.php?s=" <> s <> "&d=" <> D]

KolmogorovComplexityApproximation[s_String, D_: "d5"] := If[DigitQ[StringTake[#,1]],-Log[2,ToExpression[#]],#] &@Import["http://complexitycalculator.com/k.php?s=" <> s <> "&d=" <> D]

Algorithmic probability

Retrieve the output probability of s in the distribution d5  (in the papers D(5) or D(5,2), that is all Turing machines with 5 states and 2 symbols).

s = "11011101";

Exact values are in the form of fractions

AlgorithmicProbabilityApproximation[s, "d5"]

As a probability the result is between 0 and 1.

N@AlgorithmicProbabilityApproximation[s, "d5"]

Kolmogorov Complexity

Retrieve the best current approximation to the Kolmogorov complexity of a string s (in bits).

KolmogorovComplexityApproximation[s]

N@KolmogorovComplexityApproximation[s]

If no distribution is specified it uses by default the distribution d5.

If a string does not occur in a distribution (because it cannot occur or because it is too long to occur) then the function retrieves a message with Mathematica head expression of type String.

KolmogorovComplexityApproximation["1010110010100101010"]

Head@KolmogorovComplexityApproximation["1010110010100101010"]

KolmogorovComplexityApproximation["foo"]

If the second parameter is not a valid distribution then it retrieves an error message with Mathematica head expression of type String)

N@KolmogorovComplexityApproximation[s, "bar"]

Retrieve the best current approximation of a string s using a specific approximation to the universal distribution. (e.g. d5 is the distribution from 5-state 2-symbol one-dimensional Turing machines)

N@KolmogorovComplexityApproximation[s, "d5"]

Compare the Kolmogorov complexity of two short strings

s="010101";

KolmogorovComplexityApproximation[s, "d5"]>KolmogorovComplexityApproximation[StringJoin[ToString/@RandomInteger[{0,1},6]], "d5"]

More data covering longer strings and other non-binary and d-dimensional objects will be available soon.

Citation Info

Cite this work as follows "API developed by the Algorithmic Nature group" using the Coding Theorem method as described in:

F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit, Calculating Kolmogorov Complexity from the Frequency Output Distributions of Small Turing Machines,  arXiv:1211.1302 [cs.IT], 2012. (url: http://arxiv.org/abs/1211.1302)