And this means that they can potentially be used to achieve compression in run-length encoding. … The pictures below show the results of applying run-length encoding to typical patterns produced by cellular automata. … Examples of applying run-length encoding to patterns produced by cellular automata.

Run-length encoding is based on the idea of breaking data up into runs of identical elements of varying lengths. … In each case the input is taken to be broken into blocks of length 3. … Examples of Huffman coding based on blocks of length 3.

followed by a specification of the length of the sequence that the object describes. … For having once specified the basic sequence to be repeated, all that then needs to be given is a pointer to this sequence, together with a representation of the total length of the data. … Taking into account the length of the representation for each pointer, the compressed form of a nested sequence of length n will typically grow in length like Log[n] 2 .

The plots show what fraction of strings of a given length have been produced by each of the first 25 steps in the evolution of each multiway system. If less than half the strings of a given length are ever produced, this means that there must be some strings where neither the string nor its negation can be proved, indicating incompleteness. … Rules (f) through (i), however, produce exactly half the strings of any given length, and can be considered complete and consistent.

But if one looks just at the absolute maximum number of steps for any given length of input one finds an exactly linear increase with this length. … The result turns out to be given by 2 IntegerExponent[x + 1, 2] + 3 , which has a maximum of 2n+3 , where n is the length of the digit sequence of x , or Floor[Log[2, x]] . The average for a given length of input does not increase with n , and is always precisely 5.

But if one picks a different axiom system for logic—say one of the others on page 808 —then the length of a particular proof will usually change. … But as one tries to prove progressively longer theorems it appears that whatever axiom system one uses for logic the lengths of proofs can increase as fast as exponentially. A crucial point, however, is that for theorems of a given length there is always a definite upper limit on the length of proof needed.

One simple example of such a process is run-length encoding—a method widely used in practice to compress data that involves long sequences of identical elements, such as bitmap images of pages of text with large areas of white. The basic idea of run-length encoding is to break data into runs of identical elements, and then to specify the data just by giving the lengths of these runs. … (a) is unary, in which any given number is represented by a sequence of cells whose length is equal to that number.

One approach—which turns out to be similar to what is used in practice in most current high-performance general-purpose compression systems—is to set up an encoding in which any particular sequence of elements above some length is given explicitly only once, and all subsequent occurrences of the same sequence are specified by pointers back to the first one. … After this comes a specification of the length of sequence represented by this section of output, with the number given in the form used for run-length encoding above. … In the examples shown, pointers are used only for sequences of length at least 6.

Turing machine (a), for example, always finishes its computation after at most 5 steps, independent of the length of its input. But in most of the other Turing machines shown, the maximum number of steps needed generally increases with the length of the input. … Turing machine (e) shows an example in which the maximum number of steps grows like the square of the length of the input.

The first multiway system actually generates all strings in the end (not least since it yields the lemmas -> and -> )—and in fact strings of length n > 2 appear after at most 2n+7 steps. … The third multiway system generates a complicated collection of strings; the numbers of lengths up to 8 are 1, 2, 4, 8, 14, 22, 34, 45.