Re: Anyone wanna help with a compression routine (new type)

On 9 Dez., 04:11, Ilya Zakharevich <nospam-ab...@xxxxxxxxx> wrote:
[A complimentary Cc of this posting was sent to
WM
<mueck...@xxxxxxxxxxxxxxxxx>], who wrote in article <04e91d5a-3cd0-4e19-abdf-c8f79fd45...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>:

far as I understood, we know: For every language a part of at least 1
- 2^-d of all bit sequences of length n has a Kolmogorow-complexity of
at least n - d. This yields the result (for d =3D 1) that at least half
of the strings have a Kolmogorow-complexity of at least n - 1, and
(for d =3D 0) that at least the empty set of strings has the complexity
of at least n - 0 =3D n.

First let me apologize for the symbol "3D" above. I did not intend to
write it and do not know what caused this format error. Please ignore
it.

This does not make sense. The Kolmogorow-complexity is defined up to
an additive constant ("the information contained in the
compiler/decompressor").

That's the reason why I originally did not use Kolmogorow-complexity.
It makes things depend on the abilities of programmers of compression
programs. I am interested in the uttermost limit of information which
is needed to address or identify a number. Therefore I do not consider
the information contents O(1) of the Turing machine as belonging to
the complexity of the number. I simply ask what numbers can be
identified by n bits (or symbols). Then every string of length n
requires at most n bits (or symbols). Compare my model for n = 7
symbols:
http://groups.google.com/group/sci.math.research/msg/a07444cf340546d5?dmode=source

Nevertheless my original (rhetorical) question has been answered
meanwhile: "Is it possible to compress every number n < 10^100^1000,
to start with, to an amount of 10^50 bits?" We know that this is
impossible. Therefore we can state an important result for
"calculating mathematics", whereby I mean mathematics which is
concerned with calculating numbers from numbers (i.e. numbers go in
and numbers come out): In calculating mathematics restricted to 10^50
bits memory space the Peano axioms are invalid.

Regards, WM

.

Relevant Pages
Loading