5092:) must be specified, so that "program" means a program for this universal machine. A random string in this sense is "incompressible" in that it is impossible to "compress" the string into a program that is shorter than the string itself. For every universal computer, there is at least one algorithmically random string of each length. Whether a particular string is random, however, depends on the specific universal computer that is chosen. This is because a universal computer can have a particular string hard-coded in itself, and a program running on this universal computer can then simply refer to this hard-coded string using a short sequence of bits (i.e. much shorter than the string itself).
4285:
5059:(i.e. it incorporates prior beliefs) and information-theoretic. It has the desirable properties of statistical invariance (i.e. the inference transforms with a re-parametrisation, such as from polar coordinates to Cartesian coordinates), statistical consistency (i.e. even for very hard problems, MML will converge to any underlying model) and efficiency (i.e. the MML model will converge to any true underlying model about as quickly as is possible). C.S. Wallace and D.L. Dowe (1999) showed a formal connection between MML and algorithmic information theory (or Kolmogorov complexity).
10751:
129:); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts. Kolmogorov complexity is the length of the ultimately compressed version of a file (i.e., anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. We discuss the incomputability of Kolmogorov complexity, which formal loopholes this leaves us with, recent approaches to compute or approximate Kolmogorov complexity, which approaches are problematic, and which approaches are viable.
11963:
11953:
7124:
20:
4330:. Most strings are incompressible, i.e. their Kolmogorov complexity exceeds their length by a constant amount. 9 compressible strings are shown in the picture, appearing as almost vertical slopes. Due to Chaitin's incompleteness theorem (1974), the output of any program computing a lower bound of the Kolmogorov complexity cannot exceed some fixed limit, which is independent of the input string
2007:
Kolmogorov, who was concerned with randomness of a sequence, while
Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientist
4342:), most strings are complex in the sense that they cannot be described in any significantly "compressed" way. However, it turns out that the fact that a specific string is complex cannot be formally proven, if the complexity of the string is above a certain threshold. The precise formalization is as follows. First, fix a particular
2003:
themselves. Solomonoff used this algorithm and the code lengths it allows to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information.
30:. Simply storing the 24-bit color of each pixel in this image would require 23 million bytes, but a small computer program can reproduce these 23 MB using the definition of the Mandelbrot set and the corner coordinates of the image. Thus, the Kolmogorov complexity of this image is much less than 23 MB in any pragmatic
2006:
When
Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority. For several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with
1582:
There are some description languages which are optimal, in the following sense: given any description of an object in a description language, said description may be used in the optimal description language with a constant overhead. The constant depends only on the languages involved, not on the
2271:
Take any program for the universal Turing machine used to define plain complexity, and convert it to a prefix-free program by first coding the length of the program in binary, then convert the length to prefix-free coding. For example, suppose the program has length 9, then we can convert it as
1368:
to be a Turing machine that comes with a prefix-free code, such that the Turing machine can read any string from the code in one direction, and stop reading as soon as it reads the last symbol. Afterwards, it may compute on a work tape and write to a write tape, but it cannot move its read-head
2002:
The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings
189:
The
Kolmogorov complexity can be defined for any mathematical object, but for simplicity the scope of this article is restricted to strings. We must first specify a description language for strings. Such a description language can be based on any computer programming language, such as
181:
description language (the sensitivity of complexity relative to the choice of description language is discussed below). It can be shown that the
Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself. Strings like the
3620:
This program iterates through all possible programs (by iterating through all possible strings and only considering those which are valid programs), starting with the shortest. Each program is executed to find the result produced by that program, comparing it to the input
1597:
In more technical terms, the first part of a description is a computer program (specifically: a compiler for the object's language, written in the description language), with the second part being the input to that computer program which produces the object as output.
5420:
1292:, simply by its own length. Stated in another way, it is as if we are using a termination symbol to denote where a word ends, and so we are not using 2 symbols, but 3. To fix this defect, we introduce the prefix-free Kolmogorov complexity.
5216:
of the information source. More precisely, the
Kolmogorov complexity of the output of a Markov information source, normalized by the length of the output, converges almost surely (as the length of the output goes to infinity) to the
2966:
1356:
in the set, neither is a prefix of the other. The benefit of a prefix-free code is that we can build a machine that reads words from the code forward in one direction, and as soon as it reads the last symbol of the word, it
4118:
with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of a
1228:
The main problem with plain complexity is that there is something extra sneaked into a program. A program not only represent for something with its code, but also represent its own length. In particular, a program
2771:
For the plain complexity, just write a program that simply copies the input to the output. For the prefix-free complexity, we need to first describe the length of the string, before writing out the string itself.
2330:
5263:
269:. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article, an informal approach is discussed.
3632:
tested will not terminate, e.g. if they contain infinite loops. There is no way to avoid all of these programs by testing them in some way before executing them due to the non-computability of the
636:
6451:
834:
166:
characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, i.e., "write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" which has
7110:
6908:
In other words, it is the probability that, given a uniformly random binary stream as input, the universal Turing machine would halt after reading a certain prefix of the stream, and output
5464:
If we have a halting oracle, then the
Kolmogorov complexity of a string can be computed by simply trying every halting program, in lexicographic order, until one of them outputs the string.
1568:
3326:
6906:
2264:
1383:
The machine can read from the read tape in one direction only (no backtracking), and write to the write tape in one direction only. It can read and write the work tape in both directions.
3420:
921:, because intuitively speaking, there is no general way to tell where to divide an output string just by looking at the concatenated string. We can divide it by specifying the length of
2700:
1380:
Fix a prefix-free universal Turing machine, with three tapes: a read tape infinite in one direction, a work tape infinite in two directions, and a write tape infinite in one direction.
2578:
919:
3514:
2463:
1135:
6234:
1194:
1015:
5111:. The third way defines an infinite sequence to be random if the prefix-free Kolmogorov complexity of its initial segments grows quickly enough — there must be a constant
3022:
2763:
731:
685:
5946:
6599:
5532:
5127:. This definition, unlike the definition of randomness for a finite string, is not affected by which universal machine is used to define prefix-free Kolmogorov complexity.
558:
4582:
and outputs some proof. This function enumerates all proofs. Some of these are proofs for formulas we do not care about here, since every possible proof in the language of
2623:
1290:
6990:
6317:
5183:
3522:
Program the Turing machine to read two subsequent programs, one describing the function and one describing the string. Then run both programs on the work tape to produce
8214:
6541:
7246:
499:
6759:
2115:
5258:
7189:
6964:
6721:
6666:
6631:
5757:
3160:
3094:
2074:
2019:
1041:
5447:
3057:
2147:
1434:
1328:
758:
6497:
6370:
6110:
5811:
5608:
3549:
3189:
3123:
2492:
2409:
2184:
1223:
452:
423:
1354:
1067:
6281:
6142:
6079:
6047:
5996:
5888:
5858:
5681:
5651:
5575:
3212:
7030:
7010:
6926:
6827:
6807:
6341:
6254:
6016:
5628:
5552:
5485:
5203:
3446:
2783:
2518:
2332:
where we double each digit, then add a termination code. The prefix-free universal Turing machine can then read in any program for the other machine as follows:
1481:
1461:
1407:
1247:
959:
939:
854:
2380:
373:
The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called the
6779:
6686:
6471:
6171:
5966:
5831:
5782:
5721:
5701:
9130:
2275:
9805:
1440:
Note that some universal Turing machines may not be programmable with prefix codes. We must pick only a prefix-free universal Turing machine.
10787:
7305:
7942:
9888:
9029:
3820:
as a subroutine, the program tries every string, starting with the shortest, until it returns a string with
Kolmogorov complexity at least
1972:, who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference" as part of his invention of
11455:
11266:
8165:"The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms"
5135:
For dynamical systems, entropy rate and algorithmic complexity of the trajectories are related by a theorem of Brudno, that the equality
687:
be a computable function mapping finite binary strings to binary strings. It is a universal function if, and only if, for any computable
38:'s general-purpose image compression only reduces it to 1.6 MB, smaller than the raw data but much larger than the Kolmogorov complexity.
6375:
3683:
Otherwise all of the infinitely many possible finite strings could be generated by the finitely many programs with a complexity below
1999: – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers.
856:
as a program interpreter, which takes in an initial segment describing the program, followed by data that the program should process.
11155:
1486:
12022:
11661:
11484:
11278:
8139:
6832:
6809:, the same one used to define the (prefix-free) Kolmogorov complexity. Define the (prefix-free) universal probability of a string
11997:
10969:
10202:
11666:
11243:
8425:
Alexei
Kaltchenko (2004). "Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics".
1976:. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in
10360:
8886:
8832:
8651:
8618:
8585:
8524:
8121:
8073:
5467:
The other direction is much more involved. It shows that given a
Kolmogorov complexity function, we can construct a function
1670:. So, there is at most a constant overhead, regardless of the object described. Therefore, the optimal language is universal
425:
while the prefix-free complexity is the minimal description length of any program encoded in a prefix-free code, and denoted
9148:
11396:
10215:
9538:
8408:
3998:
2018:
There are several other variants of
Kolmogorov complexity or algorithmic information. The most widely used one is based on
563:
170:
characters. Hence the operation of writing the first string can be said to have "less complexity" than writing the second.
106:
5415:{\displaystyle {\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)}
1386:
The work tape and write tape start with all zeros. The read tape starts with an input prefix code, followed by all zeros.
11773:
11511:
11450:
11261:
11211:
11034:
10220:
10210:
9947:
9800:
9153:
8809:
5088:
that can produce that string is at least as long as the string itself. To make this precise, a universal computer (or
5052:
763:
9144:
7968:
Chaitin, Gregory J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers".
7041:
1961:
is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other
10894:
10879:
10780:
10356:
8998:
8969:
8957:
8855:
8790:
8771:
8474:
Chaitin, G.; Arslanov, A.; Calude, Cristian S. (1995-09-01). "Program-size Complexity Computes the Halting Problem".
8458:
8267:
4192:
For the same reason, most strings are complex in the sense that they cannot be significantly compressed – their
186:
example above, whose Kolmogorov complexity is small relative to the string's size, are not considered to be complex.
9698:
3222:
11886:
10453:
10197:
9022:
7838:
4091:
7924:
7881:
5051:
The minimum message length principle of statistical and inductive inference and machine learning was developed by
2194:
12017:
12012:
11896:
11734:
11585:
11504:
11298:
9758:
9451:
5108:
5100:
5068:
4217:
3337:
9192:
8915:
2628:
11869:
11489:
11283:
11071:
10714:
10416:
10179:
10174:
9999:
9420:
9104:
1958:
43:
2523:
12007:
11966:
11002:
10709:
10492:
10409:
10122:
10053:
9930:
9172:
7295:
7280:
3724:
862:
195:
102:
11631:
7135:
11956:
11859:
11401:
10959:
10773:
10634:
10460:
10146:
9780:
9379:
5218:
5213:
3451:
2414:
1072:
1143:
964:
12002:
10949:
10944:
10512:
10507:
10117:
9856:
9785:
9114:
9015:
6179:
199:
162:
The first string has a short English-language description, namely "write ab 16 times", which consists of
7954:
4284:
11891:
11818:
11656:
11636:
11580:
11238:
11029:
10832:
10441:
10031:
9425:
9393:
9084:
2033:(Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov.
2012:
4223:
distribution on the space of these bitstrings assigns exactly equal weight 2 to each string of length
2974:
2705:
2335:
690:
644:
94:, who first published on the subject in 1963 and is a generalization of classical information theory.
11992:
11901:
11842:
11768:
11616:
11206:
11201:
11056:
10899:
10731:
10680:
10577:
10075:
10036:
9513:
9158:
5209:
4316:
191:
143:
35:
9187:
8910:
8554:
5897:
5490:
3989:" in the programming language community, stating that there is no perfect size-optimizing compiler.
3657:: There exist strings of arbitrarily large Kolmogorov complexity. Formally: for each natural number
504:
11906:
11479:
11273:
10974:
10572:
10502:
10041:
9893:
9876:
9599:
9079:
8643:
8610:
7982:
6992:, but that the universal Turing machine would halt at some point after reading the initial segment
6550:
5089:
8577:
8297:
8057:
2583:
1968:
The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by
1252:
11847:
11218:
11105:
11061:
10874:
10857:
10847:
10404:
10381:
10342:
10228:
10169:
9815:
9735:
9579:
9523:
9136:
6969:
6286:
5450:
5138:
4120:
3986:
3728:
1973:
1828:
3979:
3727:-like language to denote programs; for sake of proof simplicity assume its description (i.e. an
11472:
11223:
11007:
10852:
10694:
10421:
10399:
10366:
10259:
10105:
10090:
10063:
10014:
9898:
9833:
9658:
9624:
9619:
9493:
9324:
9301:
8292:
7977:
7205:
6502:
6149:
Output the string with the lowest lexicographic order that has not been output by any of those.
5046:
3717:
460:
98:
11744:
4753:
Finally, consider the program consisting of all these procedure definitions, and a main call:
2382:
The first part programs the machine to simulate the other machine, and is a constant overhead
2079:
10477:
10269:
9987:
9723:
9629:
9488:
9473:
9354:
9329:
8164:
6726:
5230:
5034:
4175:
454:. The plain complexity is more intuitive, but the prefix-free complexity is easier to study.
8635:
8602:
8569:
8049:
7157:
6934:
4726:, this procedure tries every proof until it finds a string and a proof in the formal system
3128:
3062:
2044:
1020:
11560:
11022:
10984:
10805:
10597:
10559:
10436:
10240:
10080:
10004:
9982:
9810:
9768:
9667:
9634:
9498:
9286:
9197:
8866:
8749:
Brudno, A. (1983). "Entropy and the complexity of the trajectories of a dynamical system".
8504:
8498:
8179:
7773:
7682:
7645:
7601:
7300:
6691:
6636:
6604:
6544:
5730:
5425:
5056:
4171:
3030:
2120:
1412:
1306:
736:
177:
of a string is the length of the shortest possible description of the string in some fixed
63:
31:
8368:"Effective symbolic dynamics, random points, statistical behavior, complexity and entropy"
6346:
5787:
5584:
3525:
3165:
3099:
2961:{\displaystyle K(x|y)\leq K(x)\leq K(x,y)\leq \max(K(x|y)+K(y),K(y|x)+K(x))\leq K(x)+K(y)}
2468:
2385:
2160:
1586:
Here is an example of an optimal description language. A description will have two parts:
1199:
428:
399:
8:
11791:
11682:
11641:
11626:
11595:
11590:
11499:
11406:
11339:
11308:
11293:
11076:
10726:
10617:
10602:
10582:
10539:
10426:
10376:
10302:
10247:
10184:
9977:
9972:
9920:
9688:
9677:
9349:
9249:
9177:
9168:
9164:
9099:
9094:
8929:
8636:
8603:
8570:
8050:
7290:
6476:
6089:
3698:
1333:
1046:
8508:
8283:
Wallace, C. S.; Dowe, D. L. (1999). "Minimum Message Length and Kolmogorov Complexity".
8183:
8114:
Universal artificial intelligence: sequential decisions based on algorithmic probability
7777:
7686:
5633:
5557:
3194:
11864:
11834:
11813:
11719:
11651:
11545:
11233:
11049:
11039:
10934:
10914:
10909:
10755:
10524:
10487:
10472:
10465:
10448:
10252:
10234:
10100:
10026:
10009:
9962:
9775:
9684:
9518:
9503:
9463:
9415:
9400:
9388:
9344:
9319:
9089:
9038:
8821:
8698:
8680:
8542:
8479:
8426:
8400:
8382:
8237:
8195:
8146:
8030:
7995:
7713:
7672:
7660:
7589:
7015:
6995:
6911:
6812:
6792:
6326:
6259:
6239:
6115:
6052:
6025:
6001:
5974:
5866:
5836:
5659:
5613:
5537:
5470:
5188:
4446:
3766:). All programs are of finite length so, for sake of proof simplicity, assume it to be
3431:
2503:
1984:
1466:
1446:
1392:
1232:
944:
924:
839:
11445:
9708:
8740:
8723:
8351:
8334:
8013:
Kolmogorov, A. (1968). "Logical basis for information theory and probability theory".
7919:
7876:
7636:
7619:
4810:, under the reasonable assumption that it is encoded in binary digits. We will choose
4391:
4174:, which applies because every compressed string maps to only one uncompressed string,
11808:
11796:
11778:
11646:
11530:
11467:
11313:
11228:
11184:
11145:
10827:
10750:
10690:
10497:
10307:
10297:
10189:
10070:
9905:
9881:
9662:
9646:
9551:
9528:
9405:
9374:
9339:
9234:
9069:
8994:
8965:
8953:
8892:
8882:
8851:
8844:
8828:
8805:
8786:
8767:
8647:
8614:
8581:
8530:
8520:
8454:
8263:
8199:
8117:
8069:
7801:
7718:
7700:
7615:
7581:
7569:
7285:
4895:
4312:
396:. The plain complexity is the minimal description length of any program, and denoted
91:
8702:
8483:
8191:
8034:
7999:
276:
has at least one description. For example, the second string above is output by the
222:
as a character string, multiplied by the number of bits in a character (e.g., 7 for
11783:
11739:
11712:
11707:
11565:
11550:
11460:
11369:
11364:
11193:
10926:
10904:
10796:
10704:
10699:
10592:
10549:
10371:
10332:
10327:
10312:
10138:
10095:
9992:
9790:
9740:
9314:
9276:
8874:
8735:
8690:
8512:
8404:
8392:
8346:
8302:
8241:
8229:
8187:
8061:
8022:
7987:
7914:
7871:
7791:
7781:
7708:
7690:
7631:
7539:
7378:. If program lengths are to be multiples of 7 bits, even fewer program texts exist.
7375:
7275:
6764:
6671:
6456:
6320:
6156:
5951:
5816:
5767:
5706:
5686:
5085:
4408:
and on the choice of description language) such that there does not exist a string
4343:
4244:
To prove the theorem, note that the number of descriptions of length not exceeding
4111:
1361:
that the word is finished, and does not need to backtrack or a termination symbol.
59:
47:
7370:
There are 1 + 2 + 2 + 2 + ... + 2 = 2 − 1 different program texts of length up to
5461:
The Kolmogorov complexity function is equivalent to deciding the halting problem.
11702:
11516:
11440:
11421:
11391:
11359:
11325:
10884:
10822:
10685:
10675:
10629:
10612:
10567:
10529:
10431:
10351:
10158:
10085:
10058:
10046:
9952:
9866:
9840:
9795:
9763:
9564:
9366:
9309:
9259:
9224:
9182:
8935:
8367:
8257:
7641:
7597:
4445:: The proof of this result is modeled on a self-referential construction used in
4353:. The axiomatic system has to be powerful enough so that, to certain assertions
4233:: With the uniform probability distribution on the space of bitstrings of length
3633:
1992:
1700:
1196:
on one side, whereas the same inequalities with prefix-free complexity have only
178:
121:
for each text's Kolmogorov complexity can return a value essentially larger than
110:
8982:
8065:
1626:
can be converted into a description in the optimal language by first describing
11494:
11288:
11017:
11012:
10869:
10842:
10814:
10670:
10649:
10607:
10587:
10482:
10337:
9935:
9925:
9915:
9910:
9844:
9718:
9594:
9483:
9478:
9456:
9057:
8925:
7819:
7310:
5104:
5103:
can be defined in three equivalent ways. One way uses an effective analogue of
4350:
4075:
1969:
1962:
230:
24:
8978:
8878:
8694:
8516:
8323:
but only 2-1 shorter bit strings, hence at most that much compression results.
8306:
7786:
7761:
7012:, without reading any further input, and that, when it halts, its has written
11986:
11801:
11749:
11416:
11411:
11386:
11318:
10939:
10837:
10644:
10322:
9829:
9614:
9604:
9574:
9559:
9229:
8961:
8896:
8534:
8396:
8026:
7805:
7757:
7704:
7585:
7265:
4003:
The chain rule for Kolmogorov complexity states that there exists a constant
3875:
3867:
is shorter, the contradiction remains. If it is longer, the constant used in
457:
By default, all equations hold only up to an additive constant. For example,
4773:
will be determined later on. The overall program length can be expressed as
1638:
as input to that program (part 2). The total length of this new description
11922:
10889:
10864:
10765:
10544:
10391:
10292:
10284:
10164:
10112:
10021:
9957:
9940:
9871:
9730:
9589:
9291:
9074:
8949:
Tromp's lambda calculus computer model offers a concrete definition of K()]
7722:
5227:(Theorem 14.2.5 ) The conditional Kolmogorov complexity of a binary string
4323:
3567:
At first glance it might seem trivial to write a program which can compute
2023:
8233:
7991:
11881:
11759:
11555:
11431:
11381:
10654:
10534:
9713:
9703:
9650:
9334:
9254:
9239:
9119:
9064:
8719:
8091:"Generalized Kolmogorov complexity and duality in theory of computations"
7823:
5578:
4220:
2030:
277:
118:
67:
51:
8920:
7899:
7856:
7593:
7123:
3833:
bits, i.e. a string that cannot be produced by any program shorter than
11938:
11729:
11724:
11611:
11570:
11376:
9584:
9439:
9410:
9216:
5081:
4182:, but only 2 − 1 shorter strings, that is, strings of length less than
174:
8431:
8090:
7796:
7695:
6473:. Further, since there are only so many possible programs with length
4521:. This is a contradiction. So it is not possible for the proof system
293:
whereas the first string is output by the (much shorter) pseudo-code:
10736:
10639:
9692:
9609:
9569:
9533:
9469:
9281:
9271:
9244:
9007:
8974:
8944:
7834:
7270:
5095:
This definition can be extended to define a notion of randomness for
4913:
would eventually terminate, and that procedure would return a string
3846:
bits. However, the overall length of the above program that produced
8116:. Texts in theoretical computer science. Berlin New York: Springer.
3625:. If the result matches then the length of the program is returned.
11852:
11697:
11354:
10721:
10519:
9967:
9672:
9266:
7677:
3214:
is easy to describe, but its substrings are very hard to describe.
318:
is of minimal length (i.e., using the fewest bits), it is called a
58:
of an object, such as a piece of text, is the length of a shortest
8685:
8387:
19:
11621:
11095:
11044:
10317:
9109:
4846:
sufficiently large, because the left hand side grows linearly in
4558:
We can find an effective enumeration of all the formal proofs in
4449:. We firstly obtain a program which enumerates the proofs within
2325:{\displaystyle 9\mapsto 1001\mapsto 11-00-00-11-\color {red}{01}}
2008:
27:
7943:"Three Approaches to the Quantitative Definition of Information"
3643:, be it ever so sophisticated. This is proven in the following.
1780:: By symmetry, it suffices to prove that there is some constant
1593:
The second part is a description of the object in that language.
11135:
8991:
Advances in Minimum Description Length: Theory and Applications
7824:
A Preliminary Report on a General Theory of Inductive Inference
7574:
Sankhyā: The Indian Journal of Statistics, Series A (1961-2002)
7400:
including the language interpreter and the subroutine code for
5018:
3966:
by reduction from the non-computability of the halting problem
1608:, the optimal description language is at least as efficient as
1140:
Typically, inequalities with plain complexity have a term like
8668:
7191:
is, roughly speaking, defined as the Kolmogorov complexity of
5023:
As a consequence, the above program, with the chosen value of
4390:
must be true. This "formalization" can be achieved based on a
1865:. The interpreter is characterized by the following property:
334:) (i.e. the number of bits in the minimal description) is the
11970:
11575:
11168:
11115:
9861:
9207:
9052:
8802:
An Introduction to Kolmogorov Complexity and Its Applications
8669:"Conditional Kolmogorov complexity and universal probability"
8638:
An Introduction to Kolmogorov Complexity and Its Applications
8605:
An Introduction to Kolmogorov Complexity and Its Applications
8500:
An Introduction to Kolmogorov Complexity and Its Applications
8366:
Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal (2010).
8052:
An Introduction to Kolmogorov Complexity and its Applications
7354:
6018:. Consider this (prefix-free) program, which takes no input:
3962:
words". It is also possible to show the non-computability of
3701:. In other words, there is no program which takes any string
2149:
means some fixed way to code for a tuple of strings x and y.
1671:
223:
97:
The notion of Kolmogorov complexity can be used to state and
70:
resources needed to specify the object, and is also known as
66:) that produces the object as output. It is a measure of the
3874:
The above proof uses a contradiction similar to that of the
3559:
11125:
10979:
10964:
10954:
8140:"Course notes for Data Compression - Kolmogorov complexity"
4092:
an analogue of mutual information for Kolmogorov complexity
4078:
than a logarithmic term larger than a program to reproduce
3554:
1583:
description of the object, nor the object being described.
4817:
to be greater than the program length, that is, such that
1463:
is the shortest prefix code that makes the machine output
11100:
11066:
8945:"John's Lambda Calculus and Combinatory Logic Playground"
7387:
By the previous theorem, such a string exists, hence the
5115:
such that the complexity of an initial segment of length
5077:
4489:, we have that the required length of a program to print
4357:
about complexity of strings, one can associate a formula
4327:
3639:
What is more, no program at all can compute the function
126:
8633:
8600:
3628:
However this will not work because some of the programs
2029:
An axiomatic approach to Kolmogorov complexity based on
3992:
3646:
8259:
Information and Randomness: an algorithmic perspective
6767:
6729:
6694:
6674:
6639:
6607:
6553:
6505:
6479:
6459:
6262:
6182:
6159:
6118:
6092:
6055:
6028:
5977:
5954:
5900:
5869:
5839:
5819:
5770:
5733:
5709:
5689:
5662:
4134:
if it has a description whose length does not exceed |
1590:
The first part describes another description language.
1295:
237:
is a function which associates to each Turing Machine
218:. The length of the description is just the length of
8989:
Grunwald, P.; Pitt, M.A. (2005). Myung, I. J. (ed.).
8473:
8215:"Information-theoretic limitations of formal systems"
7208:
7160:
7154:
The conditional Kolmogorov complexity of two strings
7044:
7018:
6998:
6972:
6937:
6914:
6835:
6815:
6795:
6378:
6349:
6329:
6289:
6242:
6004:
5790:
5636:
5616:
5587:
5560:
5540:
5493:
5473:
5428:
5266:
5233:
5191:
5141:
4370:. This association must have the following property:
4237:, the probability that a string is incompressible by
3809:KolmogorovComplexity(s) ≥ 8000000000
3528:
3454:
3434:
3340:
3225:
3197:
3168:
3131:
3102:
3065:
3033:
2977:
2786:
2708:
2631:
2586:
2526:
2506:
2471:
2417:
2388:
2338:
2278:
2197:
2163:
2123:
2082:
2047:
1489:
1469:
1449:
1415:
1395:
1336:
1309:
1255:
1235:
1202:
1146:
1075:
1049:
1023:
967:
947:
927:
865:
842:
766:
739:
693:
647:
631:{\displaystyle \exists c,\forall x,|f(x)-g(x)|\leq c}
566:
507:
463:
431:
402:
4853:
whilst the right hand side grows logarithmically in
4590:. Some of these are complexity formulas of the form
4178:
must exist, since there are 2 bit strings of length
4166:. A string incompressible by 1 is said to be simply
4066:
It states that the shortest program that reproduces
3779:
bits. Now, consider the following program of length
388:
There are two definitions of Kolmogorov complexity:
8781:Lajos, Rónyai; Gábor, Ivanyos; Réka, Szabó (1999).
8365:
4279:
1372:This gives us the following formal way to describe
8843:
8820:
8572:Information and Complexity in Statistical Modeling
8212:
7240:
7183:
7104:
7024:
7004:
6984:
6958:
6920:
6900:
6821:
6801:
6773:
6753:
6715:
6680:
6660:
6625:
6593:
6535:
6491:
6465:
6446:{\displaystyle K(x)\leq n+2\log _{2}n+O(1)\leq 2n}
6445:
6364:
6335:
6311:
6275:
6248:
6228:
6165:
6144:steps. Note the outputs of those that have halted.
6136:
6104:
6073:
6041:
6010:
5990:
5960:
5940:
5882:
5852:
5825:
5805:
5776:
5751:
5715:
5695:
5675:
5645:
5622:
5602:
5569:
5546:
5526:
5479:
5441:
5414:
5252:
5197:
5177:
5033:Similar ideas are used to prove the properties of
4102:It is straightforward to compute upper bounds for
3741:bits. Assume for contradiction there is a program
3543:
3508:
3440:
3422:, we need to use a counting argument (page 38 ).
3414:
3320:
3206:
3183:
3154:
3117:
3088:
3051:
3016:
2960:
2776:Theorem. (extra information bounds, subadditivity)
2757:
2694:
2617:
2572:
2512:
2486:
2457:
2403:
2374:
2324:
2258:
2178:
2141:
2109:
2068:
2015:: "...to everyone who has, more will be given..."
1634:(part 1), and then using the original description
1562:
1475:
1455:
1428:
1401:
1348:
1322:
1284:
1241:
1217:
1188:
1129:
1061:
1035:
1009:
953:
933:
913:
848:
828:
752:
725:
679:
630:
552:
493:
446:
417:
8865:Downey, Rodney G.; Hirschfeldt, Denis R. (2010).
8864:
8424:
8048:Li, Ming; Vitányi, Paul (2008). "Preliminaries".
5784:, enumerate all (prefix-free) programs of length
829:{\displaystyle \forall x\in 2^{*},U(s_{f}x)=f(x)}
11984:
7900:"A Formal Theory of Inductive Inference Part II"
7105:{\displaystyle \log {\frac {1}{P(x)}}=K(x)+O(1)}
5610:). By modifying the function at lower values of
3863:bits, which is a contradiction. (If the code of
2846:
1820:Now, suppose there is a program in the language
1505:
1153:
974:
380:
229:We could, alternatively, choose an encoding for
8751:Transactions of the Moscow Mathematical Society
8162:
8137:
7857:"A Formal Theory of Inductive Inference Part I"
3191:. There are strings such that the whole string
1563:{\displaystyle K(x):=\min\{|c|:c\in S,U(c)=x\}}
8780:
8567:
7735:(Downey and Hirschfeldt, 2010), Theorem 3.1.4
7202:There is also a length-conditional complexity
6372:comes from the rest of the program. Therefore,
5011:was described by the program with that length
4634:th proof actually proves a complexity formula
4276:. To determine the probability, divide by 2.
4208:in bits. To make this precise, fix a value of
3321:{\displaystyle K(x,y)=K(x|y,K(y))+K(y)=K(y,x)}
10781:
9023:
4803:) represents the length of the integer value
4750:; if no such proof exists, it loops forever.
4485:to greater than the length of this procedure
3985:There is a corollary, humorously called the "
10795:
8988:
8952:Universal AI based on Kolmogorov Complexity
8561:
7661:"How Incomputable Is Kolmogorov Complexity?"
6901:{\displaystyle P(x)=\sum _{U(p)=x}2^{-l(p)}}
5453:(not to be confused with the entropy rate).
3334:One side is simple. For the other side with
2259:{\displaystyle C(x)\leq K(x)+2\log _{2}C(x)}
1721: – which depends only on the languages
1557:
1508:
733:, we can encode the function in a "program"
8911:The Legacy of Andrei Nikolaevich Kolmogorov
8761:
8448:
8282:
7744:(Downey and Hirschfeldt, 2010), Section 3.5
7572:(Dec 1963). "On Tables of Random Numbers".
4299:, and two computable lower bound functions
3415:{\displaystyle K(x,y)\geq K(x|y,K(y))+K(y)}
10788:
10774:
9215:
9030:
9016:
8926:Generalizations of algorithmic information
8332:
8095:Notices of the Russian Academy of Sciences
8082:
8012:
7940:
7897:
7854:
7818:
7614:
7568:
7306:Solomonoff's theory of inductive inference
5212:, Kolmogorov complexity is related to the
2695:{\displaystyle K(x)\leq |x|+2\log _{2}|x|}
1677:
859:One problem with plain complexity is that
8846:Introduction to the Theory of Computation
8799:
8762:Cover, Thomas M.; Thomas, Joy A. (2006).
8739:
8684:
8496:
8449:Cover, Thomas M.; Thomas, Joy A. (2006).
8430:
8386:
8350:
8296:
8256:Calude, Cristian S. (12 September 2002).
8047:
7981:
7918:
7875:
7795:
7785:
7712:
7694:
7676:
7635:
6256:comes from the length of the Busy Beaver
5040:
4427: (as formalized in
1699:are the complexity functions relative to
8871:Theory and Applications of Computability
7199:as an auxiliary input to the procedure.
6784:
6153:Let the string output by the program be
5099:sequences from a finite alphabet. These
5062:
4545:larger than the length of the procedure
4322:, ordered by length; the vertical axis (
4283:
4142:bits. This is equivalent to saying that
3560:A naive attempt at a program to compute
3555:Uncomputability of Kolmogorov complexity
2573:{\displaystyle \forall x,C(x)\leq |x|+c}
1330:such that given any two different words
76:Solomonoff–Kolmogorov–Chaitin complexity
18:
8867:"Algorithmic Randomness and Complexity"
8666:
8015:IEEE Transactions on Information Theory
7967:
7658:
7114:
6966:does not mean that the input stream is
5208:It can be shown that for the output of
4090:. Using this statement, one can define
1924:, which we can take to be the constant
1443:The prefix-free complexity of a string
1436:, used by the universal Turing machine.
914:{\displaystyle C(xy)\not <C(x)+C(y)}
127:§ Chaitin's incompleteness theorem
11985:
9037:
8841:
8748:
8255:
8111:
8088:
8056:. Texts in Computer Science. pp.
7756:
5130:
4654:in turn, are computable by procedure:
4541:arbitrarily large, in particular, for
3871:can always be changed appropriately.)
1953:
10769:
9011:
8444:
8442:
7357:program can have a length of exactly
3509:{\displaystyle K(f(x))\leq K(x)+K(f)}
3027:Note that there is no way to compare
2458:{\displaystyle \leq 2\log _{2}C(x)+3}
2344:code for simulating the other machine
1950:This proves the desired upper bound.
1666:is a constant that doesn't depend on
1577:
1572:
1130:{\displaystyle C(xy)\geq C(x)+C(y)+c}
8766:(2nd ed.). Wiley-Interscience.
8718:
8453:(2nd ed.). Wiley-Interscience.
8335:"The definition of random sequences"
7752:
7750:
7118:
6229:{\textstyle \leq n+2\log _{2}n+O(1)}
5653:, which solves the halting problem.
4326:) measures Kolmogorov complexity in
3999:Chain rule for Kolmogorov complexity
3993:Chain rule for Kolmogorov complexity
1912:. The length of this description of
1249:may represent a binary number up to
1189:{\displaystyle O(\min(\ln x,\ln y))}
1010:{\displaystyle O(\min(\ln x,\ln y))}
249:is a Turing Machine which, on input
206:is a program which outputs a string
146:of 32 lowercase letters and digits:
8634:Ming Li; Paul M.B. Vitányi (2009).
8601:Ming Li; Paul M.B. Vitányi (2009).
7497:, the number of strings of lengths
6723:. Further, that program has length
6688:has a minimal program with runtime
6633:has a minimal program with runtime
6319:comes from using the (prefix-free)
4704:NthProofProvesComplexityFormula(i)
4457:which takes as an input an integer
4386:, then the corresponding assertion
4212:. There are 2 bitstrings of length
3647:Formal proof of uncomputability of
3426:Theorem. (information non-increase)
290:"4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"
257:, then the concatenated string <
23:This image illustrates part of the
13:
8818:
8712:
8439:
8319:There are 2 bit strings of length
7659:Vitányi, Paul M. B. (April 2020).
6112:. Run every one of them for up to
6086:Generate all programs with length
5456:
4948:
4708:ComplexityLowerBoundNthProof(i) ≥
4683:Consider the following procedure:
4252:is given by the geometric series:
3705:as input and produces the integer
3218:Theorem. (symmetry of information)
2527:
1896:which is a minimal description of
1303:A prefix-free code is a subset of
1296:Prefix-free Kolmogorov complexity
767:
576:
567:
14:
12034:
8942:
8904:
7747:
7460:, which is always possible since
5055:and D.M. Boulton in 1968. MML is
4610:are constants in the language of
3613:evaluate(p) == s
2315:
2011:considers this an example of the
16:Measure of algorithmic complexity
11962:
11961:
11952:
11951:
10749:
8800:Li, Ming; Vitányi, Paul (1997).
8497:Li, Ming; Vitányi, Paul (2008).
8414:from the original on 2022-10-09.
7930:from the original on 2022-10-09.
7887:from the original on 2022-10-09.
7844:from the original on 2022-10-09.
7762:"Algorithmic information theory"
7122:
6049:, and record its runtime length
5581:shift function (also denoted as
5101:algorithmically random sequences
4620:NthProofProvesComplexityFormula(
4339:
4280:Chaitin's incompleteness theorem
3017:{\displaystyle K(xy)\leq K(x,y)}
2758:{\displaystyle K(x||x|)\leq |x|}
2036:
726:{\displaystyle f:2^{*}\to 2^{*}}
680:{\displaystyle U:2^{*}\to 2^{*}}
157:4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
151:abababababababababababababababab
12023:Computational complexity theory
8660:
8627:
8594:
8490:
8467:
8418:
8359:
8326:
8313:
8276:
8249:
8213:Gregory J. Chaitin (Jul 1974).
8206:
8192:10.1070/RM1970v025n06ABEH001269
8156:
8130:
8105:
8041:
8006:
7961:
7934:
7475:
7428:needs to be adapted to satisfy
7406:
7394:
7391:loop will eventually terminate.
7381:
7364:
7323:
6789:Fix a universal Turing machine
5941:{\textstyle p_{K}(n)\geq BB(n)}
5894:We prove by contradiction that
5069:Algorithmically random sequence
4900:ComplexityLowerBoundNthProof(i)
4465:which are within proofs within
4382:is provable from the axioms of
4186:, (i.e. with length 0, 1, ...,
2152:
1612:, with some constant overhead.
1604:Given any description language
1602:The invariance theorem follows:
1017:extra symbols. Indeed, for any
11998:Algorithmic information theory
8823:A Course in Mathematical Logic
8764:Elements of information theory
8451:Elements of information theory
8163:Zvonkin, A.; L. Levin (1970).
7891:
7855:Solomonoff, Ray (March 1964).
7848:
7812:
7738:
7729:
7652:
7608:
7562:
7235:
7232:
7226:
7219:
7212:
7178:
7171:
7164:
7099:
7093:
7084:
7078:
7066:
7060:
6947:
6941:
6893:
6887:
6865:
6859:
6845:
6839:
6739:
6733:
6710:
6704:
6655:
6649:
6594:{\textstyle p_{K}(n)<BB(n)}
6588:
6582:
6570:
6564:
6515:
6509:
6431:
6425:
6388:
6382:
6359:
6353:
6223:
6217:
6131:
6125:
6068:
6062:
5935:
5929:
5917:
5911:
5813:until one of them does output
5800:
5794:
5597:
5591:
5527:{\displaystyle p(n)\geq BB(n)}
5521:
5515:
5503:
5497:
5409:
5395:
5307:
5300:
5280:
5172:
5166:
5157:
5145:
4756:GenerateProvablyComplexString(
4689:GenerateProvablyComplexString(
4097:
3754:which takes as input a string
3538:
3532:
3503:
3497:
3488:
3482:
3473:
3470:
3464:
3458:
3409:
3403:
3394:
3391:
3385:
3372:
3365:
3356:
3344:
3315:
3303:
3294:
3288:
3279:
3276:
3270:
3257:
3250:
3241:
3229:
3178:
3172:
3149:
3142:
3135:
3112:
3106:
3083:
3076:
3069:
3046:
3037:
3011:
2999:
2990:
2981:
2955:
2949:
2940:
2934:
2925:
2922:
2916:
2907:
2900:
2893:
2884:
2878:
2869:
2862:
2855:
2849:
2840:
2828:
2819:
2813:
2804:
2797:
2790:
2751:
2743:
2736:
2732:
2724:
2719:
2712:
2688:
2680:
2656:
2648:
2641:
2635:
2611:
2603:
2596:
2590:
2560:
2552:
2545:
2539:
2481:
2475:
2446:
2440:
2398:
2392:
2369:
2361:
2358:
2350:
2347:
2339:
2288:
2282:
2253:
2247:
2222:
2216:
2207:
2201:
2173:
2167:
2136:
2124:
2104:
2101:
2089:
2086:
2063:
2051:
1995:also presents this theorem in
1959:Algorithmic information theory
1877:returns the result of running
1548:
1542:
1520:
1512:
1499:
1493:
1278:
1270:
1212:
1206:
1183:
1180:
1156:
1150:
1118:
1112:
1103:
1097:
1088:
1079:
1004:
1001:
977:
971:
908:
902:
893:
887:
878:
869:
823:
817:
808:
792:
710:
664:
618:
614:
608:
599:
593:
586:
553:{\displaystyle f(x)=g(x)+O(1)}
547:
541:
532:
526:
517:
511:
488:
482:
473:
467:
441:
435:
412:
406:
107:Gödel's incompleteness theorem
44:algorithmic information theory
1:
10710:History of mathematical logic
8916:Chaitin's online publications
8741:10.1016/S0019-9958(67)90546-3
8352:10.1016/s0019-9958(66)80018-9
7947:Problems Inform. Transmission
7920:10.1016/S0019-9958(64)90131-7
7898:Solomonoff, Ray (June 1964).
7877:10.1016/S0019-9958(64)90223-2
7637:10.1016/S0304-3975(98)00075-9
7620:"On Tables of Random Numbers"
7556:
7548:2 × (1 − 2) / (1 − 2) = 2 − 1
7296:Kolmogorov structure function
7281:Descriptive complexity theory
7248:, which is the complexity of
5076:defines a string (usually of
4953:GenerateProvablyComplexString
4911:GenerateProvablyComplexString
4839:). This is clearly true for
4673:ComplexityLowerBoundNthProof(
4630:which determines whether the
4517:was printed by the procedure
4509:is then less than the amount
3805:length exactly i
3605:length exactly i
2411:. The second part has length
1989:Problems Inform. Transmission
132:
10635:Primitive recursive function
8979:Minimum Message Length (MML)
8673:Theoretical Computer Science
8172:Russian Mathematical Surveys
7624:Theoretical Computer Science
6601:, so every string of length
4256:1 + 2 + 2 + ... + 2 = 2 − 1.
4200:) is not much smaller than |
4130:is compressible by a number
3789:GenerateComplexString()
3428:For any computable function
2618:{\displaystyle C(x)\leq |x|}
2465:. The third part has length
2186:. This section is based on.
2157:We omit additive factors of
1285:{\displaystyle \log _{2}|x|}
381:Plain Kolmogorov complexity
137:
113:. In particular, no program
7:
8936:"Review of Li Vitányi 1997"
8667:Vitányi, Paul M.B. (2013).
8375:Information and Computation
8145:. p. 7. Archived from
8066:10.1007/978-0-387-49820-1_1
7353:is not a multiple of 7, no
7259:
6985:{\displaystyle p000\cdots }
6312:{\displaystyle 2\log _{2}n}
5998:be a Busy Beaver of length
5727:List all strings of length
5178:{\displaystyle K(x;T)=h(T)}
4867:Then no proof of the form "
4700:i = 1 to infinity:
4453:and we specify a procedure
4272:that are incompressible by
4082:and a program to reproduce
2355:coded length of the program
1717:, then there is a constant
1409:be the prefix-free code on
142:Consider the following two
125:'s own length (see section
10:
12039:
11843:Compressed data structures
11165:RLE + BWT + MTF + Huffman
10833:Asymmetric numeral systems
9699:Schröder–Bernstein theorem
9426:Monadic predicate calculus
9085:Foundations of mathematics
6536:{\textstyle l(x)\leq 2n+1}
5210:Markov information sources
5066:
5044:
4400:: There exists a constant
3996:
1920:The length of the program
1784:such that for all strings
1366:prefix-free Turing machine
103:Cantor's diagonal argument
11947:
11931:
11915:
11833:
11758:
11690:
11681:
11604:
11538:
11529:
11430:
11347:
11338:
11254:
11202:Discrete cosine transform
11192:
11183:
11132:LZ77 + Huffman + context
11085:
10995:
10925:
10813:
10804:
10745:
10732:Philosophy of mathematics
10681:Automated theorem proving
10663:
10558:
10390:
10283:
10135:
9852:
9828:
9806:Von Neumann–Bernays–Gödel
9751:
9645:
9549:
9447:
9438:
9365:
9300:
9206:
9128:
9045:
8879:10.1007/978-0-387-68441-3
8724:"On the size of machines"
8695:10.1016/j.tcs.2013.07.009
8517:10.1007/978-0-387-49820-1
8136:Stated without proof in:
7941:Kolmogorov, A.N. (1965).
7837:published November 1960.
7787:10.4249/scholarpedia.2519
7345:need not exist for every
7241:{\displaystyle K(x|L(x))}
5630:we get an upper bound on
5107:; another uses effective
5017:This is a contradiction,
4860:up to the fixed constant
3579:, such as the following:
494:{\displaystyle f(x)=g(x)}
11907:Smallest grammar problem
8842:Sipser, Michael (1997).
8397:10.1016/j.ic.2009.05.001
8333:Martin-Löf, Per (1966).
8138:P. B. Miltersen (2005).
8027:10.1109/TIT.1968.1054210
7953:(1): 1–7. Archived from
7316:
6754:{\textstyle K(x)\leq 2n}
5090:universal Turing machine
4792:is some constant and log
4412:for which the statement
2110:{\displaystyle K((x,y))}
2020:self-delimiting programs
1983:Andrey Kolmogorov later
1735:chosen – such that
1674:this additive constant.
111:Turing's halting problem
11848:Compressed suffix array
11397:Nyquist–Shannon theorem
10382:Self-verifying theories
10203:Tarski's axiomatization
9154:Tarski's undefinability
9149:incompleteness theorems
8921:Solomonoff's IDSIA page
8728:Information and Control
8568:Jorma Rissanen (2007).
8339:Information and Control
8307:10.1093/comjnl/42.4.270
8112:Hutter, Marcus (2005).
7907:Information and Control
7864:Information and Control
6761:. This contradicts how
6176:The program has length
5683:, which takes input as
5451:binary entropy function
5253:{\displaystyle x_{1:n}}
4909:, then the loop inside
4894:, as can be seen by an
4614:. There is a procedure
4461:and prints the strings
4404:(which only depends on
4311:. The horizontal axis (
4241:is at least 1 − 2 + 2.
4123:in the given language.
4121:self-extracting archive
3987:full employment theorem
2022:, and is mainly due to
1985:independently published
1978:Information and Control
1974:algorithmic probability
1935:which by definition is
1678:A more formal treatment
80:program-size complexity
12018:Measures of complexity
12013:Descriptive complexity
10756:Mathematics portal
10367:Proof of impossibility
10015:propositional variable
9325:Propositional calculus
8576:. Springer S. p.
7957:on September 28, 2011.
7242:
7185:
7184:{\displaystyle K(x|y)}
7106:
7026:
7006:
6986:
6960:
6959:{\displaystyle U(p)=x}
6922:
6902:
6823:
6803:
6775:
6755:
6717:
6716:{\textstyle <BB(n)}
6682:
6662:
6661:{\textstyle <BB(n)}
6627:
6626:{\textstyle \leq 2n+1}
6595:
6537:
6493:
6467:
6447:
6366:
6337:
6313:
6277:
6250:
6230:
6167:
6138:
6106:
6075:
6043:
6012:
5992:
5962:
5942:
5884:
5854:
5827:
5807:
5778:
5753:
5752:{\textstyle \leq 2n+1}
5717:
5697:
5677:
5656:Consider this program
5647:
5624:
5604:
5571:
5548:
5528:
5481:
5443:
5416:
5254:
5199:
5179:
5047:Minimum message length
5041:Minimum message length
4902:could return a value ≥
4338:By the above theorem (
4335:
4288:Kolmogorov complexity
4260:There remain at least
4176:incompressible strings
3731:) to have a length of
3545:
3510:
3442:
3416:
3322:
3208:
3185:
3156:
3155:{\displaystyle K(y|x)}
3119:
3090:
3089:{\displaystyle K(x|y)}
3053:
3018:
2962:
2759:
2696:
2619:
2574:
2514:
2488:
2459:
2405:
2376:
2326:
2260:
2180:
2143:
2111:
2070:
2069:{\displaystyle K(x,y)}
1703:description languages
1630:as a computer program
1564:
1477:
1457:
1430:
1403:
1350:
1324:
1286:
1243:
1219:
1190:
1131:
1063:
1037:
1036:{\displaystyle c>0}
1011:
961:, but that would take
955:
935:
915:
850:
830:
754:
727:
681:
632:
554:
495:
448:
419:
299:GenerateString1()
286:GenerateString2()
84:descriptive complexity
72:algorithmic complexity
39:
11877:Kolmogorov complexity
11745:Video characteristics
11122:LZ77 + Huffman + ANS
10625:Kolmogorov complexity
10578:Computably enumerable
10478:Model complete theory
10270:Principia Mathematica
9330:Propositional formula
9159:Banach–Tarski paradox
8609:. Springer. pp.
8234:10.1145/321832.321839
7992:10.1145/321526.321530
7464:grows faster than log
7426:GenerateComplexString
7243:
7186:
7107:
7027:
7007:
6987:
6961:
6923:
6903:
6824:
6804:
6785:Universal probability
6776:
6756:
6718:
6683:
6663:
6628:
6596:
6538:
6494:
6468:
6448:
6367:
6338:
6314:
6278:
6251:
6231:
6168:
6139:
6107:
6076:
6044:
6013:
5993:
5963:
5943:
5885:
5855:
5833:. Record its runtime
5828:
5808:
5779:
5764:For each such string
5754:
5718:
5698:
5678:
5648:
5625:
5605:
5572:
5549:
5529:
5482:
5444:
5442:{\displaystyle H_{b}}
5417:
5255:
5200:
5185:holds for almost all
5180:
5084:if and only if every
5074:Kolmogorov randomness
5063:Kolmogorov randomness
5030:, must loop forever.
4586:is produced for some
4578:which takes as input
4549:, (which is finite).
4435:can be proven within
4287:
4268:bitstrings of length
4162:is incompressible by
3869:GenerateComplexString
3747:KolmogorovComplexity(
3585:KolmogorovComplexity(
3546:
3511:
3443:
3417:
3323:
3209:
3186:
3157:
3120:
3091:
3054:
3052:{\displaystyle K(xy)}
3019:
2963:
2760:
2697:
2620:
2575:
2515:
2489:
2460:
2406:
2377:
2327:
2261:
2181:
2144:
2142:{\displaystyle (x,y)}
2112:
2071:
1908:) returns the string
1565:
1478:
1458:
1431:
1429:{\displaystyle 2^{*}}
1404:
1351:
1325:
1323:{\displaystyle 2^{*}}
1287:
1244:
1220:
1191:
1132:
1064:
1038:
1012:
956:
936:
916:
851:
831:
755:
753:{\displaystyle s_{f}}
728:
682:
633:
555:
496:
449:
420:
336:Kolmogorov complexity
56:Kolmogorov complexity
22:
12008:Computability theory
11967:Compression software
11561:Compression artifact
11517:Psychoacoustic model
10573:Church–Turing thesis
10560:Computability theory
9769:continuum hypothesis
9287:Square of opposition
9145:Gödel's completeness
8642:. Springer. p.
7822:(February 4, 1960).
7538:, which is a finite
7414:KolmogorovComplexity
7402:KolmogorovComplexity
7301:Levenshtein distance
7252:given the length of
7206:
7158:
7115:Conditional versions
7042:
7032:to the output tape.
7016:
6996:
6970:
6935:
6912:
6833:
6813:
6793:
6765:
6727:
6692:
6672:
6637:
6605:
6551:
6545:pigeonhole principle
6503:
6492:{\textstyle \leq 2n}
6477:
6457:
6376:
6365:{\displaystyle O(1)}
6347:
6327:
6287:
6260:
6240:
6180:
6157:
6116:
6105:{\textstyle \leq 2n}
6090:
6053:
6026:
6002:
5975:
5952:
5898:
5867:
5837:
5817:
5806:{\displaystyle K(x)}
5788:
5768:
5731:
5707:
5687:
5660:
5634:
5614:
5603:{\displaystyle S(n)}
5585:
5558:
5538:
5491:
5471:
5426:
5264:
5231:
5189:
5139:
4172:pigeonhole principle
3865:KolmogorovComplexity
3818:KolmogorovComplexity
3661:, there is a string
3551:, and write it out.
3544:{\displaystyle f(x)}
3526:
3452:
3432:
3338:
3223:
3195:
3184:{\displaystyle K(y)}
3166:
3129:
3118:{\displaystyle K(x)}
3100:
3063:
3031:
2975:
2784:
2706:
2629:
2584:
2524:
2504:
2487:{\displaystyle C(x)}
2469:
2415:
2404:{\displaystyle O(1)}
2386:
2336:
2276:
2195:
2179:{\displaystyle O(1)}
2161:
2121:
2080:
2045:
1642:is (approximately):
1487:
1467:
1447:
1413:
1393:
1334:
1307:
1253:
1233:
1218:{\displaystyle O(1)}
1200:
1144:
1073:
1047:
1021:
965:
945:
925:
863:
840:
764:
737:
691:
645:
564:
505:
461:
447:{\displaystyle K(x)}
429:
418:{\displaystyle C(x)}
400:
326:, and the length of
265:is a description of
214:is a description of
90:. It is named after
64:programming language
62:(in a predetermined
32:model of computation
11957:Compression formats
11596:Texture compression
11591:Standard test image
11407:Silence compression
10727:Mathematical object
10618:P versus NP problem
10583:Computable function
10377:Reverse mathematics
10303:Logical consequence
10180:primitive recursive
10175:elementary function
9948:Free/bound variable
9801:Tarski–Grothendieck
9320:Logical connectives
9250:Logical equivalence
9100:Logical consequence
8827:. Springer-Verlag.
8509:2008ikca.book.....L
8184:1970RuMaS..25...83Z
8089:Burgin, M. (1982).
7778:2007SchpJ...2.2519H
7687:2020Entrp..22..408V
7420:bits, the constant
7291:Inductive reasoning
6668:. Thus, the string
5863:Output the largest
5131:Relation to entropy
5119:is always at least
4951:by construction of
4890:can be obtained in
4766:where the constant
3699:computable function
2580:. More succinctly,
1954:History and context
1349:{\displaystyle x,y}
1062:{\displaystyle x,y}
320:minimal description
173:More formally, the
99:prove impossibility
88:algorithmic entropy
12003:Information theory
11865:Information theory
11720:Display resolution
11546:Chroma subsampling
10935:Byte pair encoding
10880:Shannon–Fano–Elias
10525:Transfer principle
10488:Semantics of logic
10473:Categorical theory
10449:Non-standard model
9963:Logical connective
9090:Information theory
9039:Mathematical logic
8819:Yu, Manin (1977).
8503:. Exercise 2.7.7.
8222:Journal of the ACM
7970:Journal of the ACM
7616:Kolmogorov, Andrey
7570:Kolmogorov, Andrey
7493:strings of length
7349:. For example, if
7238:
7181:
7134:. You can help by
7102:
7038:(Theorem 14.11.1)
7022:
7002:
6982:
6956:
6918:
6898:
6875:
6819:
6799:
6771:
6751:
6713:
6678:
6658:
6623:
6591:
6533:
6489:
6463:
6443:
6362:
6333:
6309:
6276:{\textstyle p_{n}}
6273:
6246:
6226:
6163:
6137:{\textstyle BB(n)}
6134:
6102:
6074:{\textstyle BB(n)}
6071:
6042:{\textstyle p_{n}}
6039:
6008:
5991:{\textstyle p_{n}}
5988:
5958:
5938:
5883:{\textstyle n_{x}}
5880:
5853:{\textstyle n_{x}}
5850:
5823:
5803:
5774:
5749:
5713:
5693:
5676:{\textstyle p_{K}}
5673:
5646:{\displaystyle BB}
5643:
5620:
5600:
5570:{\displaystyle BB}
5567:
5544:
5524:
5477:
5439:
5412:
5347:
5250:
5195:
5175:
5035:Chaitin's constant
4650:, and the integer
4562:by some procedure
4505:as being at least
4481:. By then setting
4340:§ Compression
4336:
4007:such that for all
3797:infinity:
3609:isValidProgram(p)
3597:infinity:
3541:
3506:
3438:
3412:
3318:
3207:{\displaystyle xy}
3204:
3181:
3152:
3115:
3086:
3049:
3014:
2958:
2755:
2692:
2615:
2570:
2510:
2484:
2455:
2401:
2372:
2322:
2321:
2256:
2176:
2139:
2107:
2066:
1844:InterpretLanguage(
1578:Informal treatment
1573:Invariance theorem
1560:
1473:
1453:
1426:
1399:
1346:
1320:
1282:
1239:
1215:
1186:
1127:
1059:
1033:
1007:
951:
931:
911:
846:
836:. We can think of
826:
750:
723:
677:
628:
550:
501:really means that
491:
444:
415:
375:invariance theorem
40:
11980:
11979:
11829:
11828:
11779:Deblocking filter
11677:
11676:
11525:
11524:
11334:
11333:
11179:
11178:
10763:
10762:
10695:Abstract category
10498:Theories of truth
10308:Rule of inference
10298:Natural deduction
10279:
10278:
9824:
9823:
9529:Cartesian product
9434:
9433:
9340:Many-valued logic
9315:Boolean functions
9198:Russell's paradox
9173:diagonal argument
9070:First-order logic
8888:978-0-387-95567-4
8834:978-0-7204-2844-5
8653:978-0-387-49820-1
8620:978-0-387-49820-1
8587:978-0-387-68812-1
8526:978-0-387-33998-6
8123:978-3-540-26877-2
8075:978-0-387-33998-6
7696:10.3390/e22040408
7286:Grammar induction
7152:
7151:
7070:
7025:{\displaystyle x}
7005:{\displaystyle p}
6921:{\displaystyle x}
6851:
6822:{\displaystyle x}
6802:{\displaystyle U}
6781:was constructed.
6547:. By assumption,
6336:{\displaystyle n}
6249:{\displaystyle n}
6011:{\displaystyle n}
5623:{\displaystyle n}
5547:{\displaystyle n}
5480:{\displaystyle p}
5387:
5338:
5336:
5275:
5198:{\displaystyle x}
5015:
5014:
4981:by the choice of
4896:indirect argument
4513:since the string
4469:of the statement
4315:) enumerates all
4313:logarithmic scale
4204:|, the length of
4188:n − 1).
3980:Turing-equivalent
3441:{\displaystyle f}
2513:{\displaystyle c}
2367:
2356:
2345:
1922:InterpretLanguage
1902:InterpretLanguage
1871:InterpretLanguage
1827:which acts as an
1476:{\displaystyle x}
1456:{\displaystyle x}
1402:{\displaystyle S}
1242:{\displaystyle x}
954:{\displaystyle y}
934:{\displaystyle x}
849:{\displaystyle U}
350:). Symbolically,
306:If a description
253:, outputs string
92:Andrey Kolmogorov
12030:
11993:Data compression
11965:
11964:
11955:
11954:
11784:Lapped transform
11688:
11687:
11566:Image resolution
11551:Coding tree unit
11536:
11535:
11345:
11344:
11190:
11189:
10811:
10810:
10797:Data compression
10790:
10783:
10776:
10767:
10766:
10754:
10753:
10705:History of logic
10700:Category of sets
10593:Decision problem
10372:Ordinal analysis
10313:Sequent calculus
10211:Boolean algebras
10151:
10150:
10125:
10096:logical/constant
9850:
9849:
9836:
9759:Zermelo–Fraenkel
9510:Set operations:
9445:
9444:
9382:
9213:
9212:
9193:Löwenheim–Skolem
9080:Formal semantics
9032:
9025:
9018:
9009:
9008:
9004:
8948:
8939:
8900:
8861:
8849:
8838:
8826:
8815:
8796:
8777:
8758:
8745:
8743:
8707:
8706:
8688:
8664:
8658:
8657:
8641:
8631:
8625:
8624:
8608:
8598:
8592:
8591:
8575:
8565:
8559:
8558:
8552:
8548:
8546:
8538:
8494:
8488:
8487:
8471:
8465:
8464:
8446:
8437:
8436:
8434:
8422:
8416:
8415:
8413:
8390:
8372:
8363:
8357:
8356:
8354:
8330:
8324:
8317:
8311:
8310:
8300:
8285:Computer Journal
8280:
8274:
8273:
8253:
8247:
8245:
8219:
8210:
8204:
8203:
8169:
8160:
8154:
8153:
8151:
8144:
8134:
8128:
8127:
8109:
8103:
8102:
8086:
8080:
8079:
8055:
8045:
8039:
8038:
8010:
8004:
8003:
7985:
7965:
7959:
7958:
7938:
7932:
7931:
7929:
7922:
7904:
7895:
7889:
7888:
7886:
7879:
7861:
7852:
7846:
7845:
7843:
7828:
7816:
7810:
7809:
7799:
7789:
7754:
7745:
7742:
7736:
7733:
7727:
7726:
7716:
7698:
7680:
7656:
7650:
7649:
7639:
7612:
7606:
7605:
7566:
7550:
7549:
7545:
7540:geometric series
7537:
7533:
7507:
7492:
7479:
7473:
7459:
7446:
7442:
7441:
7438:
7427:
7415:
7410:
7404:
7403:
7398:
7392:
7390:
7385:
7379:
7376:geometric series
7368:
7362:
7327:
7276:Data compression
7256:as known/input.
7247:
7245:
7244:
7239:
7222:
7190:
7188:
7187:
7182:
7174:
7147:
7144:
7126:
7119:
7111:
7109:
7108:
7103:
7071:
7069:
7052:
7031:
7029:
7028:
7023:
7011:
7009:
7008:
7003:
6991:
6989:
6988:
6983:
6965:
6963:
6962:
6957:
6927:
6925:
6924:
6919:
6907:
6905:
6904:
6899:
6897:
6896:
6874:
6828:
6826:
6825:
6820:
6808:
6806:
6805:
6800:
6780:
6778:
6777:
6772:
6760:
6758:
6757:
6752:
6722:
6720:
6719:
6714:
6687:
6685:
6684:
6679:
6667:
6665:
6664:
6659:
6632:
6630:
6629:
6624:
6600:
6598:
6597:
6592:
6563:
6562:
6542:
6540:
6539:
6534:
6498:
6496:
6495:
6490:
6472:
6470:
6469:
6464:
6452:
6450:
6449:
6444:
6412:
6411:
6371:
6369:
6368:
6363:
6342:
6340:
6339:
6334:
6321:Elias delta code
6318:
6316:
6315:
6310:
6302:
6301:
6282:
6280:
6279:
6274:
6272:
6271:
6255:
6253:
6252:
6247:
6235:
6233:
6232:
6227:
6204:
6203:
6172:
6170:
6169:
6164:
6143:
6141:
6140:
6135:
6111:
6109:
6108:
6103:
6080:
6078:
6077:
6072:
6048:
6046:
6045:
6040:
6038:
6037:
6022:Run the program
6017:
6015:
6014:
6009:
5997:
5995:
5994:
5989:
5987:
5986:
5967:
5965:
5964:
5959:
5947:
5945:
5944:
5939:
5910:
5909:
5889:
5887:
5886:
5881:
5879:
5878:
5859:
5857:
5856:
5851:
5849:
5848:
5832:
5830:
5829:
5824:
5812:
5810:
5809:
5804:
5783:
5781:
5780:
5775:
5758:
5756:
5755:
5750:
5722:
5720:
5719:
5714:
5702:
5700:
5699:
5694:
5682:
5680:
5679:
5674:
5672:
5671:
5652:
5650:
5649:
5644:
5629:
5627:
5626:
5621:
5609:
5607:
5606:
5601:
5576:
5574:
5573:
5568:
5553:
5551:
5550:
5545:
5533:
5531:
5530:
5525:
5486:
5484:
5483:
5478:
5448:
5446:
5445:
5440:
5438:
5437:
5421:
5419:
5418:
5413:
5405:
5388:
5386:
5378:
5367:
5362:
5358:
5357:
5356:
5346:
5337:
5329:
5322:
5321:
5303:
5298:
5297:
5276:
5268:
5259:
5257:
5256:
5251:
5249:
5248:
5204:
5202:
5201:
5196:
5184:
5182:
5181:
5176:
5086:computer program
4954:
4920:
4919:
4912:
4901:
4344:axiomatic system
4310:
4309:
4304:
4303:
4298:
4110:) – simply
4050:) + c*max(1,log(
3960:
3954:
3948:
3942:
3936:
3930:
3924:
3918:
3912:
3906:
3900:
3894:
3888:
3882:
3870:
3866:
3862:
3861:
3858:
3855:
3845:
3844:
3841:
3838:
3832:
3831:
3828:
3825:
3819:
3782:
3778:
3777:
3774:
3771:
3740:
3739:
3736:
3721:by contradiction
3550:
3548:
3547:
3542:
3515:
3513:
3512:
3507:
3447:
3445:
3444:
3439:
3421:
3419:
3418:
3413:
3375:
3327:
3325:
3324:
3319:
3260:
3213:
3211:
3210:
3205:
3190:
3188:
3187:
3182:
3161:
3159:
3158:
3153:
3145:
3124:
3122:
3121:
3116:
3095:
3093:
3092:
3087:
3079:
3058:
3056:
3055:
3050:
3023:
3021:
3020:
3015:
2967:
2965:
2964:
2959:
2903:
2865:
2800:
2764:
2762:
2761:
2756:
2754:
2746:
2735:
2727:
2722:
2701:
2699:
2698:
2693:
2691:
2683:
2675:
2674:
2659:
2651:
2624:
2622:
2621:
2616:
2614:
2606:
2579:
2577:
2576:
2571:
2563:
2555:
2519:
2517:
2516:
2511:
2493:
2491:
2490:
2485:
2464:
2462:
2461:
2456:
2433:
2432:
2410:
2408:
2407:
2402:
2381:
2379:
2378:
2375:{\displaystyle }
2373:
2368:
2365:
2357:
2354:
2346:
2343:
2331:
2329:
2328:
2323:
2320:
2265:
2263:
2262:
2257:
2240:
2239:
2185:
2183:
2182:
2177:
2148:
2146:
2145:
2140:
2116:
2114:
2113:
2108:
2075:
2073:
2072:
2067:
1987:this theorem in
1923:
1903:
1889:is a program in
1872:
1858:is a program in
1618:Any description
1569:
1567:
1566:
1561:
1523:
1515:
1482:
1480:
1479:
1474:
1462:
1460:
1459:
1454:
1435:
1433:
1432:
1427:
1425:
1424:
1408:
1406:
1405:
1400:
1355:
1353:
1352:
1347:
1329:
1327:
1326:
1321:
1319:
1318:
1291:
1289:
1288:
1283:
1281:
1273:
1265:
1264:
1248:
1246:
1245:
1240:
1224:
1222:
1221:
1216:
1195:
1193:
1192:
1187:
1136:
1134:
1133:
1128:
1068:
1066:
1065:
1060:
1042:
1040:
1039:
1034:
1016:
1014:
1013:
1008:
960:
958:
957:
952:
940:
938:
937:
932:
920:
918:
917:
912:
855:
853:
852:
847:
835:
833:
832:
827:
804:
803:
785:
784:
759:
757:
756:
751:
749:
748:
732:
730:
729:
724:
722:
721:
709:
708:
686:
684:
683:
678:
676:
675:
663:
662:
637:
635:
634:
629:
621:
589:
559:
557:
556:
551:
500:
498:
497:
492:
453:
451:
450:
445:
424:
422:
421:
416:
241:a bitstring <
158:
152:
101:results akin to
60:computer program
48:computer science
12038:
12037:
12033:
12032:
12031:
12029:
12028:
12027:
11983:
11982:
11981:
11976:
11943:
11927:
11911:
11892:Rate–distortion
11825:
11754:
11673:
11600:
11521:
11426:
11422:Sub-band coding
11330:
11255:Predictive type
11250:
11175:
11142:LZSS + Huffman
11092:LZ77 + Huffman
11081:
10991:
10927:Dictionary type
10921:
10823:Adaptive coding
10800:
10794:
10764:
10759:
10748:
10741:
10686:Category theory
10676:Algebraic logic
10659:
10630:Lambda calculus
10568:Church encoding
10554:
10530:Truth predicate
10386:
10352:Complete theory
10275:
10144:
10140:
10136:
10131:
10123:
9843: and
9839:
9834:
9820:
9796:New Foundations
9764:axiom of choice
9747:
9709:Gödel numbering
9649: and
9641:
9545:
9430:
9380:
9361:
9310:Boolean algebra
9296:
9260:Equiconsistency
9225:Classical logic
9202:
9183:Halting problem
9171: and
9147: and
9135: and
9134:
9129:Theorems (
9124:
9041:
9036:
9001:
8934:
8907:
8889:
8858:
8835:
8812:
8793:
8774:
8715:
8713:Further reading
8710:
8665:
8661:
8654:
8632:
8628:
8621:
8599:
8595:
8588:
8566:
8562:
8550:
8549:
8540:
8539:
8527:
8495:
8491:
8472:
8468:
8461:
8447:
8440:
8423:
8419:
8411:
8370:
8364:
8360:
8331:
8327:
8318:
8314:
8281:
8277:
8270:
8254:
8250:
8217:
8211:
8207:
8167:
8161:
8157:
8149:
8142:
8135:
8131:
8124:
8110:
8106:
8087:
8083:
8076:
8046:
8042:
8011:
8007:
7966:
7962:
7939:
7935:
7927:
7902:
7896:
7892:
7884:
7859:
7853:
7849:
7841:
7826:
7820:Solomonoff, Ray
7817:
7813:
7755:
7748:
7743:
7739:
7734:
7730:
7657:
7653:
7613:
7609:
7567:
7563:
7559:
7554:
7553:
7547:
7544:2 + 2 + ... + 2
7543:
7536:2 + 2 + ... + 2
7535:
7532:
7522:
7515:
7509:
7498:
7490:
7482:
7480:
7476:
7467:
7450:
7444:
7439:
7436:
7434:
7429:
7425:
7413:
7411:
7407:
7401:
7399:
7395:
7388:
7386:
7382:
7369:
7365:
7328:
7324:
7319:
7262:
7218:
7207:
7204:
7203:
7170:
7159:
7156:
7155:
7148:
7142:
7139:
7132:needs expansion
7117:
7056:
7051:
7043:
7040:
7039:
7017:
7014:
7013:
6997:
6994:
6993:
6971:
6968:
6967:
6936:
6933:
6932:
6913:
6910:
6909:
6880:
6876:
6855:
6834:
6831:
6830:
6814:
6811:
6810:
6794:
6791:
6790:
6787:
6766:
6763:
6762:
6728:
6725:
6724:
6693:
6690:
6689:
6673:
6670:
6669:
6638:
6635:
6634:
6606:
6603:
6602:
6558:
6554:
6552:
6549:
6548:
6504:
6501:
6500:
6478:
6475:
6474:
6458:
6455:
6454:
6407:
6403:
6377:
6374:
6373:
6348:
6345:
6344:
6328:
6325:
6324:
6323:for the number
6297:
6293:
6288:
6285:
6284:
6267:
6263:
6261:
6258:
6257:
6241:
6238:
6237:
6199:
6195:
6181:
6178:
6177:
6158:
6155:
6154:
6117:
6114:
6113:
6091:
6088:
6087:
6054:
6051:
6050:
6033:
6029:
6027:
6024:
6023:
6003:
6000:
5999:
5982:
5978:
5976:
5973:
5972:
5953:
5950:
5949:
5905:
5901:
5899:
5896:
5895:
5874:
5870:
5868:
5865:
5864:
5844:
5840:
5838:
5835:
5834:
5818:
5815:
5814:
5789:
5786:
5785:
5769:
5766:
5765:
5732:
5729:
5728:
5708:
5705:
5704:
5688:
5685:
5684:
5667:
5663:
5661:
5658:
5657:
5635:
5632:
5631:
5615:
5612:
5611:
5586:
5583:
5582:
5559:
5556:
5555:
5539:
5536:
5535:
5492:
5489:
5488:
5472:
5469:
5468:
5459:
5457:Halting problem
5433:
5429:
5427:
5424:
5423:
5401:
5379:
5368:
5366:
5352:
5348:
5342:
5328:
5327:
5323:
5317:
5313:
5299:
5287:
5283:
5267:
5265:
5262:
5261:
5238:
5234:
5232:
5229:
5228:
5221:of the source.
5190:
5187:
5186:
5140:
5137:
5136:
5133:
5071:
5065:
5049:
5043:
5029:
4987:
4975:
4968:
4952:
4945:
4910:
4908:
4899:
4889:
4859:
4852:
4845:
4838:
4831:
4823:
4816:
4809:
4802:
4795:
4787:
4780:
4772:
4764:
4762:
4730:of the formula
4720:
4715:StringNthProof(
4681:
4668:
4660:StringNthProof(
4628:
4576:
4447:Berry's paradox
4392:Gödel numbering
4381:
4365:
4351:natural numbers
4307:
4306:
4301:
4300:
4289:
4282:
4170: – by the
4100:
4001:
3995:
3961:
3958:
3955:
3952:
3949:
3946:
3943:
3940:
3937:
3934:
3931:
3928:
3925:
3922:
3919:
3916:
3913:
3910:
3907:
3904:
3901:
3898:
3895:
3892:
3889:
3886:
3883:
3880:
3868:
3864:
3859:
3856:
3853:
3851:
3842:
3839:
3836:
3834:
3829:
3826:
3823:
3821:
3817:
3814:
3780:
3775:
3772:
3769:
3767:
3752:
3737:
3734:
3732:
3652:
3634:halting problem
3618:
3565:
3557:
3527:
3524:
3523:
3453:
3450:
3449:
3433:
3430:
3429:
3371:
3339:
3336:
3335:
3256:
3224:
3221:
3220:
3196:
3193:
3192:
3167:
3164:
3163:
3141:
3130:
3127:
3126:
3101:
3098:
3097:
3075:
3064:
3061:
3060:
3032:
3029:
3028:
2976:
2973:
2972:
2899:
2861:
2796:
2785:
2782:
2781:
2750:
2742:
2731:
2723:
2718:
2707:
2704:
2703:
2687:
2679:
2670:
2666:
2655:
2647:
2630:
2627:
2626:
2610:
2602:
2585:
2582:
2581:
2559:
2551:
2525:
2522:
2521:
2505:
2502:
2501:
2500:: There exists
2470:
2467:
2466:
2428:
2424:
2416:
2413:
2412:
2387:
2384:
2383:
2364:
2353:
2342:
2337:
2334:
2333:
2316:
2277:
2274:
2273:
2235:
2231:
2196:
2193:
2192:
2162:
2159:
2158:
2155:
2122:
2119:
2118:
2081:
2078:
2077:
2046:
2043:
2042:
2039:
1993:Gregory Chaitin
1963:data structures
1956:
1941:
1921:
1901:
1895:
1870:
1864:
1852:
1837:
1826:
1807:
1796:
1764:
1753:
1734:
1727:
1716:
1709:
1701:Turing complete
1698:
1691:
1680:
1580:
1575:
1519:
1511:
1488:
1485:
1484:
1468:
1465:
1464:
1448:
1445:
1444:
1420:
1416:
1414:
1411:
1410:
1394:
1391:
1390:
1335:
1332:
1331:
1314:
1310:
1308:
1305:
1304:
1301:
1277:
1269:
1260:
1256:
1254:
1251:
1250:
1234:
1231:
1230:
1201:
1198:
1197:
1145:
1142:
1141:
1074:
1071:
1070:
1048:
1045:
1044:
1022:
1019:
1018:
966:
963:
962:
946:
943:
942:
926:
923:
922:
864:
861:
860:
841:
838:
837:
799:
795:
780:
776:
765:
762:
761:
744:
740:
738:
735:
734:
717:
713:
704:
700:
692:
689:
688:
671:
667:
658:
654:
646:
643:
642:
617:
585:
565:
562:
561:
506:
503:
502:
462:
459:
458:
430:
427:
426:
401:
398:
397:
386:
304:
291:
231:Turing machines
156:
150:
140:
135:
46:(a subfield of
17:
12:
11:
5:
12036:
12026:
12025:
12020:
12015:
12010:
12005:
12000:
11995:
11978:
11977:
11975:
11974:
11959:
11948:
11945:
11944:
11942:
11941:
11935:
11933:
11929:
11928:
11926:
11925:
11919:
11917:
11913:
11912:
11910:
11909:
11904:
11899:
11894:
11889:
11884:
11879:
11874:
11873:
11872:
11862:
11857:
11856:
11855:
11850:
11839:
11837:
11831:
11830:
11827:
11826:
11824:
11823:
11822:
11821:
11816:
11806:
11805:
11804:
11799:
11794:
11786:
11781:
11776:
11771:
11765:
11763:
11756:
11755:
11753:
11752:
11747:
11742:
11737:
11732:
11727:
11722:
11717:
11716:
11715:
11710:
11705:
11694:
11692:
11685:
11679:
11678:
11675:
11674:
11672:
11671:
11670:
11669:
11664:
11659:
11654:
11644:
11639:
11634:
11629:
11624:
11619:
11614:
11608:
11606:
11602:
11601:
11599:
11598:
11593:
11588:
11583:
11578:
11573:
11568:
11563:
11558:
11553:
11548:
11542:
11540:
11533:
11527:
11526:
11523:
11522:
11520:
11519:
11514:
11509:
11508:
11507:
11502:
11497:
11492:
11487:
11477:
11476:
11475:
11465:
11464:
11463:
11458:
11448:
11443:
11437:
11435:
11428:
11427:
11425:
11424:
11419:
11414:
11409:
11404:
11399:
11394:
11389:
11384:
11379:
11374:
11373:
11372:
11367:
11362:
11351:
11349:
11342:
11336:
11335:
11332:
11331:
11329:
11328:
11326:Psychoacoustic
11323:
11322:
11321:
11316:
11311:
11303:
11302:
11301:
11296:
11291:
11286:
11281:
11271:
11270:
11269:
11258:
11256:
11252:
11251:
11249:
11248:
11247:
11246:
11241:
11236:
11226:
11221:
11216:
11215:
11214:
11209:
11198:
11196:
11194:Transform type
11187:
11181:
11180:
11177:
11176:
11174:
11173:
11172:
11171:
11163:
11162:
11161:
11158:
11150:
11149:
11148:
11140:
11139:
11138:
11130:
11129:
11128:
11120:
11119:
11118:
11110:
11109:
11108:
11103:
11098:
11089:
11087:
11083:
11082:
11080:
11079:
11074:
11069:
11064:
11059:
11054:
11053:
11052:
11047:
11037:
11032:
11027:
11026:
11025:
11015:
11010:
11005:
10999:
10997:
10993:
10992:
10990:
10989:
10988:
10987:
10982:
10977:
10972:
10967:
10962:
10957:
10952:
10947:
10937:
10931:
10929:
10923:
10922:
10920:
10919:
10918:
10917:
10912:
10907:
10902:
10892:
10887:
10882:
10877:
10872:
10867:
10862:
10861:
10860:
10855:
10850:
10840:
10835:
10830:
10825:
10819:
10817:
10808:
10802:
10801:
10793:
10792:
10785:
10778:
10770:
10761:
10760:
10746:
10743:
10742:
10740:
10739:
10734:
10729:
10724:
10719:
10718:
10717:
10707:
10702:
10697:
10688:
10683:
10678:
10673:
10671:Abstract logic
10667:
10665:
10661:
10660:
10658:
10657:
10652:
10650:Turing machine
10647:
10642:
10637:
10632:
10627:
10622:
10621:
10620:
10615:
10610:
10605:
10600:
10590:
10588:Computable set
10585:
10580:
10575:
10570:
10564:
10562:
10556:
10555:
10553:
10552:
10547:
10542:
10537:
10532:
10527:
10522:
10517:
10516:
10515:
10510:
10505:
10495:
10490:
10485:
10483:Satisfiability
10480:
10475:
10470:
10469:
10468:
10458:
10457:
10456:
10446:
10445:
10444:
10439:
10434:
10429:
10424:
10414:
10413:
10412:
10407:
10400:Interpretation
10396:
10394:
10388:
10387:
10385:
10384:
10379:
10374:
10369:
10364:
10354:
10349:
10348:
10347:
10346:
10345:
10335:
10330:
10320:
10315:
10310:
10305:
10300:
10295:
10289:
10287:
10281:
10280:
10277:
10276:
10274:
10273:
10265:
10264:
10263:
10262:
10257:
10256:
10255:
10250:
10245:
10225:
10224:
10223:
10221:minimal axioms
10218:
10207:
10206:
10205:
10194:
10193:
10192:
10187:
10182:
10177:
10172:
10167:
10154:
10152:
10133:
10132:
10130:
10129:
10128:
10127:
10115:
10110:
10109:
10108:
10103:
10098:
10093:
10083:
10078:
10073:
10068:
10067:
10066:
10061:
10051:
10050:
10049:
10044:
10039:
10034:
10024:
10019:
10018:
10017:
10012:
10007:
9997:
9996:
9995:
9990:
9985:
9980:
9975:
9970:
9960:
9955:
9950:
9945:
9944:
9943:
9938:
9933:
9928:
9918:
9913:
9911:Formation rule
9908:
9903:
9902:
9901:
9896:
9886:
9885:
9884:
9874:
9869:
9864:
9859:
9853:
9847:
9830:Formal systems
9826:
9825:
9822:
9821:
9819:
9818:
9813:
9808:
9803:
9798:
9793:
9788:
9783:
9778:
9773:
9772:
9771:
9766:
9755:
9753:
9749:
9748:
9746:
9745:
9744:
9743:
9733:
9728:
9727:
9726:
9719:Large cardinal
9716:
9711:
9706:
9701:
9696:
9682:
9681:
9680:
9675:
9670:
9655:
9653:
9643:
9642:
9640:
9639:
9638:
9637:
9632:
9627:
9617:
9612:
9607:
9602:
9597:
9592:
9587:
9582:
9577:
9572:
9567:
9562:
9556:
9554:
9547:
9546:
9544:
9543:
9542:
9541:
9536:
9531:
9526:
9521:
9516:
9508:
9507:
9506:
9501:
9491:
9486:
9484:Extensionality
9481:
9479:Ordinal number
9476:
9466:
9461:
9460:
9459:
9448:
9442:
9436:
9435:
9432:
9431:
9429:
9428:
9423:
9418:
9413:
9408:
9403:
9398:
9397:
9396:
9386:
9385:
9384:
9371:
9369:
9363:
9362:
9360:
9359:
9358:
9357:
9352:
9347:
9337:
9332:
9327:
9322:
9317:
9312:
9306:
9304:
9298:
9297:
9295:
9294:
9289:
9284:
9279:
9274:
9269:
9264:
9263:
9262:
9252:
9247:
9242:
9237:
9232:
9227:
9221:
9219:
9210:
9204:
9203:
9201:
9200:
9195:
9190:
9185:
9180:
9175:
9163:Cantor's
9161:
9156:
9151:
9141:
9139:
9126:
9125:
9123:
9122:
9117:
9112:
9107:
9102:
9097:
9092:
9087:
9082:
9077:
9072:
9067:
9062:
9061:
9060:
9049:
9047:
9043:
9042:
9035:
9034:
9027:
9020:
9012:
9006:
9005:
8999:
8986:
8972:
8950:
8940:
8932:
8930:J. Schmidhuber
8923:
8918:
8913:
8906:
8905:External links
8903:
8902:
8901:
8887:
8862:
8856:
8839:
8833:
8816:
8811:978-0387339986
8810:
8797:
8791:
8778:
8772:
8759:
8746:
8714:
8711:
8709:
8708:
8659:
8652:
8626:
8619:
8593:
8586:
8560:
8551:|journal=
8525:
8489:
8466:
8459:
8438:
8417:
8358:
8345:(6): 602–619.
8325:
8312:
8291:(4): 270–283.
8275:
8268:
8248:
8246:Here: Thm.4.1b
8228:(3): 403–434.
8205:
8155:
8152:on 2009-09-09.
8129:
8122:
8104:
8081:
8074:
8040:
8021:(5): 662–664.
8005:
7983:10.1.1.15.3821
7976:(3): 407–422.
7960:
7933:
7913:(2): 224–254.
7890:
7847:
7811:
7760:(2007-03-06).
7758:Hutter, Marcus
7746:
7737:
7728:
7651:
7630:(2): 387–395.
7607:
7580:(4): 369–375.
7560:
7558:
7555:
7552:
7551:
7527:
7520:
7513:
7486:
7474:
7465:
7448:
7405:
7393:
7380:
7363:
7321:
7320:
7318:
7315:
7314:
7313:
7311:Sample entropy
7308:
7303:
7298:
7293:
7288:
7283:
7278:
7273:
7268:
7261:
7258:
7237:
7234:
7231:
7228:
7225:
7221:
7217:
7214:
7211:
7180:
7177:
7173:
7169:
7166:
7163:
7150:
7149:
7129:
7127:
7116:
7113:
7101:
7098:
7095:
7092:
7089:
7086:
7083:
7080:
7077:
7074:
7068:
7065:
7062:
7059:
7055:
7050:
7047:
7021:
7001:
6981:
6978:
6975:
6955:
6952:
6949:
6946:
6943:
6940:
6917:
6895:
6892:
6889:
6886:
6883:
6879:
6873:
6870:
6867:
6864:
6861:
6858:
6854:
6850:
6847:
6844:
6841:
6838:
6818:
6798:
6786:
6783:
6774:{\textstyle x}
6770:
6750:
6747:
6744:
6741:
6738:
6735:
6732:
6712:
6709:
6706:
6703:
6700:
6697:
6681:{\textstyle x}
6677:
6657:
6654:
6651:
6648:
6645:
6642:
6622:
6619:
6616:
6613:
6610:
6590:
6587:
6584:
6581:
6578:
6575:
6572:
6569:
6566:
6561:
6557:
6532:
6529:
6526:
6523:
6520:
6517:
6514:
6511:
6508:
6488:
6485:
6482:
6466:{\textstyle n}
6462:
6442:
6439:
6436:
6433:
6430:
6427:
6424:
6421:
6418:
6415:
6410:
6406:
6402:
6399:
6396:
6393:
6390:
6387:
6384:
6381:
6361:
6358:
6355:
6352:
6332:
6308:
6305:
6300:
6296:
6292:
6270:
6266:
6245:
6225:
6222:
6219:
6216:
6213:
6210:
6207:
6202:
6198:
6194:
6191:
6188:
6185:
6166:{\textstyle x}
6162:
6151:
6150:
6146:
6145:
6133:
6130:
6127:
6124:
6121:
6101:
6098:
6095:
6083:
6082:
6070:
6067:
6064:
6061:
6058:
6036:
6032:
6007:
5985:
5981:
5961:{\textstyle n}
5957:
5948:for all large
5937:
5934:
5931:
5928:
5925:
5922:
5919:
5916:
5913:
5908:
5904:
5892:
5891:
5877:
5873:
5861:
5847:
5843:
5826:{\textstyle x}
5822:
5802:
5799:
5796:
5793:
5777:{\textstyle x}
5773:
5761:
5760:
5748:
5745:
5742:
5739:
5736:
5716:{\textstyle K}
5712:
5696:{\textstyle n}
5692:
5670:
5666:
5642:
5639:
5619:
5599:
5596:
5593:
5590:
5566:
5563:
5543:
5534:for all large
5523:
5520:
5517:
5514:
5511:
5508:
5505:
5502:
5499:
5496:
5476:
5458:
5455:
5436:
5432:
5411:
5408:
5404:
5400:
5397:
5394:
5391:
5385:
5382:
5377:
5374:
5371:
5365:
5361:
5355:
5351:
5345:
5341:
5335:
5332:
5326:
5320:
5316:
5312:
5309:
5306:
5302:
5296:
5293:
5290:
5286:
5282:
5279:
5274:
5271:
5247:
5244:
5241:
5237:
5194:
5174:
5171:
5168:
5165:
5162:
5159:
5156:
5153:
5150:
5147:
5144:
5132:
5129:
5105:measure theory
5064:
5061:
5045:Main article:
5042:
5039:
5027:
5013:
5012:
5005:
5003:
4993:
4989:
4988:
4985:
4979:
4977:
4973:
4966:
4960:
4956:
4955:
4949:
4946:
4943:
4938:
4934:
4933:
4923:
4906:
4887:
4857:
4850:
4843:
4836:
4829:
4821:
4814:
4807:
4800:
4793:
4785:
4778:
4770:
4760:
4755:
4738:) ≥
4685:
4669:
4656:
4646:. The strings
4642:) ≥
4616:
4598:) ≥
4564:
4433:
4432:
4377:
4361:
4281:
4278:
4266:
4265:
4258:
4257:
4168:incompressible
4158:. Otherwise,
4099:
4096:
4064:
4063:
3997:Main article:
3994:
3991:
3957:
3951:
3945:
3939:
3933:
3927:
3921:
3915:
3909:
3903:
3897:
3891:
3885:
3879:
3785:
3743:
3723:uses a simple
3716:The following
3651:
3645:
3581:
3564:
3558:
3556:
3553:
3540:
3537:
3534:
3531:
3505:
3502:
3499:
3496:
3493:
3490:
3487:
3484:
3481:
3478:
3475:
3472:
3469:
3466:
3463:
3460:
3457:
3437:
3411:
3408:
3405:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3374:
3370:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3317:
3314:
3311:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3284:
3281:
3278:
3275:
3272:
3269:
3266:
3263:
3259:
3255:
3252:
3249:
3246:
3243:
3240:
3237:
3234:
3231:
3228:
3203:
3200:
3180:
3177:
3174:
3171:
3151:
3148:
3144:
3140:
3137:
3134:
3114:
3111:
3108:
3105:
3085:
3082:
3078:
3074:
3071:
3068:
3048:
3045:
3042:
3039:
3036:
3025:
3024:
3013:
3010:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2969:
2968:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2906:
2902:
2898:
2895:
2892:
2889:
2886:
2883:
2880:
2877:
2874:
2871:
2868:
2864:
2860:
2857:
2854:
2851:
2848:
2845:
2842:
2839:
2836:
2833:
2830:
2827:
2824:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2799:
2795:
2792:
2789:
2753:
2749:
2745:
2741:
2738:
2734:
2730:
2726:
2721:
2717:
2714:
2711:
2690:
2686:
2682:
2678:
2673:
2669:
2665:
2662:
2658:
2654:
2650:
2646:
2643:
2640:
2637:
2634:
2613:
2609:
2605:
2601:
2598:
2595:
2592:
2589:
2569:
2566:
2562:
2558:
2554:
2550:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2509:
2483:
2480:
2477:
2474:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2431:
2427:
2423:
2420:
2400:
2397:
2394:
2391:
2371:
2363:
2360:
2352:
2349:
2341:
2319:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2255:
2252:
2249:
2246:
2243:
2238:
2234:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2175:
2172:
2169:
2166:
2154:
2151:
2138:
2135:
2132:
2129:
2126:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2065:
2062:
2059:
2056:
2053:
2050:
2038:
2035:
2013:Matthew effect
1970:Ray Solomonoff
1955:
1952:
1948:
1947:
1939:
1931:The length of
1929:
1916:is the sum of
1893:
1883:
1882:
1862:
1840:
1835:
1824:
1818:
1817:
1805:
1794:
1775:
1774:
1762:
1751:
1732:
1725:
1714:
1707:
1696:
1689:
1679:
1676:
1662:The length of
1660:
1659:
1595:
1594:
1591:
1579:
1576:
1574:
1571:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1522:
1518:
1514:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1472:
1452:
1438:
1437:
1423:
1419:
1398:
1387:
1384:
1381:
1345:
1342:
1339:
1317:
1313:
1300:
1294:
1280:
1276:
1272:
1268:
1263:
1259:
1238:
1214:
1211:
1208:
1205:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1058:
1055:
1052:
1032:
1029:
1026:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
950:
930:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
845:
825:
822:
819:
816:
813:
810:
807:
802:
798:
794:
791:
788:
783:
779:
775:
772:
769:
747:
743:
720:
716:
712:
707:
703:
699:
696:
674:
670:
666:
661:
657:
653:
650:
627:
624:
620:
616:
613:
610:
607:
604:
601:
598:
595:
592:
588:
584:
581:
578:
575:
572:
569:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
490:
487:
484:
481:
478:
475:
472:
469:
466:
443:
440:
437:
434:
414:
411:
408:
405:
385:
379:
371:
370:
314:) of a string
295:
282:
160:
159:
154:
139:
136:
134:
131:
25:Mandelbrot set
15:
9:
6:
4:
3:
2:
12035:
12024:
12021:
12019:
12016:
12014:
12011:
12009:
12006:
12004:
12001:
11999:
11996:
11994:
11991:
11990:
11988:
11972:
11968:
11960:
11958:
11950:
11949:
11946:
11940:
11937:
11936:
11934:
11930:
11924:
11921:
11920:
11918:
11914:
11908:
11905:
11903:
11900:
11898:
11895:
11893:
11890:
11888:
11885:
11883:
11880:
11878:
11875:
11871:
11868:
11867:
11866:
11863:
11861:
11858:
11854:
11851:
11849:
11846:
11845:
11844:
11841:
11840:
11838:
11836:
11832:
11820:
11817:
11815:
11812:
11811:
11810:
11807:
11803:
11800:
11798:
11795:
11793:
11790:
11789:
11787:
11785:
11782:
11780:
11777:
11775:
11772:
11770:
11767:
11766:
11764:
11761:
11757:
11751:
11750:Video quality
11748:
11746:
11743:
11741:
11738:
11736:
11733:
11731:
11728:
11726:
11723:
11721:
11718:
11714:
11711:
11709:
11706:
11704:
11701:
11700:
11699:
11696:
11695:
11693:
11689:
11686:
11684:
11680:
11668:
11665:
11663:
11660:
11658:
11655:
11653:
11650:
11649:
11648:
11645:
11643:
11640:
11638:
11635:
11633:
11630:
11628:
11625:
11623:
11620:
11618:
11615:
11613:
11610:
11609:
11607:
11603:
11597:
11594:
11592:
11589:
11587:
11584:
11582:
11579:
11577:
11574:
11572:
11569:
11567:
11564:
11562:
11559:
11557:
11554:
11552:
11549:
11547:
11544:
11543:
11541:
11537:
11534:
11532:
11528:
11518:
11515:
11513:
11510:
11506:
11503:
11501:
11498:
11496:
11493:
11491:
11488:
11486:
11483:
11482:
11481:
11478:
11474:
11471:
11470:
11469:
11466:
11462:
11459:
11457:
11454:
11453:
11452:
11449:
11447:
11444:
11442:
11439:
11438:
11436:
11433:
11429:
11423:
11420:
11418:
11417:Speech coding
11415:
11413:
11412:Sound quality
11410:
11408:
11405:
11403:
11400:
11398:
11395:
11393:
11390:
11388:
11387:Dynamic range
11385:
11383:
11380:
11378:
11375:
11371:
11368:
11366:
11363:
11361:
11358:
11357:
11356:
11353:
11352:
11350:
11346:
11343:
11341:
11337:
11327:
11324:
11320:
11317:
11315:
11312:
11310:
11307:
11306:
11304:
11300:
11297:
11295:
11292:
11290:
11287:
11285:
11282:
11280:
11277:
11276:
11275:
11272:
11268:
11265:
11264:
11263:
11260:
11259:
11257:
11253:
11245:
11242:
11240:
11237:
11235:
11232:
11231:
11230:
11227:
11225:
11222:
11220:
11217:
11213:
11210:
11208:
11205:
11204:
11203:
11200:
11199:
11197:
11195:
11191:
11188:
11186:
11182:
11170:
11167:
11166:
11164:
11159:
11157:
11154:
11153:
11152:LZ77 + Range
11151:
11147:
11144:
11143:
11141:
11137:
11134:
11133:
11131:
11127:
11124:
11123:
11121:
11117:
11114:
11113:
11111:
11107:
11104:
11102:
11099:
11097:
11094:
11093:
11091:
11090:
11088:
11084:
11078:
11075:
11073:
11070:
11068:
11065:
11063:
11060:
11058:
11055:
11051:
11048:
11046:
11043:
11042:
11041:
11038:
11036:
11033:
11031:
11028:
11024:
11021:
11020:
11019:
11016:
11014:
11011:
11009:
11006:
11004:
11001:
11000:
10998:
10994:
10986:
10983:
10981:
10978:
10976:
10973:
10971:
10968:
10966:
10963:
10961:
10958:
10956:
10953:
10951:
10948:
10946:
10943:
10942:
10941:
10938:
10936:
10933:
10932:
10930:
10928:
10924:
10916:
10913:
10911:
10908:
10906:
10903:
10901:
10898:
10897:
10896:
10893:
10891:
10888:
10886:
10883:
10881:
10878:
10876:
10873:
10871:
10868:
10866:
10863:
10859:
10856:
10854:
10851:
10849:
10846:
10845:
10844:
10841:
10839:
10836:
10834:
10831:
10829:
10826:
10824:
10821:
10820:
10818:
10816:
10812:
10809:
10807:
10803:
10798:
10791:
10786:
10784:
10779:
10777:
10772:
10771:
10768:
10758:
10757:
10752:
10744:
10738:
10735:
10733:
10730:
10728:
10725:
10723:
10720:
10716:
10713:
10712:
10711:
10708:
10706:
10703:
10701:
10698:
10696:
10692:
10689:
10687:
10684:
10682:
10679:
10677:
10674:
10672:
10669:
10668:
10666:
10662:
10656:
10653:
10651:
10648:
10646:
10645:Recursive set
10643:
10641:
10638:
10636:
10633:
10631:
10628:
10626:
10623:
10619:
10616:
10614:
10611:
10609:
10606:
10604:
10601:
10599:
10596:
10595:
10594:
10591:
10589:
10586:
10584:
10581:
10579:
10576:
10574:
10571:
10569:
10566:
10565:
10563:
10561:
10557:
10551:
10548:
10546:
10543:
10541:
10538:
10536:
10533:
10531:
10528:
10526:
10523:
10521:
10518:
10514:
10511:
10509:
10506:
10504:
10501:
10500:
10499:
10496:
10494:
10491:
10489:
10486:
10484:
10481:
10479:
10476:
10474:
10471:
10467:
10464:
10463:
10462:
10459:
10455:
10454:of arithmetic
10452:
10451:
10450:
10447:
10443:
10440:
10438:
10435:
10433:
10430:
10428:
10425:
10423:
10420:
10419:
10418:
10415:
10411:
10408:
10406:
10403:
10402:
10401:
10398:
10397:
10395:
10393:
10389:
10383:
10380:
10378:
10375:
10373:
10370:
10368:
10365:
10362:
10361:from ZFC
10358:
10355:
10353:
10350:
10344:
10341:
10340:
10339:
10336:
10334:
10331:
10329:
10326:
10325:
10324:
10321:
10319:
10316:
10314:
10311:
10309:
10306:
10304:
10301:
10299:
10296:
10294:
10291:
10290:
10288:
10286:
10282:
10272:
10271:
10267:
10266:
10261:
10260:non-Euclidean
10258:
10254:
10251:
10249:
10246:
10244:
10243:
10239:
10238:
10236:
10233:
10232:
10230:
10226:
10222:
10219:
10217:
10214:
10213:
10212:
10208:
10204:
10201:
10200:
10199:
10195:
10191:
10188:
10186:
10183:
10181:
10178:
10176:
10173:
10171:
10168:
10166:
10163:
10162:
10160:
10156:
10155:
10153:
10148:
10142:
10137:Example
10134:
10126:
10121:
10120:
10119:
10116:
10114:
10111:
10107:
10104:
10102:
10099:
10097:
10094:
10092:
10089:
10088:
10087:
10084:
10082:
10079:
10077:
10074:
10072:
10069:
10065:
10062:
10060:
10057:
10056:
10055:
10052:
10048:
10045:
10043:
10040:
10038:
10035:
10033:
10030:
10029:
10028:
10025:
10023:
10020:
10016:
10013:
10011:
10008:
10006:
10003:
10002:
10001:
9998:
9994:
9991:
9989:
9986:
9984:
9981:
9979:
9976:
9974:
9971:
9969:
9966:
9965:
9964:
9961:
9959:
9956:
9954:
9951:
9949:
9946:
9942:
9939:
9937:
9934:
9932:
9929:
9927:
9924:
9923:
9922:
9919:
9917:
9914:
9912:
9909:
9907:
9904:
9900:
9897:
9895:
9894:by definition
9892:
9891:
9890:
9887:
9883:
9880:
9879:
9878:
9875:
9873:
9870:
9868:
9865:
9863:
9860:
9858:
9855:
9854:
9851:
9848:
9846:
9842:
9837:
9831:
9827:
9817:
9814:
9812:
9809:
9807:
9804:
9802:
9799:
9797:
9794:
9792:
9789:
9787:
9784:
9782:
9781:Kripke–Platek
9779:
9777:
9774:
9770:
9767:
9765:
9762:
9761:
9760:
9757:
9756:
9754:
9750:
9742:
9739:
9738:
9737:
9734:
9732:
9729:
9725:
9722:
9721:
9720:
9717:
9715:
9712:
9710:
9707:
9705:
9702:
9700:
9697:
9694:
9690:
9686:
9683:
9679:
9676:
9674:
9671:
9669:
9666:
9665:
9664:
9660:
9657:
9656:
9654:
9652:
9648:
9644:
9636:
9633:
9631:
9628:
9626:
9625:constructible
9623:
9622:
9621:
9618:
9616:
9613:
9611:
9608:
9606:
9603:
9601:
9598:
9596:
9593:
9591:
9588:
9586:
9583:
9581:
9578:
9576:
9573:
9571:
9568:
9566:
9563:
9561:
9558:
9557:
9555:
9553:
9548:
9540:
9537:
9535:
9532:
9530:
9527:
9525:
9522:
9520:
9517:
9515:
9512:
9511:
9509:
9505:
9502:
9500:
9497:
9496:
9495:
9492:
9490:
9487:
9485:
9482:
9480:
9477:
9475:
9471:
9467:
9465:
9462:
9458:
9455:
9454:
9453:
9450:
9449:
9446:
9443:
9441:
9437:
9427:
9424:
9422:
9419:
9417:
9414:
9412:
9409:
9407:
9404:
9402:
9399:
9395:
9392:
9391:
9390:
9387:
9383:
9378:
9377:
9376:
9373:
9372:
9370:
9368:
9364:
9356:
9353:
9351:
9348:
9346:
9343:
9342:
9341:
9338:
9336:
9333:
9331:
9328:
9326:
9323:
9321:
9318:
9316:
9313:
9311:
9308:
9307:
9305:
9303:
9302:Propositional
9299:
9293:
9290:
9288:
9285:
9283:
9280:
9278:
9275:
9273:
9270:
9268:
9265:
9261:
9258:
9257:
9256:
9253:
9251:
9248:
9246:
9243:
9241:
9238:
9236:
9233:
9231:
9230:Logical truth
9228:
9226:
9223:
9222:
9220:
9218:
9214:
9211:
9209:
9205:
9199:
9196:
9194:
9191:
9189:
9186:
9184:
9181:
9179:
9176:
9174:
9170:
9166:
9162:
9160:
9157:
9155:
9152:
9150:
9146:
9143:
9142:
9140:
9138:
9132:
9127:
9121:
9118:
9116:
9113:
9111:
9108:
9106:
9103:
9101:
9098:
9096:
9093:
9091:
9088:
9086:
9083:
9081:
9078:
9076:
9073:
9071:
9068:
9066:
9063:
9059:
9056:
9055:
9054:
9051:
9050:
9048:
9044:
9040:
9033:
9028:
9026:
9021:
9019:
9014:
9013:
9010:
9002:
9000:0-262-07262-9
8996:
8993:. MIT Press.
8992:
8987:
8984:
8983:Occam's razor
8980:
8976:
8973:
8971:
8970:3-540-22139-5
8967:
8963:
8959:
8958:3-540-22139-5
8955:
8951:
8946:
8943:Tromp, John.
8941:
8937:
8933:
8931:
8927:
8924:
8922:
8919:
8917:
8914:
8912:
8909:
8908:
8898:
8894:
8890:
8884:
8880:
8876:
8872:
8868:
8863:
8859:
8857:0-534-95097-3
8853:
8848:
8847:
8840:
8836:
8830:
8825:
8824:
8817:
8813:
8807:
8803:
8798:
8794:
8792:963-279-014-6
8788:
8784:
8779:
8775:
8773:0-471-24195-4
8769:
8765:
8760:
8756:
8752:
8747:
8742:
8737:
8733:
8729:
8725:
8721:
8717:
8716:
8704:
8700:
8696:
8692:
8687:
8682:
8678:
8674:
8670:
8663:
8655:
8649:
8645:
8640:
8639:
8630:
8622:
8616:
8612:
8607:
8606:
8597:
8589:
8583:
8579:
8574:
8573:
8564:
8556:
8544:
8536:
8532:
8528:
8522:
8518:
8514:
8510:
8506:
8502:
8501:
8493:
8485:
8481:
8477:
8470:
8462:
8460:0-471-24195-4
8456:
8452:
8445:
8443:
8433:
8432:cs.CC/0404039
8428:
8421:
8410:
8406:
8402:
8398:
8394:
8389:
8384:
8380:
8376:
8369:
8362:
8353:
8348:
8344:
8340:
8336:
8329:
8322:
8316:
8308:
8304:
8299:
8298:10.1.1.17.321
8294:
8290:
8286:
8279:
8271:
8269:9783540434665
8265:
8261:
8260:
8252:
8243:
8239:
8235:
8231:
8227:
8223:
8216:
8209:
8201:
8197:
8193:
8189:
8185:
8181:
8178:(6): 83–124.
8177:
8173:
8166:
8159:
8148:
8141:
8133:
8125:
8119:
8115:
8108:
8100:
8096:
8092:
8085:
8077:
8071:
8067:
8063:
8059:
8054:
8053:
8044:
8036:
8032:
8028:
8024:
8020:
8016:
8009:
8001:
7997:
7993:
7989:
7984:
7979:
7975:
7971:
7964:
7956:
7952:
7948:
7944:
7937:
7926:
7921:
7916:
7912:
7908:
7901:
7894:
7883:
7878:
7873:
7869:
7865:
7858:
7851:
7840:
7836:
7832:
7825:
7821:
7815:
7807:
7803:
7798:
7793:
7788:
7783:
7779:
7775:
7771:
7767:
7763:
7759:
7753:
7751:
7741:
7732:
7724:
7720:
7715:
7710:
7706:
7702:
7697:
7692:
7688:
7684:
7679:
7674:
7670:
7666:
7662:
7655:
7647:
7643:
7638:
7633:
7629:
7625:
7621:
7617:
7611:
7603:
7599:
7595:
7591:
7587:
7583:
7579:
7575:
7571:
7565:
7561:
7541:
7530:
7526:
7519:
7512:
7505:
7502:= 0, 1, ...,
7501:
7496:
7489:
7485:
7481:As there are
7478:
7471:
7463:
7458:
7454:
7432:
7423:
7419:
7409:
7397:
7384:
7377:
7373:
7367:
7360:
7356:
7352:
7348:
7344:
7340:
7336:
7332:
7326:
7322:
7312:
7309:
7307:
7304:
7302:
7299:
7297:
7294:
7292:
7289:
7287:
7284:
7282:
7279:
7277:
7274:
7272:
7269:
7267:
7266:Berry paradox
7264:
7263:
7257:
7255:
7251:
7229:
7223:
7215:
7209:
7200:
7198:
7194:
7175:
7167:
7161:
7146:
7137:
7133:
7130:This section
7128:
7125:
7121:
7120:
7112:
7096:
7090:
7087:
7081:
7075:
7072:
7063:
7057:
7053:
7048:
7045:
7037:
7033:
7019:
6999:
6979:
6976:
6973:
6953:
6950:
6944:
6938:
6929:
6915:
6890:
6884:
6881:
6877:
6871:
6868:
6862:
6856:
6852:
6848:
6842:
6836:
6816:
6796:
6782:
6768:
6748:
6745:
6742:
6736:
6730:
6707:
6701:
6698:
6695:
6675:
6652:
6646:
6643:
6640:
6620:
6617:
6614:
6611:
6608:
6585:
6579:
6576:
6573:
6567:
6559:
6555:
6546:
6530:
6527:
6524:
6521:
6518:
6512:
6506:
6486:
6483:
6480:
6460:
6440:
6437:
6434:
6428:
6422:
6419:
6416:
6413:
6408:
6404:
6400:
6397:
6394:
6391:
6385:
6379:
6356:
6350:
6330:
6322:
6306:
6303:
6298:
6294:
6290:
6268:
6264:
6243:
6220:
6214:
6211:
6208:
6205:
6200:
6196:
6192:
6189:
6186:
6183:
6174:
6160:
6148:
6147:
6128:
6122:
6119:
6099:
6096:
6093:
6085:
6084:
6065:
6059:
6056:
6034:
6030:
6021:
6020:
6019:
6005:
5983:
5979:
5969:
5955:
5932:
5926:
5923:
5920:
5914:
5906:
5902:
5875:
5871:
5862:
5845:
5841:
5820:
5797:
5791:
5771:
5763:
5762:
5746:
5743:
5740:
5737:
5734:
5726:
5725:
5724:
5710:
5690:
5668:
5664:
5654:
5640:
5637:
5617:
5594:
5588:
5580:
5564:
5561:
5541:
5518:
5512:
5509:
5506:
5500:
5494:
5474:
5465:
5462:
5454:
5452:
5434:
5430:
5406:
5402:
5398:
5392:
5389:
5383:
5380:
5375:
5372:
5369:
5363:
5359:
5353:
5349:
5343:
5339:
5333:
5330:
5324:
5318:
5314:
5310:
5304:
5294:
5291:
5288:
5284:
5277:
5272:
5269:
5245:
5242:
5239:
5235:
5226:
5222:
5220:
5215:
5211:
5206:
5192:
5169:
5163:
5160:
5154:
5151:
5148:
5142:
5128:
5126:
5122:
5118:
5114:
5110:
5106:
5102:
5098:
5093:
5091:
5087:
5083:
5079:
5075:
5070:
5060:
5058:
5054:
5048:
5038:
5036:
5031:
5026:
5021:
5020:
5010:
5006:
5004:
5001:
4997:
4994:
4991:
4990:
4984:
4980:
4978:
4972:
4964:
4961:
4958:
4957:
4950:
4947:
4942:
4939:
4936:
4935:
4931:
4927:
4924:
4922:
4921:
4918:
4916:
4905:
4897:
4893:
4886:
4882:
4878:
4874:
4870:
4865:
4863:
4856:
4849:
4842:
4835:
4827:
4820:
4813:
4806:
4799:
4791:
4784:
4776:
4769:
4759:
4754:
4751:
4749:
4746: ≥
4745:
4741:
4737:
4733:
4729:
4725:
4718:
4714:
4711:
4707:
4703:
4699:
4695:
4692:
4688:
4684:
4679:
4676:
4672:
4666:
4663:
4659:
4655:
4653:
4649:
4645:
4641:
4637:
4633:
4626:
4623:
4619:
4615:
4613:
4609:
4605:
4601:
4597:
4593:
4589:
4585:
4581:
4574:
4571:
4567:
4563:
4561:
4556:
4554:
4550:
4548:
4544:
4540:
4536:
4532:
4528:
4524:
4520:
4516:
4512:
4508:
4504:
4500:
4496:
4493:as stated in
4492:
4488:
4484:
4480:
4476:
4472:
4468:
4464:
4460:
4456:
4452:
4448:
4444:
4440:
4438:
4430:
4426:
4422:
4418:
4415:
4414:
4413:
4411:
4407:
4403:
4399:
4395:
4393:
4389:
4385:
4380:
4376:
4371:
4369:
4364:
4360:
4356:
4352:
4348:
4345:
4341:
4333:
4329:
4325:
4321:
4318:
4314:
4296:
4292:
4286:
4277:
4275:
4271:
4263:
4262:
4261:
4255:
4254:
4253:
4251:
4247:
4242:
4240:
4236:
4232:
4228:
4226:
4222:
4219:
4215:
4211:
4207:
4203:
4199:
4195:
4190:
4189:
4185:
4181:
4177:
4173:
4169:
4165:
4161:
4157:
4153:
4149:
4145:
4141:
4137:
4133:
4129:
4124:
4122:
4117:
4113:
4109:
4105:
4095:
4093:
4089:
4085:
4081:
4077:
4073:
4069:
4061:
4057:
4053:
4049:
4045:
4041:
4037:
4033:
4029:
4025:
4021:
4018:
4017:
4016:
4014:
4010:
4006:
4000:
3990:
3988:
3983:
3981:
3977:
3973:
3969:
3965:
3877:
3876:Berry paradox
3872:
3849:
3812:
3808:
3804:
3800:
3796:
3792:
3788:
3784:
3765:
3761:
3757:
3750:
3746:
3742:
3730:
3726:
3722:
3720:
3714:
3713:) as output.
3712:
3708:
3704:
3700:
3696:
3692:
3688:
3686:
3682:
3678:
3676:
3672:
3668:
3664:
3660:
3656:
3650:
3644:
3642:
3637:
3635:
3631:
3626:
3624:
3616:
3612:
3608:
3604:
3600:
3596:
3592:
3588:
3584:
3580:
3578:
3574:
3570:
3563:
3552:
3535:
3529:
3521:
3517:
3500:
3494:
3491:
3485:
3479:
3476:
3467:
3461:
3455:
3435:
3427:
3423:
3406:
3400:
3397:
3388:
3382:
3379:
3376:
3368:
3362:
3359:
3353:
3350:
3347:
3341:
3333:
3329:
3312:
3309:
3306:
3300:
3297:
3291:
3285:
3282:
3273:
3267:
3264:
3261:
3253:
3247:
3244:
3238:
3235:
3232:
3226:
3219:
3215:
3201:
3198:
3175:
3169:
3146:
3138:
3132:
3109:
3103:
3080:
3072:
3066:
3043:
3040:
3034:
3008:
3005:
3002:
2996:
2993:
2987:
2984:
2978:
2971:
2970:
2952:
2946:
2943:
2937:
2931:
2928:
2919:
2913:
2910:
2904:
2896:
2890:
2887:
2881:
2875:
2872:
2866:
2858:
2852:
2843:
2837:
2834:
2831:
2825:
2822:
2816:
2810:
2807:
2801:
2793:
2787:
2780:
2779:
2778:
2777:
2773:
2770:
2766:
2747:
2739:
2728:
2715:
2709:
2684:
2676:
2671:
2667:
2663:
2660:
2652:
2644:
2638:
2632:
2625:. Similarly,
2607:
2599:
2593:
2587:
2567:
2564:
2556:
2548:
2542:
2536:
2533:
2530:
2507:
2499:
2495:
2478:
2472:
2452:
2449:
2443:
2437:
2434:
2429:
2425:
2421:
2418:
2395:
2389:
2317:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2285:
2279:
2270:
2266:
2250:
2244:
2241:
2236:
2232:
2228:
2225:
2219:
2213:
2210:
2204:
2198:
2191:
2187:
2170:
2164:
2150:
2133:
2130:
2127:
2098:
2095:
2092:
2083:
2060:
2057:
2054:
2048:
2037:Basic results
2034:
2032:
2027:
2025:
2021:
2016:
2014:
2010:
2004:
2000:
1998:
1994:
1990:
1986:
1981:
1979:
1975:
1971:
1966:
1964:
1960:
1951:
1945:
1938:
1934:
1930:
1927:
1919:
1918:
1917:
1915:
1911:
1907:
1899:
1892:
1888:
1880:
1876:
1868:
1867:
1866:
1861:
1857:
1850:
1847:
1843:
1839:
1834:
1830:
1823:
1815:
1811:
1804:
1800:
1793:
1790:
1789:
1788:
1787:
1783:
1779:
1772:
1768:
1761:
1757:
1750:
1746:
1742:
1738:
1737:
1736:
1731:
1724:
1720:
1713:
1706:
1702:
1695:
1688:
1684:
1675:
1673:
1669:
1665:
1657:
1653:
1649:
1645:
1644:
1643:
1641:
1637:
1633:
1629:
1625:
1621:
1617:
1613:
1611:
1607:
1603:
1599:
1592:
1589:
1588:
1587:
1584:
1570:
1554:
1551:
1545:
1539:
1536:
1533:
1530:
1527:
1524:
1516:
1502:
1496:
1490:
1470:
1450:
1441:
1421:
1417:
1396:
1388:
1385:
1382:
1379:
1378:
1377:
1375:
1370:
1367:
1362:
1360:
1343:
1340:
1337:
1315:
1311:
1299:
1293:
1274:
1266:
1261:
1257:
1236:
1226:
1209:
1203:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1147:
1138:
1124:
1121:
1115:
1109:
1106:
1100:
1094:
1091:
1085:
1082:
1076:
1056:
1053:
1050:
1043:there exists
1030:
1027:
1024:
998:
995:
992:
989:
986:
983:
980:
968:
948:
928:
905:
899:
896:
890:
884:
881:
875:
872:
866:
857:
843:
820:
814:
811:
805:
800:
796:
789:
786:
781:
777:
773:
770:
745:
741:
718:
714:
705:
701:
697:
694:
672:
668:
659:
655:
651:
648:
639:
625:
622:
611:
605:
602:
596:
590:
582:
579:
573:
570:
544:
538:
535:
529:
523:
520:
514:
508:
485:
479:
476:
470:
464:
455:
438:
432:
409:
403:
395:
391:
384:
378:
376:
368:
364:
360:
356:
353:
352:
351:
349:
345:
341:
337:
333:
329:
325:
321:
317:
313:
309:
302:
298:
294:
289:
285:
281:
279:
275:
270:
268:
264:
260:
256:
252:
248:
244:
240:
236:
232:
227:
225:
221:
217:
213:
209:
205:
201:
197:
193:
187:
185:
180:
176:
171:
169:
165:
155:
149:
148:
147:
145:
130:
128:
124:
120:
116:
112:
108:
104:
100:
95:
93:
89:
85:
81:
77:
73:
69:
68:computational
65:
61:
57:
53:
49:
45:
37:
33:
29:
26:
21:
11923:Hutter Prize
11887:Quantization
11876:
11792:Compensation
11586:Quantization
11309:Compensation
10875:Shannon–Fano
10815:Entropy type
10747:
10624:
10545:Ultraproduct
10392:Model theory
10357:Independence
10293:Formal proof
10285:Proof theory
10268:
10241:
10198:real numbers
10170:second-order
10081:Substitution
9958:Metalanguage
9899:conservative
9872:Axiom schema
9816:Constructive
9786:Morse–Kelley
9752:Set theories
9731:Aleph number
9724:inaccessible
9630:Grothendieck
9514:intersection
9401:Higher-order
9389:Second-order
9335:Truth tables
9292:Venn diagram
9075:Formal proof
8990:
8870:
8845:
8822:
8804:. Springer.
8801:
8783:Algoritmusok
8782:
8763:
8754:
8750:
8731:
8727:
8676:
8672:
8662:
8637:
8629:
8604:
8596:
8571:
8563:
8499:
8492:
8475:
8469:
8450:
8420:
8378:
8374:
8361:
8342:
8338:
8328:
8320:
8315:
8288:
8284:
8278:
8262:. Springer.
8258:
8251:
8225:
8221:
8208:
8175:
8171:
8158:
8147:the original
8132:
8113:
8107:
8098:
8094:
8084:
8051:
8043:
8018:
8014:
8008:
7973:
7969:
7963:
7955:the original
7950:
7946:
7936:
7910:
7906:
7893:
7867:
7863:
7850:
7831:Report V-131
7830:
7814:
7769:
7766:Scholarpedia
7765:
7740:
7731:
7668:
7664:
7654:
7627:
7623:
7610:
7577:
7573:
7564:
7528:
7524:
7517:
7510:
7503:
7499:
7494:
7487:
7483:
7477:
7469:
7461:
7456:
7452:
7430:
7421:
7417:
7408:
7396:
7383:
7371:
7366:
7358:
7350:
7346:
7342:
7338:
7334:
7330:
7329:However, an
7325:
7253:
7249:
7201:
7196:
7192:
7153:
7140:
7136:adding to it
7131:
7035:
7034:
6930:
6788:
6453:for all big
6175:
6152:
5970:
5893:
5655:
5487:, such that
5466:
5463:
5460:
5224:
5223:
5207:
5134:
5124:
5120:
5116:
5112:
5096:
5094:
5073:
5072:
5053:C.S. Wallace
5050:
5032:
5024:
5022:
5016:
5008:
4999:
4995:
4982:
4970:
4962:
4940:
4929:
4925:
4914:
4903:
4891:
4884:
4880:
4876:
4872:
4868:
4866:
4861:
4854:
4847:
4840:
4833:
4825:
4818:
4811:
4804:
4797:
4789:
4782:
4774:
4767:
4765:
4757:
4752:
4747:
4743:
4739:
4735:
4731:
4727:
4723:
4721:
4716:
4712:
4709:
4705:
4701:
4697:
4693:
4690:
4686:
4682:
4677:
4674:
4670:
4664:
4661:
4657:
4651:
4647:
4643:
4639:
4635:
4631:
4629:
4624:
4621:
4617:
4611:
4607:
4603:
4599:
4595:
4591:
4587:
4583:
4579:
4577:
4572:
4569:
4565:
4559:
4557:
4552:
4551:
4546:
4542:
4538:
4534:
4530:
4526:
4522:
4518:
4514:
4510:
4506:
4502:
4498:
4494:
4490:
4486:
4482:
4478:
4474:
4470:
4466:
4462:
4458:
4454:
4450:
4442:
4441:
4436:
4434:
4428:
4424:
4420:
4416:
4409:
4405:
4401:
4397:
4396:
4387:
4383:
4378:
4374:
4372:
4367:
4362:
4358:
4354:
4346:
4337:
4331:
4324:linear scale
4319:
4294:
4290:
4273:
4269:
4267:
4259:
4249:
4245:
4243:
4238:
4234:
4230:
4229:
4224:
4213:
4209:
4205:
4201:
4197:
4193:
4191:
4187:
4183:
4179:
4167:
4163:
4159:
4155:
4151:
4147:
4143:
4139:
4135:
4131:
4127:
4125:
4115:
4107:
4103:
4101:
4087:
4083:
4079:
4071:
4067:
4065:
4059:
4055:
4051:
4047:
4043:
4039:
4035:
4031:
4027:
4023:
4019:
4012:
4008:
4004:
4002:
3984:
3975:
3971:
3967:
3963:
3873:
3847:
3815:
3810:
3806:
3802:
3798:
3794:
3790:
3786:
3763:
3759:
3758:and returns
3755:
3753:
3748:
3744:
3718:
3715:
3710:
3706:
3702:
3694:
3690:
3689:
3684:
3680:
3679:
3674:
3670:
3666:
3662:
3658:
3654:
3653:
3648:
3640:
3638:
3629:
3627:
3622:
3619:
3614:
3610:
3606:
3602:
3598:
3594:
3590:
3586:
3582:
3576:
3572:
3568:
3566:
3561:
3519:
3518:
3425:
3424:
3331:
3330:
3217:
3216:
3026:
2775:
2774:
2768:
2767:
2497:
2496:
2268:
2267:
2189:
2188:
2156:
2153:Inequalities
2040:
2028:
2024:Leonid Levin
2017:
2005:
2001:
1996:
1988:
1982:
1977:
1967:
1957:
1949:
1943:
1936:
1932:
1925:
1913:
1909:
1905:
1897:
1890:
1886:
1884:
1878:
1874:
1859:
1855:
1853:
1848:
1845:
1841:
1832:
1821:
1819:
1813:
1809:
1802:
1798:
1791:
1785:
1781:
1777:
1776:
1770:
1766:
1759:
1755:
1748:
1744:
1740:
1729:
1722:
1718:
1711:
1704:
1693:
1686:
1682:
1681:
1667:
1663:
1661:
1655:
1651:
1647:
1639:
1635:
1631:
1627:
1623:
1619:
1615:
1614:
1609:
1605:
1601:
1600:
1596:
1585:
1581:
1442:
1439:
1373:
1371:
1365:
1363:
1358:
1302:
1297:
1227:
1139:
858:
760:, such that
640:
456:
393:
389:
387:
382:
374:
372:
366:
362:
358:
354:
347:
343:
339:
335:
331:
327:
323:
319:
315:
311:
307:
305:
300:
296:
292:
287:
283:
273:
271:
266:
262:
258:
254:
250:
246:
242:
238:
234:
228:
219:
215:
211:
207:
203:
188:
183:
172:
167:
163:
161:
141:
122:
117:computing a
114:
96:
87:
83:
79:
75:
71:
55:
41:
11882:Prefix code
11735:Frame types
11556:Color space
11382:Convolution
11112:LZ77 + ANS
11023:Incremental
10996:Other types
10915:Levenshtein
10655:Type theory
10603:undecidable
10535:Truth value
10422:equivalence
10101:non-logical
9714:Enumeration
9704:Isomorphism
9651:cardinality
9635:Von Neumann
9600:Ultrafilter
9565:Uncountable
9499:equivalence
9416:Quantifiers
9406:Fixed-point
9375:First-order
9255:Consistency
9240:Proposition
9217:Traditional
9188:Lindström's
9178:Compactness
9120:Type theory
9065:Cardinality
8785:. TypoTeX.
8476:Bull. EATCS
8101:(3): 19–23.
7870:(1): 1–22.
7772:(3): 2519.
7416:has length
5703:, and uses
5579:Busy Beaver
5109:martingales
5080:) as being
4221:probability
4114:the string
4098:Compression
3729:interpreter
2366:the program
2031:Blum axioms
1829:interpreter
560:, that is,
394:prefix-free
278:pseudo-code
272:Any string
233:, where an
119:lower bound
52:mathematics
11987:Categories
11939:Mark Adler
11897:Redundancy
11814:Daubechies
11797:Estimation
11730:Frame rate
11652:Daubechies
11612:Chain code
11571:Macroblock
11377:Companding
11314:Estimation
11234:Daubechies
10940:Lempel–Ziv
10900:Exp-Golomb
10828:Arithmetic
10466:elementary
10159:arithmetic
10027:Quantifier
10005:functional
9877:Expression
9595:Transitive
9539:identities
9524:complement
9457:hereditary
9440:Set theory
8975:David Dowe
8757:: 127–151.
8734:(3): 257.
8679:: 93–100.
7833:(Report).
7797:1885/15015
7678:2002.07674
7671:(4): 408.
7557:References
7374:bits; cf.
6499:, we have
5067:See also:
4917:such that
4443:Proof Idea
3575:) for any
3448:, we have
2520:such that
1069:such that
342:, written
303:"ab" × 16
175:complexity
133:Definition
11916:Community
11740:Interlace
11126:Zstandard
10905:Fibonacci
10895:Universal
10853:Canonical
10737:Supertask
10640:Recursion
10598:decidable
10432:saturated
10410:of models
10333:deductive
10328:axiomatic
10248:Hilbert's
10235:Euclidean
10216:canonical
10139:axiomatic
10071:Signature
10000:Predicate
9889:Extension
9811:Ackermann
9736:Operation
9615:Universal
9605:Recursive
9580:Singleton
9575:Inhabited
9560:Countable
9550:Types of
9534:power set
9504:partition
9421:Predicate
9367:Predicate
9282:Syllogism
9272:Soundness
9245:Inference
9235:Tautology
9137:paradoxes
8962:M. Hutter
8897:2190-619X
8686:1206.0983
8553:ignored (
8543:cite book
8535:1868-0941
8388:0801.0209
8381:: 23–41.
8293:CiteSeerX
8200:250850390
7978:CiteSeerX
7806:1941-6016
7705:1099-4300
7586:0581-572X
7542:with sum
7271:Code golf
7143:July 2014
7049:
6980:⋯
6882:−
6853:∑
6743:≤
6609:≤
6519:≤
6481:≤
6435:≤
6414:
6392:≤
6304:
6206:
6184:≤
6094:≤
5921:≥
5735:≤
5507:≥
5373:
5340:∑
5311:≤
5260:satisfies
4788:), where
4742:for some
4722:Given an
4568:NthProof(
4525:to prove
4264:2 − 2 + 1
4126:A string
3896:positive
3890:smallest
3801:string s
3697:is not a
3601:string p
3477:≤
3360:≥
2994:≤
2929:≤
2844:≤
2823:≤
2808:≤
2740:≤
2677:
2645:≤
2600:≤
2549:≤
2528:∀
2435:
2419:≤
2313:−
2307:−
2301:−
2295:−
2289:↦
2283:↦
2242:
2211:≤
2041:We write
1991:in 1965.
1885:Thus, if
1873:on input
1531:∈
1422:∗
1369:anymore.
1364:Define a
1316:∗
1267:
1175:
1163:
1092:≥
996:
984:
782:∗
774:∈
768:∀
719:∗
711:→
706:∗
673:∗
665:→
660:∗
623:≤
603:−
577:∀
568:∃
245:>. If
179:universal
138:Intuition
11902:Symmetry
11870:Timeline
11853:FM-index
11698:Bit rate
11691:Concepts
11539:Concepts
11402:Sampling
11355:Bit rate
11348:Concepts
11050:Sequitur
10885:Tunstall
10858:Modified
10848:Adaptive
10806:Lossless
10722:Logicism
10715:timeline
10691:Concrete
10550:Validity
10520:T-schema
10513:Kripke's
10508:Tarski's
10503:semantic
10493:Strength
10442:submodel
10437:spectrum
10405:function
10253:Tarski's
10242:Elements
10229:geometry
10185:Robinson
10106:variable
10091:function
10064:spectrum
10054:Sentence
10010:variable
9953:Language
9906:Relation
9867:Automata
9857:Alphabet
9841:language
9695:-jection
9673:codomain
9659:Function
9620:Universe
9590:Infinite
9494:Relation
9277:Validity
9267:Argument
9165:theorem,
8722:(1967).
8720:Blum, M.
8703:12085503
8484:39718973
8409:Archived
8035:11402549
8000:12584692
7925:Archived
7882:Archived
7839:Archived
7835:Revision
7723:33286182
7618:(1998).
7594:25049284
7523:+ ... +
7424:used in
7260:See also
7036:Theorem.
6236:, where
5554:, where
5225:Theorem.
5097:infinite
5057:Bayesian
4687:function
4671:function
4658:function
4618:function
4566:function
4349:for the
4308:prog2(s)
4302:prog1(s)
4112:compress
3970:, since
3956:English
3926:defined
3902:integer
3850:is only
3799:for each
3787:function
3745:function
3599:for each
3583:function
2272:follows:
2190:Theorem.
2117:, where
2026:(1974).
1869:Running
1842:function
1648:D′
1640:D′
882:≮
297:function
284:function
235:encoding
11860:Entropy
11809:Wavelet
11788:Motion
11647:Wavelet
11627:Fractal
11622:Deflate
11605:Methods
11392:Latency
11305:Motion
11229:Wavelet
11146:LHA/LZH
11096:Deflate
11045:Re-Pair
11040:Grammar
10870:Shannon
10843:Huffman
10799:methods
10664:Related
10461:Diagram
10359: (
10338:Hilbert
10323:Systems
10318:Theorem
10196:of the
10141:systems
9921:Formula
9916:Grammar
9832: (
9776:General
9489:Forcing
9474:Element
9394:Monadic
9169:paradox
9110:Theorem
9046:General
8850:. PWS.
8505:Bibcode
8405:5555443
8242:2142553
8180:Bibcode
7774:Bibcode
7714:7516884
7683:Bibcode
7665:Entropy
7646:1643414
7602:0178484
7455:) <
7447:+ 7·log
5577:is the
5449:is the
5219:entropy
5214:entropy
4879:" with
4398:Theorem
4317:strings
4231:Theorem
4218:uniform
4076:no more
3950:twenty
3914:cannot
3691:Theorem
3655:Theorem
3589:s)
2498:Theorem
2009:Ming Li
1900:, then
1683:Theorem
210:, then
144:strings
54:), the
28:fractal
11971:codecs
11932:People
11835:Theory
11802:Vector
11319:Vector
11136:Brotli
11086:Hybrid
10985:Snappy
10838:Golomb
10427:finite
10190:Skolem
10143:
10118:Theory
10086:Symbol
10076:String
10059:atomic
9936:ground
9931:closed
9926:atomic
9882:ground
9845:syntax
9741:binary
9668:domain
9585:Finite
9350:finite
9208:Logics
9167:
9115:Theory
8997:
8985:pages.
8968:
8956:
8895:
8885:
8854:
8831:
8808:
8789:
8770:
8701:
8650:
8617:
8613:–106.
8584:
8533:
8523:
8482:
8457:
8403:
8295:
8266:
8240:
8198:
8120:
8072:
8033:
7998:
7980:
7804:
7721:
7711:
7703:
7644:
7600:
7592:
7584:
7195:given
6931:Note.
6343:, and
5422:where
5082:random
5019:Q.E.D.
5007:since
4713:return
4696:)
4602:where
4216:. The
4086:given
3938:fewer
3816:Using
3811:return
3793:i = 1
3783:bits:
3749:string
3725:Pascal
3687:bits.
3681:Proof:
3615:return
3593:i = 1
3587:string
3520:Proof.
3332:Proof.
2769:Proof.
2702:, and
2269:Proof.
2076:to be
1997:J. ACM
1854:where
1846:string
1616:Proof:
301:return
288:return
202:. If
196:Pascal
109:, and
11762:parts
11760:Codec
11725:Frame
11683:Video
11667:SPIHT
11576:Pixel
11531:Image
11485:ACELP
11456:ADPCM
11446:μ-law
11441:A-law
11434:parts
11432:Codec
11340:Audio
11279:ACELP
11267:ADPCM
11244:SPIHT
11185:Lossy
11169:bzip2
11160:LZHAM
11116:LZFSE
11018:Delta
10910:Gamma
10890:Unary
10865:Range
10417:Model
10165:Peano
10022:Proof
9862:Arity
9791:Naive
9678:image
9610:Fuzzy
9570:Empty
9519:union
9464:Class
9105:Model
9095:Lemma
9053:Axiom
8699:S2CID
8681:arXiv
8480:S2CID
8427:arXiv
8412:(PDF)
8401:S2CID
8383:arXiv
8371:(PDF)
8238:S2CID
8218:(PDF)
8196:S2CID
8168:(PDF)
8150:(PDF)
8143:(PDF)
8060:–99.
8031:S2CID
7996:S2CID
7928:(PDF)
7903:(PDF)
7885:(PDF)
7860:(PDF)
7842:(PDF)
7827:(PDF)
7673:arXiv
7590:JSTOR
7361:bits.
7355:ASCII
7333:with
7317:Notes
6829:to be
4898:: If
4824:>
4553:Proof
4423:) ≥
4150:) ≤ |
3944:than
3908:that
3719:proof
3665:with
1778:Proof
1685:: If
1672:up to
1654:| + |
1650:| = |
1359:knows
390:plain
361:) = |
261:>
224:ASCII
198:, or
153:, and
86:, or
11774:DPCM
11581:PSNR
11512:MDCT
11505:WLPC
11490:CELP
11451:DPCM
11299:WLPC
11284:CELP
11262:DPCM
11212:MDCT
11156:LZMA
11057:LDCT
11035:DPCM
10980:LZWL
10970:LZSS
10965:LZRW
10955:LZJB
10540:Type
10343:list
10147:list
10124:list
10113:Term
10047:rank
9941:open
9835:list
9647:Maps
9552:sets
9411:Free
9381:list
9131:list
9058:list
8995:ISBN
8981:and
8966:ISBN
8954:ISBN
8893:ISSN
8883:ISBN
8852:ISBN
8829:ISBN
8806:ISBN
8787:ISBN
8768:ISBN
8648:ISBN
8615:ISBN
8582:ISBN
8555:help
8531:ISSN
8521:ISBN
8455:ISBN
8264:ISBN
8118:ISBN
8070:ISBN
7802:ISSN
7719:PMID
7701:ISSN
7582:ISSN
7445:1218
7341:) =
6696:<
6641:<
6574:<
5971:Let
5078:bits
4965:+log
4959:>
4828:+log
4777:+log
4606:and
4537:for
4533:) ≥
4501:) ≥
4477:) ≥
4328:bits
4154:| −
4138:| −
4070:and
4062:))).
4038:) +
4030:) =
4011:and
3978:are
3974:and
3884:The
3781:1288
3673:) ≥
3059:and
2286:1001
1831:for
1812:) +
1801:) ≤
1769:) ≤
1758:) −
1743:. −
1728:and
1710:and
1692:and
1389:Let
1028:>
641:Let
392:and
200:Java
192:Lisp
184:abab
50:and
11819:DWT
11769:DCT
11713:VBR
11708:CBR
11703:ABR
11662:EZW
11657:DWT
11642:RLE
11632:KLT
11617:DCT
11500:LSP
11495:LAR
11480:LPC
11473:FFT
11370:VBR
11365:CBR
11360:ABR
11294:LSP
11289:LAR
11274:LPC
11239:DWT
11224:FFT
11219:DST
11207:DCT
11106:LZS
11101:LZX
11077:RLE
11072:PPM
11067:PAQ
11062:MTF
11030:DMC
11008:CTW
11003:BWT
10975:LZW
10960:LZO
10950:LZ4
10945:842
10227:of
10209:of
10157:of
9689:Sur
9663:Map
9470:Ur-
9452:Set
8977:'s
8964::
8960:by
8928:by
8875:doi
8736:doi
8691:doi
8677:501
8644:119
8611:105
8513:doi
8393:doi
8379:208
8347:doi
8303:doi
8230:doi
8188:doi
8062:doi
8023:doi
7988:doi
7915:doi
7872:doi
7792:hdl
7782:doi
7709:PMC
7691:doi
7632:doi
7628:207
7508:is
7506:− 1
7491:= 2
7440:000
7437:400
7412:If
7389:for
7138:.
7046:log
6977:000
6928:.
6543:by
6405:log
6295:log
6197:log
6173:.
5370:log
4706:and
4698:for
4691:int
4675:int
4662:int
4622:int
4570:int
4373:If
4366:in
4074:is
3932:in
3920:be
3878:: "
3860:288
3857:401
3854:001
3843:000
3840:000
3837:000
3830:000
3827:000
3824:000
3791:for
3776:000
3773:000
3770:000
3751:s)
3738:000
3735:400
3693::
3611:and
3591:for
3162:or
3125:or
3096:or
2847:max
2668:log
2426:log
2233:log
1965:).
1622:in
1506:min
1258:log
1154:min
975:min
941:or
377:).
369:)|.
338:of
322:of
226:).
42:In
36:PNG
11989::
11637:LP
11468:FT
11461:DM
11013:CM
10613:NP
10237::
10231::
10161::
9838:),
9693:Bi
9685:In
8891:.
8881:.
8873:.
8869:.
8753:.
8732:11
8730:.
8726:.
8697:.
8689:.
8675:.
8671:.
8646:.
8580:.
8578:53
8547::
8545:}}
8541:{{
8529:.
8519:.
8511:.
8478:.
8441:^
8407:.
8399:.
8391:.
8377:.
8373:.
8341:.
8337:.
8301:.
8289:42
8287:.
8236:.
8226:21
8224:.
8220:.
8194:.
8186:.
8176:25
8174:.
8170:.
8099:25
8097:.
8093:.
8068:.
8029:.
8019:14
8017:.
7994:.
7986:.
7974:16
7972:.
7949:.
7945:.
7923:.
7909:.
7905:.
7880:.
7866:.
7862:.
7829:.
7800:.
7790:.
7780:.
7768:.
7764:.
7749:^
7717:.
7707:.
7699:.
7689:.
7681:.
7669:22
7667:.
7663:.
7642:MR
7640:.
7626:.
7622:.
7598:MR
7596:.
7588:.
7578:25
7576:.
7546:=
7534:=
7531:−1
7516:+
7472:).
7466:10
7449:10
7443:+
7433:+
6283:,
5968:.
5723:.
5205:.
5037:.
4932:)
4875:)≥
4864:.
4763:)
4719:)
4702:if
4680:)
4667:)
4627:)
4575:)
4555::
4439:.
4394:.
4305:,
4248:−
4227:.
4094:.
4015::
3982:.
3959:14
3953:13
3947:12
3941:11
3935:10
3813:s
3807:if
3803:of
3795:to
3677:.
3636:.
3617:i
3607:if
3603:of
3595:to
3516:.
3328:.
2765:.
2494:.
2318:01
2310:11
2304:00
2298:00
2292:11
1980:.
1946:).
1851:)
1838::
1747:≤
1503::=
1376:.
1225:.
1172:ln
1160:ln
1137:.
993:ln
981:ln
638:.
280::
194:,
168:38
164:17
105:,
82:,
78:,
74:,
34:.
11973:)
11969:(
10789:e
10782:t
10775:v
10693:/
10608:P
10363:)
10149:)
10145:(
10042:∀
10037:!
10032:∃
9993:=
9988:↔
9983:→
9978:∧
9973:∨
9968:¬
9691:/
9687:/
9661:/
9472:)
9468:(
9355:∞
9345:3
9133:)
9031:e
9024:t
9017:v
9003:.
8947:.
8938:.
8899:.
8877::
8860:.
8837:.
8814:.
8795:.
8776:.
8755:2
8744:.
8738::
8705:.
8693::
8683::
8656:.
8623:.
8590:.
8557:)
8537:.
8515::
8507::
8486:.
8463:.
8435:.
8429::
8395::
8385::
8355:.
8349::
8343:9
8321:n
8309:.
8305::
8272:.
8244:.
8232::
8202:.
8190::
8182::
8126:.
8078:.
8064::
8058:1
8037:.
8025::
8002:.
7990::
7951:1
7917::
7911:7
7874::
7868:7
7808:.
7794::
7784::
7776::
7770:2
7725:.
7693::
7685::
7675::
7648:.
7634::
7604:.
7529:n
7525:N
7521:1
7518:N
7514:0
7511:N
7504:n
7500:L
7495:L
7488:L
7484:N
7470:m
7468:(
7462:m
7457:m
7453:m
7451:(
7435:1
7431:n
7422:m
7418:n
7372:n
7359:n
7351:n
7347:n
7343:n
7339:s
7337:(
7335:K
7331:s
7254:x
7250:x
7236:)
7233:)
7230:x
7227:(
7224:L
7220:|
7216:x
7213:(
7210:K
7197:y
7193:x
7179:)
7176:y
7172:|
7168:x
7165:(
7162:K
7145:)
7141:(
7100:)
7097:1
7094:(
7091:O
7088:+
7085:)
7082:x
7079:(
7076:K
7073:=
7067:)
7064:x
7061:(
7058:P
7054:1
7020:x
7000:p
6974:p
6954:x
6951:=
6948:)
6945:p
6942:(
6939:U
6916:x
6894:)
6891:p
6888:(
6885:l
6878:2
6872:x
6869:=
6866:)
6863:p
6860:(
6857:U
6849:=
6846:)
6843:x
6840:(
6837:P
6817:x
6797:U
6769:x
6749:n
6746:2
6740:)
6737:x
6734:(
6731:K
6711:)
6708:n
6705:(
6702:B
6699:B
6676:x
6656:)
6653:n
6650:(
6647:B
6644:B
6621:1
6618:+
6615:n
6612:2
6589:)
6586:n
6583:(
6580:B
6577:B
6571:)
6568:n
6565:(
6560:K
6556:p
6531:1
6528:+
6525:n
6522:2
6516:)
6513:x
6510:(
6507:l
6487:n
6484:2
6461:n
6441:n
6438:2
6432:)
6429:1
6426:(
6423:O
6420:+
6417:n
6409:2
6401:2
6398:+
6395:n
6389:)
6386:x
6383:(
6380:K
6360:)
6357:1
6354:(
6351:O
6331:n
6307:n
6299:2
6291:2
6269:n
6265:p
6244:n
6224:)
6221:1
6218:(
6215:O
6212:+
6209:n
6201:2
6193:2
6190:+
6187:n
6161:x
6132:)
6129:n
6126:(
6123:B
6120:B
6100:n
6097:2
6081:.
6069:)
6066:n
6063:(
6060:B
6057:B
6035:n
6031:p
6006:n
5984:n
5980:p
5956:n
5936:)
5933:n
5930:(
5927:B
5924:B
5918:)
5915:n
5912:(
5907:K
5903:p
5890:.
5876:x
5872:n
5860:.
5846:x
5842:n
5821:x
5801:)
5798:x
5795:(
5792:K
5772:x
5759:.
5747:1
5744:+
5741:n
5738:2
5711:K
5691:n
5669:K
5665:p
5641:B
5638:B
5618:n
5598:)
5595:n
5592:(
5589:S
5565:B
5562:B
5542:n
5522:)
5519:n
5516:(
5513:B
5510:B
5504:)
5501:n
5498:(
5495:p
5475:p
5435:b
5431:H
5410:)
5407:n
5403:/
5399:1
5396:(
5393:O
5390:+
5384:n
5381:2
5376:n
5364:+
5360:)
5354:i
5350:x
5344:i
5334:n
5331:1
5325:(
5319:b
5315:H
5308:)
5305:n
5301:|
5295:n
5292::
5289:1
5285:x
5281:(
5278:K
5273:n
5270:1
5246:n
5243::
5240:1
5236:x
5193:x
5173:)
5170:T
5167:(
5164:h
5161:=
5158:)
5155:T
5152:;
5149:x
5146:(
5143:K
5125:c
5123:−
5121:n
5117:n
5113:c
5028:0
5025:n
5009:s
5002:)
5000:s
4998:(
4996:K
4992:≥
4986:0
4983:n
4976:)
4974:0
4971:n
4969:(
4967:2
4963:U
4944:0
4941:n
4937:≥
4930:s
4928:(
4926:K
4915:s
4907:0
4904:n
4892:S
4888:0
4885:n
4883:≥
4881:L
4877:L
4873:s
4871:(
4869:K
4862:U
4858:0
4855:n
4851:0
4848:n
4844:0
4841:n
4837:0
4834:n
4832:(
4830:2
4826:U
4822:0
4819:n
4815:0
4812:n
4808:0
4805:n
4801:0
4798:n
4796:(
4794:2
4790:U
4786:0
4783:n
4781:(
4779:2
4775:U
4771:0
4768:n
4761:0
4758:n
4748:n
4744:L
4740:L
4736:s
4734:(
4732:K
4728:S
4724:n
4717:i
4710:n
4694:n
4678:n
4665:n
4652:L
4648:s
4644:L
4640:s
4638:(
4636:K
4632:n
4625:n
4612:S
4608:n
4604:s
4600:n
4596:s
4594:(
4592:K
4588:n
4584:S
4580:n
4573:n
4560:S
4547:P
4543:L
4539:L
4535:L
4531:x
4529:(
4527:K
4523:S
4519:P
4515:x
4511:L
4507:L
4503:L
4499:x
4497:(
4495:K
4491:x
4487:P
4483:L
4479:L
4475:x
4473:(
4471:K
4467:S
4463:x
4459:L
4455:P
4451:S
4437:S
4431:)
4429:S
4425:L
4421:s
4419:(
4417:K
4410:s
4406:S
4402:L
4388:A
4384:S
4379:A
4375:F
4368:S
4363:A
4359:F
4355:A
4347:S
4334:.
4332:s
4320:s
4297:)
4295:s
4293:(
4291:K
4274:c
4270:n
4250:c
4246:n
4239:c
4235:n
4225:n
4214:n
4210:n
4206:s
4202:s
4198:s
4196:(
4194:K
4184:n
4180:n
4164:c
4160:s
4156:c
4152:s
4148:s
4146:(
4144:K
4140:c
4136:s
4132:c
4128:s
4116:s
4108:s
4106:(
4104:K
4088:X
4084:Y
4080:X
4072:Y
4068:X
4060:Y
4058:,
4056:X
4054:(
4052:K
4048:X
4046:|
4044:Y
4042:(
4040:K
4036:X
4034:(
4032:K
4028:Y
4026:,
4024:X
4022:(
4020:K
4013:Y
4009:X
4005:c
3976:H
3972:K
3968:H
3964:K
3929:9
3923:8
3917:7
3911:6
3905:5
3899:4
3893:3
3887:2
3881:1
3852:7
3848:s
3835:8
3822:8
3768:7
3764:s
3762:(
3760:K
3756:s
3733:1
3711:s
3709:(
3707:K
3703:s
3695:K
3685:n
3675:n
3671:s
3669:(
3667:K
3663:s
3659:n
3649:K
3641:K
3630:p
3623:s
3577:s
3573:s
3571:(
3569:K
3562:K
3539:)
3536:x
3533:(
3530:f
3504:)
3501:f
3498:(
3495:K
3492:+
3489:)
3486:x
3483:(
3480:K
3474:)
3471:)
3468:x
3465:(
3462:f
3459:(
3456:K
3436:f
3410:)
3407:y
3404:(
3401:K
3398:+
3395:)
3392:)
3389:y
3386:(
3383:K
3380:,
3377:y
3373:|
3369:x
3366:(
3363:K
3357:)
3354:y
3351:,
3348:x
3345:(
3342:K
3316:)
3313:x
3310:,
3307:y
3304:(
3301:K
3298:=
3295:)
3292:y
3289:(
3286:K
3283:+
3280:)
3277:)
3274:y
3271:(
3268:K
3265:,
3262:y
3258:|
3254:x
3251:(
3248:K
3245:=
3242:)
3239:y
3236:,
3233:x
3230:(
3227:K
3202:y
3199:x
3179:)
3176:y
3173:(
3170:K
3150:)
3147:x
3143:|
3139:y
3136:(
3133:K
3113:)
3110:x
3107:(
3104:K
3084:)
3081:y
3077:|
3073:x
3070:(
3067:K
3047:)
3044:y
3041:x
3038:(
3035:K
3012:)
3009:y
3006:,
3003:x
3000:(
2997:K
2991:)
2988:y
2985:x
2982:(
2979:K
2956:)
2953:y
2950:(
2947:K
2944:+
2941:)
2938:x
2935:(
2932:K
2926:)
2923:)
2920:x
2917:(
2914:K
2911:+
2908:)
2905:x
2901:|
2897:y
2894:(
2891:K
2888:,
2885:)
2882:y
2879:(
2876:K
2873:+
2870:)
2867:y
2863:|
2859:x
2856:(
2853:K
2850:(
2841:)
2838:y
2835:,
2832:x
2829:(
2826:K
2820:)
2817:x
2814:(
2811:K
2805:)
2802:y
2798:|
2794:x
2791:(
2788:K
2752:|
2748:x
2744:|
2737:)
2733:|
2729:x
2725:|
2720:|
2716:x
2713:(
2710:K
2689:|
2685:x
2681:|
2672:2
2664:2
2661:+
2657:|
2653:x
2649:|
2642:)
2639:x
2636:(
2633:K
2612:|
2608:x
2604:|
2597:)
2594:x
2591:(
2588:C
2568:c
2565:+
2561:|
2557:x
2553:|
2546:)
2543:x
2540:(
2537:C
2534:,
2531:x
2508:c
2482:)
2479:x
2476:(
2473:C
2453:3
2450:+
2447:)
2444:x
2441:(
2438:C
2430:2
2422:2
2399:)
2396:1
2393:(
2390:O
2370:]
2362:[
2359:]
2351:[
2348:]
2340:[
2280:9
2254:)
2251:x
2248:(
2245:C
2237:2
2229:2
2226:+
2223:)
2220:x
2217:(
2214:K
2208:)
2205:x
2202:(
2199:C
2174:)
2171:1
2168:(
2165:O
2137:)
2134:y
2131:,
2128:x
2125:(
2105:)
2102:)
2099:y
2096:,
2093:x
2090:(
2087:(
2084:K
2064:)
2061:y
2058:,
2055:x
2052:(
2049:K
1944:s
1942:(
1940:2
1937:K
1933:P
1928:.
1926:c
1914:s
1910:s
1906:P
1904:(
1898:s
1894:2
1891:L
1887:P
1881:.
1879:p
1875:p
1863:2
1860:L
1856:p
1849:p
1836:2
1833:L
1825:1
1822:L
1816:.
1814:c
1810:s
1808:(
1806:2
1803:K
1799:s
1797:(
1795:1
1792:K
1786:s
1782:c
1773:.
1771:c
1767:s
1765:(
1763:2
1760:K
1756:s
1754:(
1752:1
1749:K
1745:c
1741:s
1739:∀
1733:2
1730:L
1726:1
1723:L
1719:c
1715:2
1712:L
1708:1
1705:L
1697:2
1694:K
1690:1
1687:K
1668:D
1664:P
1658:|
1656:D
1652:P
1646:|
1636:D
1632:P
1628:L
1624:L
1620:D
1610:L
1606:L
1558:}
1555:x
1552:=
1549:)
1546:c
1543:(
1540:U
1537:,
1534:S
1528:c
1525::
1521:|
1517:c
1513:|
1509:{
1500:)
1497:x
1494:(
1491:K
1483::
1471:x
1451:x
1418:2
1397:S
1374:K
1344:y
1341:,
1338:x
1312:2
1298:K
1279:|
1275:x
1271:|
1262:2
1237:x
1213:)
1210:1
1207:(
1204:O
1184:)
1181:)
1178:y
1169:,
1166:x
1157:(
1151:(
1148:O
1125:c
1122:+
1119:)
1116:y
1113:(
1110:C
1107:+
1104:)
1101:x
1098:(
1095:C
1089:)
1086:y
1083:x
1080:(
1077:C
1057:y
1054:,
1051:x
1031:0
1025:c
1005:)
1002:)
999:y
990:,
987:x
978:(
972:(
969:O
949:y
929:x
909:)
906:y
903:(
900:C
897:+
894:)
891:x
888:(
885:C
879:)
876:y
873:x
870:(
867:C
844:U
824:)
821:x
818:(
815:f
812:=
809:)
806:x
801:f
797:s
793:(
790:U
787:,
778:2
771:x
746:f
742:s
715:2
702:2
698::
695:f
669:2
656:2
652::
649:U
626:c
619:|
615:)
612:x
609:(
606:g
600:)
597:x
594:(
591:f
587:|
583:,
580:x
574:,
571:c
548:)
545:1
542:(
539:O
536:+
533:)
530:x
527:(
524:g
521:=
518:)
515:x
512:(
509:f
489:)
486:x
483:(
480:g
477:=
474:)
471:x
468:(
465:f
442:)
439:x
436:(
433:K
413:)
410:x
407:(
404:C
383:C
367:s
365:(
363:d
359:s
357:(
355:K
348:s
346:(
344:K
340:s
332:s
330:(
328:d
324:s
316:s
312:s
310:(
308:d
274:s
267:x
263:w
259:M
255:x
251:w
247:M
243:M
239:M
220:P
216:x
212:P
208:x
204:P
123:P
115:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
