Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures

Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures∗ Fernando Soler-Toscano1, Hector Zenil2† , Jean-Paul Delahaye3 and Nicolas Gauvrit4 1Grupo de L´ogica, Lenguaje e Informaci´on, Universidad de Sevilla, Spain. 2Department of Computer Science, University of Sheffield, UK. 3Laboratoire d’Informatique Fondamentale de Lille, France. 4LDAR, Universit´e de Paris VII, Paris, France. Abstract We show that real-value approximations of Kolmogorov-Chaitin (Km) using the algorithmic Coding theorem as calculated from the output frequency of a large set of small deterministic Turing machines with up to 5 states (and 2 symbols), is in agreement with the number of instructions used by the Turing machines producing s, which is consistent with strict integer-value program-size complexity. Nevertheless, Kmproves to be a finer-grained measure and a potential alternative approach to lossless compression algorithms for small entities, where compression fails. We also show that neither Km nor the number of instructions used shows any correlation with Bennett’s Logical Depth LD(s) other than what’s predicted by the theory. The agreement between theory and numerical calculations shows that despite the undecidability of these theoretical measures, approximations are stable and meaningful, even for small programs and for short strings. We also announce a first Beta version of an Online Algorithmic Complexity Calculator (OACC), based on a combination of theoretical concepts, as a numerical implementation of the Coding Theorem Method. Keywords: Coding Theorem Method; Kolmogorov complexity; Solomonoff-Levin algorithmic probability; program-size complexity; Bennett’s Logical Depth; small Turing machines. ∗Algorithmic Nature Group URL: http://www.algorithmicnature.org. Online Algorithmic Complexity Calculator (OACC) URL: http://www.complexitycalculator.com. †Corresponding author: [email protected] 1 arXiv:1211.4891v3 [cs.IT] 13 Feb 2013 1 Introduction Kolmogorov complexity (also known as Kolmogorov-Chaitin or programsize complexity) is recognized as a fundamental concept, but it is also often thought of as having little or no applicability because it is not possible to provide stable numerical approximations for finite—particularly short—strings by using the traditional approach, namely lossless compression algorithms. We advance a method that can overcome this limitation, and which, though itself limited in ways both theoretical and numerical, nonetheless offers a means of providing sensible values for the complexity of short strings, complementing the traditional lossless compression method that works well for long strings. This is done at the cost of massive numerical calculations and through the application of the Coding theorem from algorithmic probability theory that relates the frequency of production of a string to its Kolmogorov complexity. Bennett’s logical depth, on the other hand, is a measure of the complexity of strings that, unlike Kolmogorov complexity, measures the organized information content of a string. In [23] an application inspired by the notion of logical depth was reported in the context of the problem of image classification. However, the results in this paper represent the first attempt to provide direct numerical approximations of logical depth. The independence of the two measures– Kolmogorov complexity and logical depth– which has been established theoretically, is also numerically tested and confirmed in this paper. Our work is in agreement with what the theory predicts, even for short strings–despite the limitations of our approach. Our attempt to apply these concepts to practical problems (detailed in a series of articles (see e.g. [13,23])) is novel, and they are indeed proving to have interesting applications where evaluations of the complexity of finite short strings are needed [22]. In Sections 2,3,4and 5, we introduce the measures, tools and formalism used for the method described in Section 6. In Section 7, we report the numerical results of the evaluation and analysis of the comparisons among the various measures, particularly the connection between number of instructions, integer valued program-size complexity, Kolmogorov complexity approximated by means of the Coding Theorem method, and logical depth. 2 2 Kolmogorov-Chaitin complexity When researchers have chosen to apply the theory of algorithmic information (AIT), it has proven to be of great value despite initial reservations [7]. It has been successfully applied, for example, to DNA false positive repeat sequence detection in genetic sequence analysis [18], in distance measures and classification methods [8], and in numerous other applications [17]. This effort has, however, been hamstrung by the limitations of compression algorithms– currently the only method used to approximate the Kolmogorov complexity of a string–given that this measure is not computable. Central to AIT is the basic definition of plain algorithmic (Kolmogorov- Chaitin or program-size) complexity [15,6]: KU(s) = min{|p|, U(p) = s}(1) Where Uis a universal Turing machine and pthe program that, running on U, produces s. Traditionally, the way to approach the algorithmic complexity of a string has been by using lossless compression algorithms. The result of a lossless compression algorithm applied to sis an upper bound of the Kolmogorov complexity of s. Short strings, however, are difficult to compress in practice, and the theory does not provide a satisfactory solution to the problem of the instability of the measure for short strings. The invariance theorem, however, guarantees that complexity values will only diverge by a constant c(e.g. the length of a compiler or a translation program). Invariance Theorem ([4,17]): If U1and U2are two universal Turing machines, and KU1(s) and KU2(s) the algorithmic complexity of sfor U1 and U2respectively, there exists a constant csuch that: |KU1(s)−KU2(s)|< c (2) Hence the longer the string, the less important cis (i.e. the choice of programming language or universal Turing machine). However, in practice ccan be arbitrarily large, thus having a very great impact on the stability of Kolmogorov complexity approximations for short strings. 3 Bennett’s Logical Depth A measure of the structural complexity (i.e. richness of structure and organization) of a string can be arrived at by combining the notions of algorithmic 3 information and time complexity. According to the concept of logical depth [1,2], the complexity of a string is best defined by the time that an unfolding process takes to reproduce the string from its shortest description. While Kolmogorov complexity is related to compression length, Bennett’s logical depth is related to decompression time. A typical example that illustrates the concept of logical depth, underscoring its potential as a measure of complexity, is a sequence of fair coin tosses. Such a sequence would have a high information content (Kolmogorov complexity) because the outcomes are random, but it would have no structure because it is easily generated. The string 1111. . . 1111 would be equally shallow as measured by logical depth. Its compressed version, while very small, requires little time to decompress into the original string. In contrast, the binary expansion of the mathematical constant πis not shallow, because though highly compressible and hence having a low Kolmogorov complexity, it requires non-negligible computational time to produce arbitrary numbers of digits from its shortest program (or indeed from any short program computing the digits of π). A detailed explanation pointing out the convenience of the concept of logical depth as a measure of organized complexity as compared to plain algorithmic complexity, which is what is usually used, is provided in [10]. For finite strings, one of Bennett’s formal approaches to the logical depth of a string is defined as follows: Let sbe a string and da significance parameter. A string’s depth at significance dis given by LDd(s) = min{t(p) : (|p|−|p∗|< d)and (U(p) = s)}(3) with |p∗|the length of the shortest program for s, (therefore K(s)). In other words, LDd(s) is the least time trequired to compute sfrom a dincompressible program pon a universal Turing machine U. Each of the three linked definitions of logical depth provided in [1] comes closer to a definition in which near-shortest programs are taken into consideration. In this experimental approach we make no such distinction among significance parameters, so we will denote the logical depth of a string s simply by LD(s). Like K(s), LD(s) as a function of sis uncomputable. A novel feature of this research is that we provide exact numerical approximations for both measures– K(s) and LD(s)– for specific short s, allowing a direct comparison. This was achieved by running a large set of random Turing machines and finding the smallest and fastest machines generating each output string. 4 Hence these approximations are deeply related to another important measure of algorithmic information theory. 4 Solomonoff-Levin Algorithmic Probability The algorithmic probability (also known as Levin’s semi-measure) of a string s, is a measure that describes the expected probability of a random program prunning on a universal (prefix-free 1) Turing machine Uproducing s. Formally [20,16,6], m(s) = Σp:U(p)=s1/2|p|(4) i.e. the sum over all the programs for which Uwith poutputs sand halts. Levin’s semi-measure m(s) defines a distribution known as the Universal Distribution [14]. It is important to notice that the value of m(s) is dominated by the length of the smallest program p(when the denominator of mreaches its largest value). The length of the smallest program p that produces the string sis K(s). The semi-measure m(s) is therefore also uncomputable, because for every s,m(s) requires the calculation of 2−K(s), involving K, which is itself uncomputable. An extension of m(s) to non-binary alphabets is natural. More formally, m2(s) can be associated with the original definition for binary strings. However, one may want to extend m2(s) to mk(s), in which case for every k, the function s→mk(s) is semi-computable (for the same reason that s→m2(s) is uncomputable). An alternative [13] to the traditional use of compression algorithms to approximate Kcan be derived from a fundamental theorem that establishes the exact connection between m(s) and K(s). Coding Theorem (Levin [16]): | − log2m(s)−K(s)|< c (5) This theorem posits that if a string has many long descriptions it also has a short one. It elegantly connects frequency to complexity, more specifically the frequency (or probability) of occurrence of a string with its algorithmic (Kolmogorov) complexity. The Coding theorem implies that [9,4] one can calculate the Kolmogorov complexity of a string from its frequency [12,11, 21,13], simply rewriting the formula as: 1The group of valid programs forms a prefix-free set, that is, no element is a prefix of any other, a property necessary to keep 0 < m(s)<1. For details see [4]). 5 Km(s) = −log2m(s) + O(1) (6) Where we will use Kmto indicate that Khas been approximated by means of mthrough the Coding theorem. An important property of m as a semi-measure is that it dominates any other effective semi-measure µ, because there is a constant cµsuch that for all s,m(s)≥cµµ(s). For this reason m(s) is often called a Universal Distribution [14]. 5 Deterministic Turing machines The ability of a universal Turing machine to simulate any algorithmic process2has motivated and justified the use of universal Turing machines as the language framework within which definitions and properties of mathematical objects are given and studied. However, it is important to describe the formalism of a Turing machine, because exact values of algorithmic probability for short strings will be approximated under this model, both for K(s)– through m(s) (denoted by Km), and for K(s)–in terms of the number of instructions used by the smallest Turing machine producing s. Consider a Turing machine Twith alphabet Σ = {0,1}symbols, {1,2, . . . , n}states and an additional halting state denoted by 0 (as defined by Rado in his original Busy Beaver paper [19]). At the outset the Turing machine is in its initial state 1. The machine runs on a 2-way unbounded tape. Its behavior is determined by the transition function δT. So, at each step: 1. the machine’s current “state” (instruction) s; and 2. the tape symbol the machine’s head is scanning k define the transition δT(s, k)=(s0, k0, d) with 1. a unique symbol k0to write (the machine can overwrite a 1 on a 0, a 0 on a 1, a 1 on a 1, and a 0 on a 0); 2. a direction dto move in: −1 (left), 1 (right) or 0 (none, when halting); and 3. a state s0to transition into (which may be the same as the one it was in). 2Under Church’s hypothesis. 6 The machine halts if and when it reaches the special halt state 0. There are (4n+ 2)2nTuring machines with nstates and 2 symbols according to the formalism described above, as there are 2nentries in the transition table and any of them may have 4n+ 2 possible instructions: there are 2 halting instructions (writing ‘0’ and ‘1’) and 4nnon-halting instructions (2 movements, 2 possible symbols to write and nstates). The output string is taken from the number of contiguous cells on the tape the head of the halting n-state machine has gone through. A Turing machine is considered to produce an output string only if it halts. The output is what the machine has written on the tape. 6 The Coding Theorem Method In order to arrive at an approximation of m(s), a method based on the Coding theorem was advanced in [13]. It is captured in the following function. Let Tbe a Turing machine in (n, m) with empty input. Then: D(n, m)(s) = |{T∈(n, m) : Tproduces s}| |{T∈(n, m) : Thalts }| (7) Where |E|denotes the number of elements of E. Let mbe fixed. It has been proved [21,13] that the function n→D(n, m) is non-computable (due to the denominator). However, D(n, m) for fixed and small values n and mis computable for values of the Busy Beaver problem [19] that are known. For n= 4, for example, the Busy Beaver function Stells us that S(4,2) = 107 [3], so given a Turing machine with 4 states running on a blank tape that hasn’t halted after 107 steps, we know it will never stop. More generally, for every string s(with alphabet {0,1, . . . , m −1}) one can compute a sequence D(n, m)(s, t) which converges to D(n, m)(s) when t→ ∞. For D(n, m)(s, t) we compute for tsteps all m-Turing machines with nstates (there is a finite number of them) and compute the quotient for D(n, m)(s) for machines that halted before tsteps. Since D(n, m)(s, t) converges for every sto D(n, m)(s) (mfixed, nfixed, sfixed), the value of D(n, m)(t) converges for fixed mand n. In this specific sense D(n, m) is approachable, even if D(n, m)(s, t) as a function of increasing time tmay increase when a machine produces s, or decrease when a machine halts without producing s. By the invariance theorem (Eq. 2) and the Coding theorem (Eq. 6), D(n, m)(s) is guaranteed to converge to m(s). Exact values of D(n, m)(s, t) were previously calculated [21,13] for m= 2 symbols and n= 1,...,4 states for which the Busy Beaver val- 7 ues are known. That is, a total of 36, 10 000, 7 529 536 and 11 019 960 576 Turing machines respectively. The distributions were very stable and are proving to be capable of delivering applications that are also in agreement with results from lossless compression algorithms [22] for boundary cases (where both methods can be applied), hence validating the utility of both methods (compression being largely validated by its plethora of applications and by the fact that it achieves an approximation of K, see e.g. [17]). The chief advantage of the Coding Theorem method, however, is that it is capable of dealing with short entities (unlike compression algorithms, which are designed for large entities). There are 26 559 922 791 424 Turing machines with 5 states and 2 symbols, and the values of Busy Beaver functions for these machines are unknown. In what follows we describe how we proceeded. Calculating D(5,2) is an improvement on our previous numerical evaluations and provides a larger data set to work with, allowing us to draw more significant statistical conclusions vis-`a-vis the relation between these calculations and strict integer value program-size complexity, as well as to make a direct comparison to Bennett’s logical depth. 6.1 Reduction techniques We did not run all the Turing machines with 5 states to produce D(5,2), because one can take advantage of symmetries and anticipate some of the behavior of the Turing machines directly from their transition tables without actually running them (this is impossible generally due to the halting problem, but some reductions are possible). If (n, m) is the set of Turing machines with nstates and msymbols, as defined above, we reduce it to: Red(n, m) = {T∈(n, m)|δT(1,0) = (s, k, 1), s /∈ {0,1}, k ∈ {0,· · · , m−1}} where δTis the transition function of T. So Red(n, m) is a subset of (n, m), with machines with the transition corresponding to initial state 1 and symbol 0 (this is the initial transition in a ‘0’-filled blank tape) moving to the right and changing to a state different from the initial and halting ones. For machines with two symbols, |Red(n, 2)|= 2(n−1)(4n+ 2)2n−1 as there are 2(n−1) different initial transitions (the machine can write ‘0’ or ‘1’ and move to one of the n−1 states in {2, . . . , n}), and for the other 2n−1 transitions there are 4n+ 2 possibilities, as in (n, m). 8 After running Red(n, 2) on a ‘0’-filled tape, the procedure for completing the output strings so that they reach the frequency they have in (n, m) is: •For every T∈Red(n, 2), –If Thalts and produces the output string s, add one occurrence of rev(s), the reverse of s. –If Tdoes not halt, count another non-halting machine. These two completions add the output (or number of non-halting machines) of 2(n−1)(4n+ 2)2n−1new machines, one for each machine in Red(n, 2). These new machines are left-right symmetric to the machines in Red(n, 2). Formally, this is the set {T0|T∈Red(n, 2), δT0(s, k)=(s0, k0,−d) iff δT(s, k)=(s0, k0, d),for all sand k)} When the original machine halts, its symmetric counterpart halts too and produces the reversed strings, and if the original machine does not halt, neither does the symmetric machine. This way we consider the output of all machines with the initial transition moving to the left and to a state not in {0,1}. •Include (4n+ 2)2n−1occurrences of string “1”. This corresponds to the machines writing ‘1’ and halting at the initial transition. There is just one possible initial transition for these machines (move to the halting state, write ‘1’ and remain in the initial cell). The other 2n−1 transitions can have any of the 4n+ 2 possible instructions. •Include (4n+ 2)2n−1occurrences of string “0”. This is justified as above, for machines writing ‘0’ and halting at the initial transition. •Include 4(4n+ 2)2n−1additional non-halting machines, corresponding to machines remaining in the initial state in the initial transition (these machines never halt, as they remain forever in the initial state). There are 4 initial transitions of this kind, as the machine can write 2 different symbols and move in 2 possible directions. If we sum |Red(n, 2)|and the machines considered above, having completed them in the manner described, we get the output corresponding to the (4n+ 2)2nmachines in (n, 2). Moreover, we need the output of those machines starting with a ‘0’-filled tape and with a ‘1’-filled tape. But we do not run any machine twice, as 9 25 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 500 0 10 20 30 40 Figure 4: LD and Km(distribution). The vertical axis shows the distribution of Kmfor each runtime interval (horizontal axis). There is no correlation between LD and Kmother than the expected one, viz. that both measures identify simple objects as objects of low complexity. 16 We have partitioned the runtime space from 1 to 500 (our runtime bound) into 20 groups of equal length (25 steps). In order to explore the relation of Kmto Bennett’s LD we are interested in the values of Kmfor the strings in each group. Fig. 3shows the minimum, mean and maximum Km values for each of the runtime groups. The same information is in Table 1. The distribution of Kmvalues for the different groups is shown in Fig. 4. For each interval, the maximum runtime is shown on the horizontal axis. Runtime Min KmMean KmMax Km 1-25 2.51428 25.6049 34.3638 26-50 21.0749 34.5849 39.0642 51-75 25.6104 37.0796 39.0642 76-100 26.8569 37.8125 39.0642 101-125 30.3777 38.1337 39.0642 126-150 32.5096 38.2150 39.0642 151-175 32.6048 38.3208 39.0642 176-200 32.3093 38.2850 39.0642 201-225 34.1573 38.4213 39.0642 226-250 33.9767 38.3846 39.0642 251-275 33.3093 38.4249 39.0642 276-300 33.3363 38.2785 39.0642 301-325 36.7423 38.5963 39.0642 326-350 32.8943 38.2962 39.0642 351-375 32.8163 38.3742 39.0642 376-400 36.0642 38.6081 39.0642 401-425 33.2062 38.4035 39.0642 426-450 33.1100 38.5543 39.0642 451-475 37.0642 38.7741 39.0642 476-500 36.0642 38.6147 39.0642 Table 2: Extreme and mean Kmvalues for different runtime intervals. We now provide some examples of the discordance between Kmand LD. “0011110001011” is a string with high Kmand low LD. Fig. 5shows the transition table of the smallest machine found producing this string. The runtime is low–just 29 steps (of the 99 584 different strings found in our sample, only 3 360 are produced in fewer steps), but it uses 10 instructions and produces a string with complexity 39.0642. It is the greatest complexity we have calculated for Km. Fig. 6shows the execution of the machine. On the other hand, “(10)201” is a string with high LD but a low Km 17 States: H1L, H2L, H3L, H4L, H5L, HhaltingL Figure 5: Transitions of a sample machine producing “0011110001011”. Figure 6: Execution of the machine producing “0011110001011”. With a low runtime, this sample machine produces a string with high complexity. 18 value. Fig. 7shows the transition table of the machine found producing this string, and Fig. 8depicts the execution. The machine uses 9 instructions and runs for 441 steps (only 710 strings out of the 99 584 strings in our sample require more time) but its Kmvalue is 33.11. This is a low complexity if we consider that in Kmthere are 99 608 strings and that 90 842 are more complex than this one. States: H1L, H2L, H3L, H4L, H5L, HhaltingL Figure 7: Transition table of a sample machine producing “(10)201”. Figure 8: Execution of the sample machine producing “(10)201”. With a high runtime, it produces a string with low complexity. We may rate the overall strength of the relation between Kmand LD by the correlation rKm,LD = 0.41, corresponding to a medium positive link. As we previously mentioned, however, the fact that the length Lof the strings is linked with both variables may bias our interpretation. A more relevant measure is thus rKm,LD.L =−0.06, a slight negative but with no significant value between Kmand LD once Lis controlled. 19 8 Concluding remarks The results in this paper are important because these measures can be better studied and understood under a specific but widely known general formalism. What we have found is very interesting because it is what one would wish in the best case scenario, stable and reasonable distributions rather than chaotic and unstable ones. The results also suggest that these measures can be applied even if numerically approximated using a specific model of computation. For example, as we expected, the Kolmogorov-Chaitin complexity evaluated by means of Levin’s Coding Theorem from the output distribution of small Turing machines correlates with the number of instructions used but not with logical depth. Logical depth also yields a measure that is different from the measure obtained by considering algorithmic complexity (K) alone, and this investigation proves that all these three measures (Kolmogorov-Chaitin Complexity, Solomonoff-Levin Algorithmic Probability and Bennett’s Logic Depth) are consistent with theoretical expectations. Kas a measure of program-size complexity is traditionally expected to be an integer (the length of a program in bits), but when evaluated through algorithmic probability using the Coding theorem it retrieves non-integer values (still bits). These results confirm the utility of non-integer values in the approximation of the algorithmic complexity of short strings, as they provide finer values with which one can tell apart small differences among short strings–which also means one can avoid the longer calculations that would be necessary in order to tell apart the complexity of very small objects if only integer values were allowed. Thus it also constitutes a complementary and alternative method to compression algorithms. An On-line Algorithmic Complexity Calculator (or OACC) is now available at http://www.complexitycalculator.com. It represents a long-term project to develop an encompassing universal tool implementing some of the measures and techniques described in this paper. It is expected to be expanded in the future as it currently only implements numerical approximations of Kolmogorov complexity and Levin’s semi-measure for short binary strings. More measures, more data and better approximations will be gradually incorporated in the future, covering a wider range of objects, such as longer binary strings, non-binary strings and multidimensional arrays (such as images). 20 References [1] C.H. Bennett, Logical Depth and Physical Complexity in Rolf Herken (ed) The Universal Turing Machine–a Half-Century Survey, Oxford University Press 227–257, 1988. [2] C.H. Bennett, How to define complexity in physics and why. In Complexity, entropy and the physics of information. Zurek, W. H., Addison- Wesley, Eds. SFI studies in the sciences of complexity, p 137-148, 1990. [3] A.H. Brady, The determination of the value of Rado’s noncomputable function Sigma(k) for four-state Turing machines, Mathematics of Computation 40 (162): 647–665, 1983. [4] C.S. Calude, Information and Randomness, Springer, 2002. [5] C.S. Calude and M.A. Stay, Most Programs Stop Quickly or Never Halt, Advances in Applied Mathematics, 40, 295-308, 2008. [6] G.J. Chaitin, On the length of programs for computing finite binary sequences: Statistical considerations, Journal of the ACM, 16(1):145– 159, 1969. [7] G.J. Chaitin. From Philosophy to Program Size, 8th. Estonian Winter School in Computer Science, Institute of Cybernetics, Tallinn, 2003. [8] R. Cilibrasi, P. Vitanyi, Clustering by Compression, IEEE Transactions On Information Theory, 51, 4, 1523–1545, 2005. [9] T.M. Cover and J.A. Thomas, Information Theory, J. Wiley and Sons, 2006. [10] J.P. Delahaye, Complexit´e al´eatoire et complexit´e organis´ee, Editions Quae, 2009. [11] J-P. Delahaye, H. Zenil, Towards a stable definition of Kolmogorov- Chaitin complexity, arXiv:0804.3459, 2007. [12] J-P. Delahaye and H. Zenil, On the Kolmogorov-Chaitin complexity for short sequences. In C. Calude (ed.), Randomness and Complexity: From Leibniz to Chaitin, World Scientific, 2007. [13] J.-P. Delahaye & H. Zenil, Numerical Evaluation of the Complexity of Short Strings: A Glance Into the Innermost Structure of Algorithmic Randomness, Applied Math. and Comp., 2012. 21 [14] W. Kircher, M. Li, and P. Vitanyi, The Miraculous Universal Distribution, The Mathematical Intelligencer, 19:4, 7–15, 1997. [15] A.N. Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information and Transmission, 1(1):1–7, 1965. [16] L. Levin, Laws of information conservation (non-growth) and aspects of the foundation of probability theory., Problems in Form. Transmission 10. 206—210, 1974. [17] M. Li, P. Vit´anyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 2008. [18] ´ E. Rivals, M. Dauchet, J.-P. Delahaye, O. Delgrange, Compression and genetic sequence analysis., Biochimie, 78, pp 315-322, 1996. [19] T. Rad´o, On non-computable functions, Bell System Technical Journal, Vol. 41, No. 3, pp. 877–884, 1962. [20] R.J. Solomonoff, A formal theory of inductive inference: Parts 1 and 2. Information and Control, 7:1–22 and 224–254, 1964. [21] H. Zenil, Une approche exp´erimentale `a la th´eorie algorithmique de la complexit´e, dissertation in fulfilment of the degree of Doctor in Computer Science (jury members: J.-P. Delahaye and C.S. Calude, G. Chaitin, S. Grigorieff, P. Mathieu and H. Zwirn), Universit´e de Lille 1, 2011. [22] H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit, Two- Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility, arXiv:1212.6745 [cs.CC]. [23] H. Zenil, J.-P. Delahaye and C. Gaucherel, Image Information Content Characterization and Classification by Physical Complexity, Complexity, vol. 17–3, pages 26–42, 2012. 22