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