Home > Archive > Compression > May 2005 > compressible vs. uncompressible data - who can enlighten me?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
compressible vs. uncompressible data - who can enlighten me?
|
|
| Claudio Grondi 2005-05-16, 3:55 pm |
| Important introductory information:
----------------------------------------------
I am after a very deep understanding of the
behind-the-scenes of compression, so I
believe, that it is vital to know about the
assumptions my current point of view on
compression is based on before helping
me out with an reply:
#1 it makes no sense to distinguish
compression and differential compression,
because all compression is in some way
differential, at least because the processing
abilities implemented on the machine and the
compression program itself are the data the
compression is done against.
#2 there is no such thing as suitability
of a string for compession or entropy
of data because e.g. the strings
"0000000000" and
"axo97glq48"
carry the "same amount of information"
(I don't understand and like this term,
but I haven't found any better yet)
and therefore it is in principle equal
hard to compress both of them.
My concern:
----------------
I would like to be able to grasp how the
architecture of the computer system design
and the data stored as a program are
related to the ease with which e.g. the string
"0000000000" can be compressed
(or related to the difficulties in compressing
the string "axo97glq48")?
Any hints towards enligthment
are appreciated.
Claudio
| |
| Willem 2005-05-16, 3:55 pm |
| Claudio wrote:
) My concern:
) ----------------
) I would like to be able to grasp how the
) architecture of the computer system design
) and the data stored as a program are
) related to the ease with which e.g. the string
) "0000000000" can be compressed
) (or related to the difficulties in compressing
) the string "axo97glq48")?
)
) Any hints towards enligthment
) are appreciated.
Each and every compressor carries with it an explicit or implicit model.
This model is essentially labeling certain strings as more likely than
others, and the effectiveness of a compressor is decided by how well it
models 'real-world data'.
Most compressors, especially the simpler/faster ones, make a lot of
tradeoffs to simplify (the implementation of) their models.
So, to wrap up, the string '0000000000' is more compressible because a
model that has a simple implementation (and still reasonably models
real-world data) inherently favors such strings.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Jim Leonard 2005-05-16, 3:55 pm |
| Claudio Grondi wrote:
> I am after a very deep understanding of the
> behind-the-scenes of compression, so I
Read this:
http://www.fadden.com/techmisc/hdc/
It will give you the basic information you need to ask more targeted
questions.
| |
| Matt Mahoney 2005-05-16, 8:55 pm |
| Claudio Grondi wrote:
> Important introductory information:
> ----------------------------------------------
> I am after a very deep understanding of the
> behind-the-scenes of compression, so I
> believe, that it is vital to know about the
> assumptions my current point of view on
> compression is based on before helping
> me out with an reply:
> #1 it makes no sense to distinguish
> compression and differential compression,
> because all compression is in some way
> differential, at least because the processing
> abilities implemented on the machine and the
> compression program itself are the data the
> compression is done against.
If by "differential compression" you mean predicting the next data
sample and coding the error, then yes. This coding method is
convenient for continuous data such as images and audio, but is
independent of the actual information content of the data.
> #2 there is no such thing as suitability
> of a string for compession or entropy
> of data because e.g. the strings
> "0000000000" and
> "axo97glq48"
> carry the "same amount of information"
> (I don't understand and like this term,
> but I haven't found any better yet)
> and therefore it is in principle equal
> hard to compress both of them.
The first string is more compressible in the algorithmic sense, in that
the length of the shortest program which outputs the data will be
smaller in the first case. Look up "algorithmic complexity" or
"Kolmogorov complexity" for more on this topic.
-- Matt Mahoney
| |
| Claudio Grondi 2005-05-16, 8:55 pm |
| > > I am after a very deep understanding of the
First thank you for the answers I have got
already, as:[color=darkred]
> Look up "algorithmic complexity" or
> "Kolmogorov complexity"
> Read this:
> http://www.fadden.com/techmisc/hdc/
> It will give you the basic information you need to ask more targeted
> questions.
I think (maybe I am wrong, because not went
into every detail of mentioned subjects yet),
these hints are not leading me to what I am after,
so I will try here to express my concern more
precise and detailed (consider, that
I am not very satisfied with what I have written
below, so please have enough patience with me
and read it all including the Finally block):
----------------------------------------------------------
I was not yet able to find information which
relates the features of a computing system
used to run an algorithm and the time and power
needed to get to the ratio of achievable
compression and the ability to find appropriate
compression algorithm.
Maybe I am asking for what has to
be done to get an algorithm able to perform
a transformation which favors e.g. arbitrary
choosen 255 values out of all possible values
of e.g. a 1 MByte data chunk, so that these
255 selected chunks can be compressed to
one byte in range 1 to 255 and the other ones
to chunks of data beginning with the 0-byte?
Can this be solved for chunks of any size
and for any size of the smallest data in
the transformation table? How does the size
of data required to store the algorithm
depend on the selected chunks which must
be compressed down to a byte?
Here a little bit more background information:
-------------------------------------------------------------
I am watching this newsgroup for at least
some months and are after understanding
of compression already for many years.
I have already looked into "algorithmic complexity"
and "Kolmogorov complexity" and have written
some own simple compression algorithms in the
past, but haven't got the feeling, that it touches the
core of what I am currently looking for.
From my current point of view a study of
compression algorithms doesn't help me
here much too, because the dependence on the
uderlying computing capabilities are assumed
at the very very beginning and the cost of the
data and algorithms stored in a machine
running a program and the data of the program
itself as also the principles of used mathematics
are not considered.
e.g. it is not considered that our computers
and the mathematics behind them are
designed in a way making it easy to compute
the area of a square with known length of its
side, but need some more time and additional
data to compute the area of a circle with known
length of a radius (with same precision).
How does the logic, the philosophy and
the way of reasoning we use affect the
approaches we use to compress data?
How do compression profit from additional
instructions added to new processors?
Which data available in the hardware
of a computer, especially in the processor
unit itself can be used in differential compression?
Which chunks of data can't be generated by a
computer program running on Intel Pentium
processors when not input in an explicit way
within this program?
If I understand it right, theoretically it should be
possible to find a transformation of data in
which e.g. a collection of 255 CDs storing 700
MByte each can be compressed to one byte, so,
that e.g. the company selling these CDs will need to
share only one byte to the customers which have
the appropriate compression program installed
to make the CD content available to them.
As the number of different CDs on the market
is maybe less than the maximum value
stored in a 32 bit integer, there is theoretically
possible to find a transformation algorithm able
to compress all of them to 32 bits each.
Finally:
----------
After many efforst towards understanding
compression I have got the feeling, that there
is something important to know about the
mathematics and the computing systems
used, but I am still not really seeing me able
to express what I am asking for,
BUT
I hope, that maybe someone who has got
same feeling in the past reads this and is
so kind to share with me what the precise
formulation of my question is and maybe
even the answer to it.
Thank you in advance for your attention
and the patience required to read such
a long and partially very chaotic content.
Claudio
| |
| David A. Scott 2005-05-17, 3:55 am |
| "Claudio Grondi" <claudio.grondi@freenet.de> wrote in
news:3esighF4p059U1@individual.net:
>
> If I understand it right, theoretically it should be
> possible to find a transformation of data in
> which e.g. a collection of 255 CDs storing 700
> MByte each can be compressed to one byte, so,
> that e.g. the company selling these CDs will need to
> share only one byte to the customers which have
> the appropriate compression program installed
> to make the CD content available to them.
> As the number of different CDs on the market
> is maybe less than the maximum value
> stored in a 32 bit integer, there is theoretically
> possible to find a transformation algorithm able
> to compress all of them to 32 bits each.
>
>
Then you don't understand it!!
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
| |
| Keith Thompson 2005-05-17, 3:55 am |
| "David A. Scott" <daVvid_a_scott@email.com> writes:
> "Claudio Grondi" <claudio.grondi@freenet.de> wrote in
> news:3esighF4p059U1@individual.net:
>
> Then you don't understand it!!
I'm not so sure about that.
Suppose there's an accessible central repository containing the exact
contents of 4 billion CDs. If you send me a 32-bit integer that
happens to be an index into the repository, I can derive the entire
700 MByte contents of the specified CD by looking it up in the
repository and retrieving the contents.
This can be implemented as a compression/decompression algorithm,
without the need for an external repository, by incorporating the
contents of the repository into the algorithm. This gives you a
compression/decompression algorithm that's extremely powerful when
operating on a specific limited set of files. The drawbacks are: it
works *only* on that limited set of files, and the algorithm can't be
expressed in less than about 3 exabytes (possibly less if you apply
some secondary compression to the repository).
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Claudio Grondi 2005-05-17, 8:55 am |
| Thank you Keith for supporting me in
expressing the idea I intended to share.
Reading this newsgroup I have often
got the impression, that many of the posted
questions and even some of the posted
replies on the subject of uncompressible
data result from lack of understanding
what compression basically is (watched
from my current point of view at the level of
"englightment" I currently am) , so I was
happy to read
among the replies also such strightforward
ones as e.g. those from Mark Adler, because
they were expressing some fundamental
knowledge about compression in a very
short and clear way stating e.g. in
"How to compress random IDs?",
that a random number generator
is the best compression algorithm for the
numbers generated by it, able to compress
chunks of data of any size which are
usually considered uncompressible
down to the few bytes required
to store the seed and the length of the data
to compress.
By the way: I would be very happy to understand
what "truly random" means, but to be honest I
don't really expect to get a good explanation
of it here, because this concept seems to be
the same way weird as e.g. this one of
artificial intelligence (changing all the time
dependent on what was already achieved).
I think, that it is very hard or even not possible
to find a clear path through the knowledge
available about compression not understanding
some fundamental truths about it.
Now I am at a point where I have
got the feeling, that I am missing vital
awareness about some fundamental
assumptions my thinking about compression
is based on, because after intermediate
clearing of the very foggy picture I had
about it years ago, it has started to be
foggy again.
I suppose, that the main part of the
picture dimming fog comes from not
understanding what the impact of the
set of in a microprocessor available
instructions on the ability to create
compression algorithms which can
be run on this microprocessor is.
Further I assume, that I am probably not
the first on this path, so maybe someone
can give me a hint which clears the foggy
picture again (until the next step where
it gets foggy again - as this is in my
eyes the usual way of getting to the next
level of enlightment about any matter).
Thank you in advance for any efforts
to help me.
Claudio
"Keith Thompson" <kst-u@mib.org> schrieb im Newsbeitrag
news:ln1x864keh.fsf@nuthaus.mib.org...
> "David A. Scott" <daVvid_a_scott@email.com> writes:
>
> I'm not so sure about that.
>
> Suppose there's an accessible central repository containing the exact
> contents of 4 billion CDs. If you send me a 32-bit integer that
> happens to be an index into the repository, I can derive the entire
> 700 MByte contents of the specified CD by looking it up in the
> repository and retrieving the contents.
>
> This can be implemented as a compression/decompression algorithm,
> without the need for an external repository, by incorporating the
> contents of the repository into the algorithm. This gives you a
> compression/decompression algorithm that's extremely powerful when
> operating on a specific limited set of files. The drawbacks are: it
> works *only* on that limited set of files, and the algorithm can't be
> expressed in less than about 3 exabytes (possibly less if you apply
> some secondary compression to the repository).
>
> --
> Keith Thompson (The_Other_Keith) kst-u@mib.org
<http://www.ghoti.net/~kst>
> San Diego Supercomputer Center <*>
<http://users.sdsc.edu/~kst>
> We must do something. This is something. Therefore, we must do this.
| |
| Willem 2005-05-17, 8:55 am |
| Claudio wrote:
) got the feeling, that I am missing vital
) awareness about some fundamental
) assumptions my thinking about compression
) is based on, because after intermediate
) clearing of the very foggy picture I had
) about it years ago, it has started to be
) foggy again.
Okay, here's a fundamental idea that is hard to get to yourself,
but easy to understand once it's explained sufficiently:
All decompressors, without exception, are essentially functions/mappings
from one set to another. Usually from files to files or from streams to
streams, sometimes from files to sets of files, or from files to streams.
As is evident from the counting theorem, any given decompressor will only
decompress a small fraction of its possible inputs by a significant amount.
Here comes the new insight:
All functions from 'something' to 'something else' can be viewed as
'decompressors', and are therefore subject to the counting theorem.
A computer, in itself, can be viewed as a function from 'programs' to
'program outputs', so that too is subject to the counting theorem.
So, basically, each computer is a 'decompressor'.
Now, to finish the loop, with a bit of imagination a decompressor can be
viewed as a 'CPU' that is 'executing' the contents of a compressed file,
with the decompressed fileset/file/stream as 'program output'.
So, in conclusion, there is a duality between computers and compressors.
The fundamental truth thus lies in the counting theorem, and in counting
the number of possible inputs and outputs..
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| SuperFly 2005-05-17, 8:55 am |
| On Tue, 17 May 2005 09:23:22 +0000 (UTC), Willem <willem@stack.nl>
wrote:
-8<-
>All decompressors, without exception, are essentially functions/mappings
>from one set to another. Usually from files to files or from streams to
>streams, sometimes from files to sets of files, or from files to streams.
>
>As is evident from the counting theorem, any given decompressor will only
>decompress a small fraction of its possible inputs by a significant amount.
-8<-
>The fundamental truth thus lies in the counting theorem, and in counting
>the number of possible inputs and outputs..
That's the compression part. But there is also the modeling part. And
if you can model the data, you can compress it. Take for example a set
of 100 dvd movies. If we see the dvd data as +/- 4GB numbers, in an
insanely big pool of 4GB big numbers, which from a statistical point
are random and have no connection. You can't be sure these numbers are
just members of a specific subset of their entire domain which can be
represented by a function that generates these subset numbers and an
index to specify the particular number.
And off course the counting theorem also applies here, and there is no
way to compress all 4GB files as proven by Vitanyi/Li. But there might
be ways to extract specific sets of relevant files (model them) from
what we now call the random domain into the non-random domain.
Basically we don't understand much about randomness yet. And we don't
know what is, and is not possible yet.
More on this at:
http://members.fortunecity.com/templarser/onaroll.html
-SF
| |
| Claudio Grondi 2005-05-17, 3:55 pm |
| Maybe I am making here
a historical breakthrough,
maybe I am telling just weird or
stupid things,
maybe I have not understood even
a single word in any text about the
whole Kolmogorov stuff,
but down to a simple example,
I suggest, that there is
_no_ difference between the
"randomness" within
the bits of the number:
2222222222
and the bits of the number
1974629487
or the bits of any other
ten digits long number,
so the compression of
any of it is in principle
same difficult.
The idea of
compressible/uncompressible
is just only a misunderstanding
feeded by the efforts put into
the development of myriads of
new compression algorithms.
Because I can't currently track
down the details maybe I can
ask someone who can:
Am I right or wrong in terms
of http://members.fortunecity.com/templarser/onaroll.html
stating, that there is nothing
special about the bit pattern of
the number
2222222222
compared to the bit pattern of
the number
1974629487
or any other ten digits long
number
?
In my current state of mind,
generally each pattern of bits
is equivalent from the point of
view of beeing compressible,
because what really matters
here is in my eyes not mentioned
at all because hidden in the
foundation all thoughts about it
are build on - the logic we use,
the patterns we agreed to be special
because they _appear to us_ as
well known patterns.
Imagine someone who all his life
meets only numbers like
1974629487
and develops its math on it.
As he stumble upon the number
2222222222
he will consider it total "random"
and therefore "not compressible",
because there is nothing like this
in his "database" called experience.
What I am looking for, is maybe
not so much the missing element
of a puzzle which allows to complete
the picture, but a new picture to
build from the beginning on a new
foundation by getting aware of the
very basic assumptions the whole
idea of compression is based on.
By the way: do someone know a
compression scheme based on
an external repository available
via Internet? Isn't it THE only true
way to excellent compression
rates?
Claudio
"SuperFly" <s@f.net> schrieb im Newsbeitrag
news:ahgk81d9c2svhl55868nj2lqdhdoor260n@
4ax.com...
> On Tue, 17 May 2005 09:23:22 +0000 (UTC), Willem <willem@stack.nl>
> wrote:
>
> -8<-
>
amount.[color=darkred]
>
> -8<-
>
>
> That's the compression part. But there is also the modeling part. And
> if you can model the data, you can compress it. Take for example a set
> of 100 dvd movies. If we see the dvd data as +/- 4GB numbers, in an
> insanely big pool of 4GB big numbers, which from a statistical point
> are random and have no connection. You can't be sure these numbers are
> just members of a specific subset of their entire domain which can be
> represented by a function that generates these subset numbers and an
> index to specify the particular number.
>
> And off course the counting theorem also applies here, and there is no
> way to compress all 4GB files as proven by Vitanyi/Li. But there might
> be ways to extract specific sets of relevant files (model them) from
> what we now call the random domain into the non-random domain.
>
> Basically we don't understand much about randomness yet. And we don't
> know what is, and is not possible yet.
>
> More on this at:
> http://members.fortunecity.com/templarser/onaroll.html
>
> -SF
>
| |
| David A. Scott 2005-05-17, 3:55 pm |
| "Claudio Grondi" <claudio.grondi@freenet.de> wrote in
news:3eubp3F517kiU1@individual.net:
>
> Because I can't currently track
> down the details maybe I can
> ask someone who can:
> Am I right or wrong in terms
> of http://members.fortunecity.com/templarser/onaroll.html
> stating, that there is nothing
> special about the bit pattern of
> the number
> 2222222222
> compared to the bit pattern of
> the number
> 1974629487
> or any other ten digits long
> number
> ?
>
If you only have 2 numbers to compress yes if one
of the numbers is 2222222222 and the other is 1974629487
then you could assign a 1 to the first and a 0 to the next
the problem is as you get more numbers that you want to compress
you need to have larger and larger numbers to represent those
you want to compress. If the number have simple patterns you
can write short prograns to assign numbers for these. But if
you have a large number of numbers with no apparant patterns
then you have to write a longer program to compress such a set
of numbers. You might even have to code the numbers directly in
your program to check for the number.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
| |
|
| "David A. Scott" <daVvid_a_scott@email.com> ha scritto nel messaggio
news:Xns965954AB347B9H110W296LC45WIN3030
R@213.155.197.138...
> "Claudio Grondi" <claudio.grondi@freenet.de> wrote in
> news:3eubp3F517kiU1@individual.net:
>
>
> If you only have 2 numbers to compress yes if one
> of the numbers is 2222222222 and the other is 1974629487
> then you could assign a 1 to the first and a 0 to the next
> the problem is as you get more numbers that you want to compress
> you need to have larger and larger numbers to represent those
> you want to compress. If the number have simple patterns you
> can write short prograns to assign numbers for these. But if
> you have a large number of numbers with no apparant patterns
> then you have to write a longer program to compress such a set
> of numbers. You might even have to code the numbers directly in
> your program to check for the number.
(preface: I'm on the same "s ing enlightment" path...Claudio is looking
for.. :))
Yes but one of Claudio's points is, are we sure that 2222222222 is
"universally" (or "naturally") a simple path?
Or rather 1974629487 is a universally simple one? Or just because **our
logic** considers the repetition of a symbol like a "simple" scheme?
Other "logics" might consider more complicate patterns (for us) as simpler
than repetition.
Do we require totally different "logic grounds" than the ones used till now
?
Best,
E.
| |
| Matt Mahoney 2005-05-17, 3:55 pm |
| Claudio Grondi wrote:
> Because I can't currently track
> down the details maybe I can
> ask someone who can:
> Am I right or wrong in terms
> of http://members.fortunecity.com/templarser/onaroll.html
> stating, that there is nothing
> special about the bit pattern of
> the number
> 2222222222
> compared to the bit pattern of
> the number
> 1974629487
> or any other ten digits long
> number
> ?
This article doesn't seem to address your question. To say that random
data cannot be compressed, you need a precise definition of "random".
The widely accepted meaning of the word is that if something is
unpredictable, then it is random, but this definition depends on an
observer or agent, and the result depends on what the agent already
knows. A coin flip is random until you look.
In http://www.idsia.ch/~marcus/ai/aixigentle.htm
Hutter gives a precise mathematical definition of an agent as a system
which interacts with its environment with the goal of maximizing a
"reward" signal from the environment. Hutter proved that if the
environment (including the reward signal) is computable on a Turing
machine, then the optimal behavior of the agent is to behave as if the
enviroment is computed by the Solomonoff distribution of possible
programs consistent with the behavior observed so far. The Solomonoff
distribution favors smaller programs because there is no other
distribution over an infinite set of nonzero probabilities that sum to
1.
The goal of data compression is to produce the smallest possible output
that can later be decompressed. The agent (you) output a probability
distribution P(1|h), P(2|h), ... P(n|h) as a guess for the next symbol
from n choices in a stream given input history h. The environment
outputs a symbol x, which is appended to h, and a reward signal -log
P(x|h). Your goal is to minimize the total (negative) reward signal,
which is the size of the output. Then according to Hutter, the optimal
way to assign P is to guess that the input stream originated from a
distribution of Turing machines consistent with those that could have
produced h, such that the probability assigned to each machine M is
proportional to 2^-|M|, where |M| is the length of program M in bits.
When expressed in this precise way, our common definition of randomness
is just Kolmogorov (algorithmic) complexity.
To answer the question "is 2222222222 random?" you test whether there
is a program shorter than this string (80 bits) that would output it
and halt. Obviously the answer depends on which progrmming language
you use, but Kolmogorov proved that the answer varies by only a
constant, C, which depends on the language and not on the size of the
input. This is true because you can always write a compiler in one
language to simulate any other language. The constant cannot exceed
the size of the compiler.
The Kolmogorov complexity of N repeats of a symbol is log N + C, so if
N is big enough, any repeating string is not random, regardless of what
language you use, so it is compressible. The factor of log N comes
from coding N in the program "repeat 'x' N times".
The problem with Kolmogorov complexity is that it is not computable in
general. If a procedure for finding it existed, then you could use it
to solve the halting problem. You can compute it for some special
cases, but there are also some hard cases, such as compressing an
encrypted block of 0 bits, where compression would be equivalent to
finding the key.
-- Matt Mahoney
| |
| Claudio Grondi 2005-05-17, 8:55 pm |
| Thanks to Matt Mahoney for his detailed
and interesting reply:
-----------------------------------------------------------------------
> In http://www.idsia.ch/~marcus/ai/aixigentle.htm
> Hutter gives a precise mathematical definition of an agent as a system
> which interacts with its environment with the goal of maximizing a
> "reward" signal from the environment.
I think I have seen something similar put in action
in practice at http://lmw.a-i.com/ ( Learning Machine
Challenge 2001 ) but haven't run into any pointers to
Hutter at that time.
Are there any implementations of the AIXI agent which
could be tested against the other approaches submitted
to the Challenge to proove the claim:
"We give strong arguments that the resulting AIXI
model is the most intelligent unbiased agent possible."
? Or am I on the wrong track here?
-----------------------------------------------------------------------
> The Kolmogorov complexity of N repeats of a symbol is log N + C, so if
> N is big enough, any repeating string is not random, regardless of what
> language you use, so it is compressible.
If I understand the above right, the calculation of
Kolmogorov complexity and the resulting
understanding of randomity and compressibility
is in contradiction to what I stated saying, that
there is nothing special in patterns with repetitions
compared to any other patterns.
Maybe I am wrong, but my intuition tells me now,
that going down to the details will probably make
the picture I have about computing and compression
more dark and foggy and result in deeper confusion
instead of enlightment.
Claudio
| |
| Keith Thompson 2005-05-17, 8:55 pm |
| "Claudio Grondi" <claudio.grondi@freenet.de> writes:
[snip]
> I suggest, that there is
> _no_ difference between the
> "randomness" within
> the bits of the number:
> 2222222222
> and the bits of the number
> 1974629487
> or the bits of any other
> ten digits long number,
> so the compression of
> any of it is in principle
> same difficult.
Any compression algorithm that can achieve extremely good compression
on some inputs (e.g., representing the contents of a CD as a 32-bit
number) will be able to do so only for a tiny fraction of all possible
inputs. For the "repository index" method discussed earlier, a CD
that happens to be in the repository can be compresed to 32 bits; that
same CD with a single bit flipped cannot. Unless you add some
secondary compression, the altered cd might be "compressed" to a copy
of its entire contents *plus* a bit to indicate that the compressed
form is not an index. (I'm oversimplifying somewhat; you can tell
it's not an index because it's longer than 32 bits.)
So the question of how good a given compression algorithm is depends
on the nature of the input it's going to be asked to compress. If it
can find and exploit some pattern in the inputs you give it, it's a
good compressor for those inputs. If the nature of the pattern is
simple repetition (for example, English words occurring multiple
times), then a general-purpose compression algorithm that doesn't
depend on some internal or external repository is likely to work well;
such an algorithm is going to work better on 2222222222 than on
1974629487. If you have some reason to think that 1974629487 is going
to appear commonly in your input (more so than, say, 1974629486 or
1974629488), tweaking your algorithm to recognize that particular
pattern may be fruitful. If your input then *doesn't* contain
1974629487, the effort will have been wasted and the algorithm won't
work quite as well as it could have without the tweak.
If the inputs we dealt with were mostly random and unpredictable,
compression would be largely futile. Since real-world inputs are
often redundant, compression is useful -- particularly the kind of
compression that works better with 2222222222 than with 1974629487.
BTW, unlike many of the regulars here, I'm not an expert on this
stuff; please correct any errors I might have made.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Matt Mahoney 2005-05-18, 3:55 am |
| Claudio Grondi wrote:
> Thanks to Matt Mahoney for his detailed
> and interesting reply:
>
-----------------------------------------------------------------------
system[color=darkred]
>
> I think I have seen something similar put in action
> in practice at http://lmw.a-i.com/ ( Learning Machine
> Challenge 2001 ) but haven't run into any pointers to
> Hutter at that time.
>
> Are there any implementations of the AIXI agent which
> could be tested against the other approaches submitted
> to the Challenge to proove the claim:
> "We give strong arguments that the resulting AIXI
> model is the most intelligent unbiased agent possible."
> ? Or am I on the wrong track here?
AIXI is not a practical system. The unbounded space model is not
computable, and the bounded space model runs in exponential time. The
important result is theoretical: that if data from our environment is
the result of a computable process, then any sufficiently large sample
is compressible, because small programs are more common than larger
ones, because no other distribution is possible. It puts Ockham's
Razor (the simplest explanation is best) and our intuition that
compression is a useful thing to do, on a firmer mathematical
foundation.
What AIXI does not do is tell us how to test if a string is
compressible, or how to compress it optimally if it is. Those are
still not computable.
-- Matt Mahoney
| |
|
| "Keith Thompson" <kst-u@mib.org> ha scritto nel messaggio
news:lnr7g51ou4.fsf@nuthaus.mib.org...
> "Claudio Grondi" <claudio.grondi@freenet.de> writes:
> [snip]
>
> Any compression algorithm that can achieve extremely good compression
> on some inputs (e.g., representing the contents of a CD as a 32-bit
> number) will be able to do so only for a tiny fraction of all possible
> inputs. For the "repository index" method discussed earlier, a CD
> that happens to be in the repository can be compresed to 32 bits; that
> same CD with a single bit flipped cannot.
Ok, just for the sake of it... for X streams of N bytes, how many
probabilities there could be to find two or more equal streams (equal
meaning same byte stream of same length, same bytes order, same values etc.)
but representing different "types of information", be it a picture in a
given format or a compressed file or an executable ? (considering raw data,
i.e. not including header bytes - otherwise it's just, none ^_^ )
Best,
E.
| |
| Keith Thompson 2005-05-18, 3:55 am |
| "Erpy" <info@forwardgames.com> writes:
> "Keith Thompson" <kst-u@mib.org> ha scritto nel messaggio
> news:lnr7g51ou4.fsf@nuthaus.mib.org...
>
> Ok, just for the sake of it... for X streams of N bytes, how many
> probabilities there could be to find two or more equal streams (equal
> meaning same byte stream of same length, same bytes order, same values etc.)
> but representing different "types of information", be it a picture in a
> given format or a compressed file or an executable ? (considering raw data,
> i.e. not including header bytes - otherwise it's just, none ^_^ )
I don't know.
If you assume the streams are entirely random, there are 2**(8*N)
possible streams (assuming 8-bit bytes). Computing the probability
that two or more of X such streams are identical should be fairly
straightforward, but I'm not going to do the math.
If you don't assume they're random, the question is much more complex.
Does the fact that two streams represent different "types of
information" make it more or less likely that they happen to be
identical? I have no idea; in general, I suppose it depends on the
details of the representations. (A stream of 7-bit ASCII text can
never match a stream in a format that requires some bytes to have
values in the range 128..255; if the format doesn't have that
requirement, it's conceivable that a thousand words could literally be
a picture.) I'd expect the probability to be very low for any
reasonable values of X and N.
I'm afraid I don't see the point behind your question. Can you
clarify?
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Malcolm Taylor 2005-05-18, 3:55 am |
| Hi Claudio,
I have been following this thread, trying to figure out what it is that
you are trying to grasp.
I'm not sure if this will be helpful, but here is another perspective on
compression.
You believe there is no difference between '2222222222' and
'1974629487'. However, just try rearranging the numbers in the first
string and see if you can create a new distinguishable string.
This is where Shannon came accross entropy. Accordingly, the entropy of
the first string is less that that of the second.
Now, the insight that Kolmogorov made, was that entropy was meaningless
without a definition of some form (the Gibbs equation in statistical
mechanics for example). So he generalised the definition by means of a
universal computer.
So accordingly, the compressibility can be directly related to the
Kolmogorov complexity of the string.
Now the unfortunate aspect of this work is that the Kolmogorov
complexity is not computable. In fact, asking what the exact value of
the Kolmogorov complexity is for a given string is meaningless. Why? A
simple thought will reveal that we need a method to encode the computer
program in order to find it's length. If we were to pick the shortest
such encoding, we would be attempting to try to find the Kolmogorov
complexity of the encoding... Somewhat recursive.
Maybe you can see a patern by now? All the results on 'randomness',
'entropy', 'compresibility' etc. all require a definition to be made
(somewhat arbitrarily) before they can be computed.
This leads us to the ideas in information theory, where we formalise the
idea of the 'definition' as a model. In this way we can figure out the
length of a compressed string by referring to the model as our
definition of what is 'compressible' or 'random'...
Now, most people will pick a useful model (such as a tree model, or
markov model which prove to be good models for language), but there is
no reason why we shouldn't pick a model based on something else, such as
a psuedo random generator (which would compress a string only if it were
generated with a given seed).
Also, if you want to get a valid measure of the 'compressibility' of a
given string, you must consider only a closed system. That means that
the size of dictionaries etc. have to be included. In the CD compression
example, the size of the library of CDs would have to be added to the
byte to get the actual compressed length under that model (which
obviously would turn out to be pretty bad!).
I suppose the most succinct conclusion, is that the difference in
compressibility between '2222222222' and '1974629487', is down to your
choice of model (ie. point of view).
Malcolm
| |
|
| "Keith Thompson" <kst-u@mib.org> ha scritto nel messaggio
news:lnis1h1jpq.fsf@nuthaus.mib.org...
> "Erpy" <info@forwardgames.com> writes:
etc.)[color=darkred]
data,[color=darkred]
>
> I don't know.
>
> If you assume the streams are entirely random, there are 2**(8*N)
> possible streams (assuming 8-bit bytes). Computing the probability
> that two or more of X such streams are identical should be fairly
> straightforward, but I'm not going to do the math.
>
> If you don't assume they're random, the question is much more complex.
> Does the fact that two streams represent different "types of
> information" make it more or less likely that they happen to be
> identical? I have no idea; in general, I suppose it depends on the
> details of the representations. (A stream of 7-bit ASCII text can
> never match a stream in a format that requires some bytes to have
> values in the range 128..255; if the format doesn't have that
> requirement, it's conceivable that a thousand words could literally be
> a picture.) I'd expect the probability to be very low for any
> reasonable values of X and N.
>
> I'm afraid I don't see the point behind your question. Can you
> clarify?
Well, that would simply mean that if you have N "data types" in which you
can always translate the input stream as it is, you have already compressed
by a magnitude of N all the other streams with "different meanings". (1
stream of size X+type_index equals also to N streams of the same size but of
different meaning - if you had to transmit all the N streams, you'd transmit
just Input_stream+index)
Of course I doubt you can *always* do that, infact you probably can do that
just for some coincidence...but I never tried. :)
(maybe with a hugely vast "knowledge base" of input streams... )
Speculation... ;)
| |
| Keith Thompson 2005-05-18, 3:55 am |
| Malcolm Taylor <me@me.com> writes:
[...]
> Now the unfortunate aspect of this work is that the Kolmogorov
> complexity is not computable. In fact, asking what the exact value of
> the Kolmogorov complexity is for a given string is meaningless. Why? A
> simple thought will reveal that we need a method to encode the
> computer program in order to find it's length. If we were to pick the
> shortest such encoding, we would be attempting to try to find the
> Kolmogorov complexity of the encoding... Somewhat recursive.
[...]
I think the following 47-byte string illustrates this point (or
something close to it):
"The smallest number not expressible in 47 bytes"
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Willem 2005-05-18, 8:55 am |
| SuperFly wrote:
) On Tue, 17 May 2005 09:23:22 +0000 (UTC), Willem <willem@stack.nl>
) wrote:
)
) -8<-
)
)>All decompressors, without exception, are essentially functions/mappings
)>from one set to another. Usually from files to files or from streams to
)>streams, sometimes from files to sets of files, or from files to streams.
)>
)>As is evident from the counting theorem, any given decompressor will only
)>decompress a small fraction of its possible inputs by a significant amount.
)
) -8<-
)
)>The fundamental truth thus lies in the counting theorem, and in counting
)>the number of possible inputs and outputs..
You snipped out the core of my argument, which is that a computer in itself
is also a 'decompressor', which means that the counting theorem applies to
it as well. More importantly, this means that we're working with a
'decompressor' that is fixed beforehand, which also means that you can't
speculate about different models, because that is fixed as well.
Because it's fixed (even if it's unknown) you have to come up with
arguments that correlate existing computers to a set of data. If not,
simple statistical analysis will show that the probability of being able
to compress a given set of data is vanishingly small.
) That's the compression part. But there is also the modeling part. And
) if you can model the data, you can compress it. Take for example a set
) of 100 dvd movies. If we see the dvd data as +/- 4GB numbers, in an
) insanely big pool of 4GB big numbers, which from a statistical point
) are random and have no connection. You can't be sure these numbers are
) just members of a specific subset of their entire domain which can be
) represented by a function that generates these subset numbers and an
) index to specify the particular number.
Mathematically, you can't be sure of anything. You can't be sure that your
computer will not suddenly jump into the air through the roof. But in the
real world, chances that are small enough can be considered zero.
If there is no reason why a set of dvds could be represented by a small
function, the probability of this occurring is so vanishingly small that it
can be neglected.
The probability of cosmic rays making a copy of Star Wars III appear on
your computer within the next month is greater than the probability that
the kol. complexity of a set of 100 dvd movies on any existing computer
is significantly small.
) And off course the counting theorem also applies here, and there is no
) way to compress all 4GB files as proven by Vitanyi/Li. But there might
) be ways to extract specific sets of relevant files (model them) from
) what we now call the random domain into the non-random domain.
Yes, but the probability that such sets of files are interesting (i.e. they
are actually a movie or a piece of music or whatever, instead of a lot of
useless garbage) is so small that it can be neglected.
) Basically we don't understand much about randomness yet. And we don't
) know what is, and is not possible yet.
But we can assign some rough ballpark estimates on the probability of what
is and is not possible in this field, and conclude that it is so unlikely
that it essentially *is* impossible.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Claudio Grondi 2005-05-18, 3:55 pm |
| Thank you Malcolm for the valuable contribution, where
when reading it I have got the feeling, that it helps much in
tracking down my confusion to the vital elements required
to be known before the confusion could be terminated
by an insight.
So let's now go down to the details to tackle the problem:
A) -------------------------------------------------------------------------
-------
> Also, if you want to get a valid measure of the 'compressibility' of a
> given string, you must consider only a closed system. That means that
> the size of dictionaries etc. have to be included.
In terms of the mentioned above,
my picture about compression has got foggy after I had
detected, that I have no idea about the size of the dictionaries,
etc. which are delivered with a computer able to run a program
(beeing e.g. the program with a compression algorithm).
As I have already mentioned in this thread, I believe also,
that it makes no sense to talk about pure compression
(without reference to already known data) distinguishing it
from differential one, because, to say it very simplificated,
one can't generate something out of nothing.
Fulfilling the requirement of considering only a closed system
includes for me also the computer system used to run the
compression algorithm on. With the ability to run programs
able to write data chunks larger than the code of the programs
and with content differing from what is programmed, I see the
new content generated not out of nothing, but from the
"data" delivered with the computer system, which are usually
not considered to belong to the size of the dictionaries.
From this point of view, the quality of any compression
algorithm depends therefore on two main criteria:
-#1. how good does the algorithm implement knowledge
about the data which it is expected to compress
(i.e. contains in itself even if not directly explicit, the
most often occuring data patterns)
-#2. how good does the algorithm use the ressources
delivered by the hardware and the operating system
which are maybe not directly data, but at least
potential data which can be got out of the system
using appropriate addressing e.g. in form of
programs able to generate data chunks larger than
the size of the addressing itself.
By the way:
it appears to me, that
#2. has currently much less impact on the
improvements in compression ratio than
#1., so #2 is maybe not as deeply studied
and analyzed as #1.?
Maybe it could be helpful here to consider the impact
of extending the set of available CPU assembler
instructions on the achievable compression
ratio for a finite precise defined collection of data?
Maybe it could be helpful here to consider the impact
of the programming language and the used compiler?
B) -------------------------------------------------------------------------
-------
> Maybe you can see a pattern/pastern(?) by now?
> All the results on 'randomness',
> 'entropy', 'compresibility' etc. all require a definition to be made
> (somewhat arbitrarily) before they can be computed.
Let me share here some introductory information on
another subject, before sharing my thoughts about
the above:
In the past I put some efforts into the idea of creating a
new better standalone dictionary able to provide the
explanation for any word avoiding what I call
"cyclic definitions", i.e. where one word is explained by
another one, which uses the first as its own explanation.
Sometimes the cycles found in available dictionaries are
not that apparent as mentioned above, because the
chain of words is much longer before the cycle goes
back to the origin, but it doesn't change the
insight, that none of the currently available dictionaries
can explain anything when the reader does not
understand some as a-priori known and therefore as not
needing any explanation assumed words (hidden behind
the cyclic definitions).
Considering the ideas of 'randomness', 'entropy',
'compresibility', 'non computablility', trying to get a
clear view on the meaning of any of these ideas,
I can't get rid of the feeling, that I am trapped here
in such cyclic references not explaining anything
but assuming the meaning will become clear
"by itself" if only elaborated long enough.
The real true insight is from this point of view to
get a clear view on an idea without need for any
further explanation. This implicates, that it is not
possible to share any insight using explanations
composed of words, but the good thing is, that
in spite of this there is a chance to communicate
the insight using words by asking someone to do
something in hope the experience gained from
doing it causes the insight.
Any suggestions what could *I* do?
C) -------------------------------------------------------------------------
-------
> I suppose the most succinct conclusion, is that the difference in
> compressibility between '2222222222' and '1974629487',
> is down to your choice of model (ie. point of view).
I think, that it makes sense here to cite a snippet out of the
posting by SaSW, Willem, before expressing my own thoughts
about it:
> [...] the core of my argument [...] is that a computer in itself
> is also a 'decompressor', [...] More importantly, this means that
> we're working with a 'decompressor' that is fixed beforehand,
> which also means that you can't
> speculate about different models, because that is fixed as well.
> Because it's fixed (even if it's unknown) you have to come up with
> arguments that correlate existing computers to a set of data.
I am not sure, but I suppose, that both statements have at least
one thing in common. They tackle the fact, that it is vital for any
further discussion of compressibility to have a model as reference.
If I understand SaSW Willem right, in his opinion (which I share
fully with him) at least the computer hardware and the operating
system can be seen as fixed in this model.
I suppose, that it would be very helpful to know about the results
of any available research on the impact of this part of the model
on the performance of compression algorithms, but I am not
aware of any work in this area.
Any hints towards this are therefore very welcome.
Claudio
"Malcolm Taylor" <me@me.com> schrieb im Newsbeitrag
news:428a8cf1$1@news.orcon.net.nz...
> Hi Claudio,
>
> I have been following this thread, trying to figure out what it is that
> you are trying to grasp.
> I'm not sure if this will be helpful, but here is another perspective on
> compression.
>
> You believe there is no difference between '2222222222' and
> '1974629487'. However, just try rearranging the numbers in the first
> string and see if you can create a new distinguishable string.
> This is where Shannon came accross entropy. Accordingly, the entropy of
> the first string is less that that of the second.
>
> Now, the insight that Kolmogorov made, was that entropy was meaningless
> without a definition of some form (the Gibbs equation in statistical
> mechanics for example). So he generalised the definition by means of a
> universal computer.
> So accordingly, the compressibility can be directly related to the
> Kolmogorov complexity of the string.
>
> Now the unfortunate aspect of this work is that the Kolmogorov
> complexity is not computable. In fact, asking what the exact value of
> the Kolmogorov complexity is for a given string is meaningless. Why? A
> simple thought will reveal that we need a method to encode the computer
> program in order to find it's length. If we were to pick the shortest
> such encoding, we would be attempting to try to find the Kolmogorov
> complexity of the encoding... Somewhat recursive.
>
> Maybe you can see a patern by now? All the results on 'randomness',
> 'entropy', 'compresibility' etc. all require a definition to be made
> (somewhat arbitrarily) before they can be computed.
>
> This leads us to the ideas in information theory, where we formalise the
> idea of the 'definition' as a model. In this way we can figure out the
> length of a compressed string by referring to the model as our
> definition of what is 'compressible' or 'random'...
>
> Now, most people will pick a useful model (such as a tree model, or
> markov model which prove to be good models for language), but there is
> no reason why we shouldn't pick a model based on something else, such as
> a psuedo random generator (which would compress a string only if it were
> generated with a given seed).
>
>
> Also, if you want to get a valid measure of the 'compressibility' of a
> given string, you must consider only a closed system. That means that
> the size of dictionaries etc. have to be included. In the CD compression
> example, the size of the library of CDs would have to be added to the
> byte to get the actual compressed length under that model (which
> obviously would turn out to be pretty bad!).
>
>
> I suppose the most succinct conclusion, is that the difference in
> compressibility between '2222222222' and '1974629487', is down to your
> choice of model (ie. point of view).
>
> Malcolm
| |
|
| "I think, that it is very hard or even not possible
to find a clear path through the knowledge
available about compression not understanding
some fundamental truths about it. "
I know what MATH it is that you, and everybody else, are missing.
It sounds like you want to "compress random data", but are too afriad
to say those exact words because you already know the general consensus
of the people that read/post to this group. I have been sing to do
that for a LONG time (8 years). As I figured about 5-6 years ago,
today's modern math is not going to work with the idea of compressing
"random" data.
So....I would be willing to help you figure out this "true" logic that
does not even exist in ANY computer system today as I have, but you
should have to follow the same path I did, because it made me
understand it more. I AM NOT STATING THAT I HAVE FIGURED OUT HOW TO
COMPRESS RANDOM DATA, just that I found a new math, and that I am
TRYING to find a way to do this with this new math.
Please contract me via e.mail if you want a little bit more
enlightenment.
k y l e . k w i l l i a m s @ g m a i l . c o m
(Please remove the spaces.)
| |
| jackokring@yahoo.com 2005-05-20, 3:55 am |
|
Goldy wrote:
> "I think, that it is very hard or even not possible
> to find a clear path through the knowledge
> available about compression not understanding
> some fundamental truths about it. "
yes i too think it is true if say I(S) = -log2(S) for symbol self
information is not understood.
>
> I know what MATH it is that you, and everybody else, are missing.
> It sounds like you want to "compress random data", but are too afriad
> to say those exact words because you already know the general
consensus
> of the people that read/post to this group. I have been sing to
do
> that for a LONG time (8 years). As I figured about 5-6 years ago,
> today's modern math is not going to work with the idea of compressing
> "random" data.
a standard understanding by removing entropic redundancy will never
lead to compression of random data.
>
> So....I would be willing to help you figure out this "true" logic
that
> does not even exist in ANY computer system today as I have, but you
> should have to follow the same path I did, because it made me
> understand it more. I AM NOT STATING THAT I HAVE FIGURED OUT HOW TO
> COMPRESS RANDOM DATA, just that I found a new math, and that I am
> TRYING to find a way to do this with this new math.
>
sounds interesting, but was it you who proposed the $1 million dollar
solution, i did not reply to it as i felt your(?) half had not been
proved.
> Please contract me via e.mail if you want a little bit more
> enlightenment.
>
> k y l e . k w i l l i a m s @ g m a i l . c o m
> (Please remove the spaces.)
when there is no entropic redundancy to be removed, then some other
method of compression must be found. A lower bound on the compressed
data has to exist by the fact that 1 bit output can only represent two
possible outputs. a simple application of the low order pigion
principal. when complexity reaches a critical threshold, a powerful
enough symbology may exist which can be represented in a higher number
of bits, which may encapsulate any random information stream.
Q. how may operators are required to represent a minimal possible
compactor (pigeon immune descriptor) group? and so how many bits?
compression requires that the data to be compressed is used in the
compression, and does not need to remain in the compression buffer. so
for compression to occur the compressed form has to have an upper bound
placed on its size in order for it not to exceed toward infinity data
output. so any compressor of this nature would need to have a maximum
output size which would be known in advance of compression. the only
reason for this not being of the minimal compactor size is for speed
and byte packing reasons.
Q. how much inefficiency of compression is optimum?
the only way to maintain a ceiling on the compacted size to arrange for
statistical shrinking of the output by making the compactor move
through a sequence of more probable (small) and less probable (big)
representations. understanding that a bias in symbol probability would
have to exist in such a compactor is the first step to classifying it.
Q. what statistical occurance probabilities would have to occur to have
useable bound controlled shrinking of information?
realizing that the compactor moves in a pseudo random sequence it is
reasonable to assume that only a small number of bits can be absorbed
by the statitically shrunk compactor, bringing back upto a bigger size,
and so a buffer absorbtion code has to be created to handle these few
bits per cycle, and to ensure absorbtion leads to a valid compactor
state, and to allow deterministic and computable desorbtion on
decompression.
Q. how many mappings between state are needed for a minimal absorbtion
code, and is Jaxon Modulation optimum? do all absorbtion codes only
operate on one bit of the compactor? and for the class that do what is
the required compactor modulated bit bias between 0 and 1 states needed
for the code to operate absorbatively?
enough for now?
jacko
| |
| Matt Mahoney 2005-05-20, 3:55 pm |
| jackokring@yahoo.com wrote:
> sounds interesting, but was it you who proposed the $1 million dollar
> solution, i did not reply to it as i felt your(?) half had not been
> proved.
Actually I had proposed that. I showed that random compression implies
P = NP, which is one of the seven problems for which the Clay institute
is offering a $1 million prize. See
http://www.claymath.org/millennium/
Essentially I showed that any problem (including NP-complete problems,
and even harder ones such as the halting problem) can be solved in O(n)
time by iteratively compressing the input down to a fixed size,
computing the compressed output using a lookup table, and decompressing
the output. There are some additional details, such as transmitting
the number of iterations and showing that each iteration of random
compression can be converted to a constant time operation, but these
are easy to prove. You can google this newsgroup for the details that
I posted earlier. I'm not aware of any flaws in the proof.
I had originally offered to split the prize money, but decided later to
let anyone completing the proof keep the whole thing. Once this proof
is published, I think it will be trivial to solve the other 6 Clay
problems, so it is a good tradeoff for me. Besides, most of the people
who have claimed that random compression is possible seem to lack
enough understanding of math to submit their entry to the Clay
institute in an acceptable form.
-- Matt Mahoney
| |
|
| "Matt Mahoney" <matmahoney@yahoo.com> ha scritto nel messaggio
news:1116601514.477532.185540@g49g2000cwa.googlegroups.com...
> jackokring@yahoo.com wrote:
>
> Actually I had proposed that. I showed that random compression implies
> P = NP, which is one of the seven problems for which the Clay institute
> is offering a $1 million prize. See
> http://www.claymath.org/millennium/
>
> Essentially I showed that any problem (including NP-complete problems,
> and even harder ones such as the halting problem) can be solved in O(n)
> time by iteratively compressing the input down to a fixed size,
> computing the compressed output using a lookup table, and decompressing
> the output. There are some additional details, such as transmitting
> the number of iterations and showing that each iteration of random
> compression can be converted to a constant time operation, but these
> are easy to prove. You can google this newsgroup for the details that
> I posted earlier. I'm not aware of any flaws in the proof.
>
> I had originally offered to split the prize money, but decided later to
> let anyone completing the proof keep the whole thing. Once this proof
> is published, I think it will be trivial to solve the other 6 Clay
> problems, so it is a good tradeoff for me.
Excellent! As a new millionaire...remember I've always been your dearest
friend - even though we don't know each other. :))))
>Besides, most of the people
> who have claimed that random compression is possible seem to lack
> enough understanding of math to submit their entry to the Clay
> institute in an acceptable form.
Acceptable form?!
Which would be? "Strict formal mathematical language" ?
Even though admittedly I know very little of such a language, you might have
noted as the researcher you are, that most math "geniuses" in history tended
to describe hard problems in plain english - often using metaphores or
everyday-life examples.
Also Einstein had problems with pure math, and didn't pass physics at a
younger age. :)
So, all this "academic" heritage of "speaking math"... I don't see the
point.
If my butcher has an idea for solving one of those problems, and explains it
by drawing a scheme cutting it in a piece of raw meat...didn't he solved the
problem anyway? - might be difficult to read...but he'd actually solved it.
:)))))
Best,
E.
| |
| jackokring@yahoo.com 2005-05-20, 3:55 pm |
| as far as i understood, all that was shown was to recall pre computed
results from an array. this waould be cached lookup and fast, but would
not obliviate the need to solve for all x in the NP computation before
the P array cache lookup. on execution multiple times t this would be
o(tP+xNP) not what is called P complete problem solving.
| |
| jackokring@yahoo.com 2005-05-20, 3:55 pm |
| too right! sorry for implicating others in the NP scam!
| |
| jackokring@yahoo.com 2005-05-20, 3:55 pm |
| too right! sorry for implicating others in the NP scam!
| |
| jackokring@yahoo.com 2005-05-20, 3:55 pm |
| too right! sorry for potentially implicating others in the NP scam!
| |
| Matt Mahoney 2005-05-20, 3:55 pm |
| Erpy wrote:
> "Matt Mahoney" <matmahoney@yahoo.com> ha scritto nel messaggio
> news:1116601514.477532.185540@g49g2000cwa.googlegroups.com...
dollar[color=darkred]
been[color=darkred]
implies[color=darkred]
institute[color=darkred]
problems,[color=darkred]
O(n)[color=darkred]
decompressing[color=darkred]
transmitting[color=darkred]
these[color=darkred]
that[color=darkred]
later to[color=darkred]
proof[color=darkred]
>
> Excellent! As a new millionaire...remember I've always been your
dearest
> friend - even though we don't know each other. :))))
>
>
> Acceptable form?!
> Which would be? "Strict formal mathematical language" ?
> Even though admittedly I know very little of such a language, you
might have
> noted as the researcher you are, that most math "geniuses" in history
tended
> to describe hard problems in plain english - often using metaphores
or
> everyday-life examples.
> Also Einstein had problems with pure math, and didn't pass physics at
a
> younger age. :)
>
> So, all this "academic" heritage of "speaking math"... I don't see
the
> point.
> If my butcher has an idea for solving one of those problems, and
explains it
> by drawing a scheme cutting it in a piece of raw meat...didn't he
solved the
> problem anyway? - might be difficult to read...but he'd actually
solved it.
> :)))))
>
>
> Best,
>
> E.
Sounds simple enough, but the Clay institute has their rules. You have
to publish your proof in a peer reviewed mathematics journal, wait 2
years, etc. etc. All the random compressionists know this is just a
conspiracy to let the anonymous reviewers reject their paper and steal
their ideas so they can claim the prize for themselves. That's why
they keep their technology a secret.
:-)
-- Matt Mahoney
| |
| Matt Mahoney 2005-05-20, 8:55 pm |
| jackokring@yahoo.com wrote:
> as far as i understood, all that was shown was to recall pre computed
> results from an array. this waould be cached lookup and fast, but
would
> not obliviate the need to solve for all x in the NP computation
before
> the P array cache lookup. on execution multiple times t this would be
> o(tP+xNP) not what is called P complete problem solving.
This is a common objection. It is due to confusing the cost of writing
a program with the cost of running it. Programming the lookup table is
hard but not impossible. Once it is written, it runs in O(1) time.
The P vs. NP problem is only concerned with running time.
Another common objection is that a lookup table is impractical. For
example, if your random compressor will compress all strings over N =
10^6 bits, then the lookup table requires 2^(10^6) x 10^6 bits, far
exceeding the 10^80 or so atoms in the universe. Again, this does not
affect the proof. An operation is O(1) if the run time does not depend
on the size of the input, even if it would take a trillion years on a
machine that is totally impractical to build.
A third objection is that the NP-complete computation is somehow hidden
in the random compressor, so the compressor takes exponential time to
run. This is addressed by showing that any random compressor can be
implemented in a way that runs in O(n) time (again, independent of the
cost of programming and building it). Given that any string longer
than N bits can be compressed, then certainly any string of N+1 bits
can be compressed to N bits. This can be done by a 2^(N+1) by N lookup
table. It must run in O(1) time (however slow this is) because the
input size is fixed. Therefore you can compress any string of
arbitrary length iteratively by appending one bit at a time to the
previous result and compressing it. (A small detail is that you must
also transmit the number of compression cycles so the decompressor
knows when to stop. There are various ways of including this number in
your data and compressing it as well).
It is not necessary to implement your random compression function as a
lookup table to claim the Clay prize. All you need is one of the
following:
1. A program that compresses all strings longer than N bits by at least
one bit (or at least from N+1 to N), where you choose N. Your program
may use arbitrary resources (CPU and memory) but must be provably
correct either by examination of the source code or by exhaustive
testing of all strings of length N+1.
2. Or a 1 to 1 mapping between all bit strings of length N and all bit
strings of length N+1.
You can submit the entire proof and claim the entire prize if you want.
Or I could write up my half of the proof in exchange for half of the
prize. I am pretty sure I can convince the Clay committee that my half
of the proof is correct.
-- Matt Mahoney
| |
|
| "Matt Mahoney" <matmahoney@yahoo.com> ha scritto nel messaggio
news:1116610625.214724.51460@g49g2000cwa.googlegroups.com...
> Sounds simple enough, but the Clay institute has their rules. You have
> to publish your proof in a peer reviewed mathematics journal, wait 2
> years, etc. etc. All the random compressionists know this is just a
> conspiracy to let the anonymous reviewers reject their paper and steal
> their ideas so they can claim the prize for themselves. That's why
> they keep their technology a secret.
> :-)
That's it...my butcher is out of the game. Too bad! ;)))
Best,
E.
| |
| guenther vonKnakspott 2005-05-20, 8:55 pm |
|
Keith Thompson wrote:
> "David A. Scott" <daVvid_a_scott@email.com> writes:
>
> I'm not so sure about that.
>
> Suppose there's an accessible central repository containing the exact
> contents of 4 billion CDs. If you send me a 32-bit integer that
> happens to be an index into the repository, I can derive the entire
> 700 MByte contents of the specified CD by looking it up in the
> repository and retrieving the contents.
>
> This can be implemented as a compression/decompression algorithm,
> without the need for an external repository, by incorporating the
> contents of the repository into the algorithm. This gives you a
What is the purpose of the whole thing if the decompressor will include
all of the information that is going to be compressed? Instead of
shuffling around with a compressor/decompressor simply transmit the
repository.
Regards
| |
| Claudio Grondi 2005-05-20, 8:55 pm |
|
> 1. A program that compresses all strings longer than N bits by at least
> one bit (or at least from N+1 to N), where you choose N. Your program
> may use arbitrary resources (CPU and memory) but must be provably
> correct either by examination of the source code or by exhaustive
> testing of all strings of length N+1.
It looks to me as approaching infinity with other infinity.
Nice to do on paper, not practical at all and of no
use as e.g. the proof I have once bumped into,
that it is possible to dissect a ball made out of real
numbers, so, that the parts put together give two balls
of same size (sorry, it was very long time ago and I
have no reference to this, but maybe someone else
can point to a page with such a proof?).
If this were practical, one would need only to produce
any item once, then dissect it to get two, then four, etc.
From my point of view the real numbers and infinity
have nothing to do with our real world, even if prooved
so useful in 3D geometry and 3D graphics.
So I can imagine, that the same can be done going
with N towards infinity in case of the compression
program as follows:
If N is infinity, than N+1 is also infinity because
infinity+1 is still infinity, so I can represent each
case of N+1 simply with N because both are the
same.
I have just won the prize!!! :-)),
didn't I ?
Where have I to publish this insight to fulfill the
requirements and get the money?
Claudio
P.S. Here the scheme of the program:
0. set N+1 to infinite value as length in bits
of the input data chunk
1. read N bits of the N+1 bits long data chunk
2. print N
N will be the same as N+1 because I can
check any bit of N+1 against any bit of N
and they will be the same.
I offer half of the prize to anyone who puts
the above into the language required by
the Clay committee, so that we can
successfully claim the money.
| |
| guenther vonKnakspott 2005-05-20, 8:55 pm |
|
Claudio Grondi wrote:
> Maybe I am making here
> a historical breakthrough,
> maybe I am telling just weird or
> stupid things,
> maybe I have not understood even
> a single word in any text about the
> whole Kolmogorov stuff,
> but down to a simple example,
> I suggest, that there is
> _no_ difference between the
> "randomness" within
> the bits of the number:
> 2222222222
> and the bits of the number
> 1974629487
> or the bits of any other
> ten digits long number,
> so the compression of
> any of it is in principle
> same difficult.
> The idea of
> compressible/uncompressible
> is just only a misunderstanding
> feeded by the efforts put into
> the development of myriads of
> new compression algorithms.
>
> Because I can't currently track
> down the details maybe I can
> ask someone who can:
> Am I right or wrong in terms
> of http://members.fortunecity.com/templarser/onaroll.html
> stating, that there is nothing
> special about the bit pattern of
> the number
> 2222222222
> compared to the bit pattern of
> the number
> 1974629487
> or any other ten digits long
> number
> ?
>
> In my current state of mind,
> generally each pattern of bits
> is equivalent from the point of
> view of beeing compressible,
> because what really matters
> here is in my eyes not mentioned
> at all because hidden in the
> foundation all thoughts about it
> are build on - the logic we use,
> the patterns we agreed to be special
> because they _appear to us_ as
> well known patterns.
> Imagine someone who all his life
> meets only numbers like
> 1974629487
> and develops its math on it.
> As he stumble upon the number
> 2222222222
> he will consider it total "random"
> and therefore "not compressible",
> because there is nothing like this
> in his "database" called experience.
>
> What I am looking for, is maybe
> not so much the missing element
> of a puzzle which allows to complete
> the picture, but a new picture to
> build from the beginning on a new
> foundation by getting aware of the
> very basic assumptions the whole
> idea of compression is based on.
>
> By the way: do someone know a
> compression scheme based on
> an external repository available
> via Internet? Isn't it THE only true
> way to excellent compression
> rates?
>
> Claudio
Try these basic ideas.
Given any compression algorithm of your choice, it wil only be able to
compress exactly eight files to a length of 3 bits. Why? Because there
are exactly eight different strings of three bits. Which files those
will be is totally dependent on what is called the Model. The model is,
if you will, the function that selects which files will be mapped to a
compressed string.
To illustrate what a model does, forget all about files and bits and
such. Suppose you have a hundred uniquely different oranges, and a bag
into which exactly eight oranges fit. Picture the model as the set of
criteria that determine which oranges will be put in the bag. You can
have a model that will select for bitternes, another will select for
sweetness and yet another for juicyness. A random model would simply
choose eight oranges out of the hundred, with no criteria being
applied.
So, from the point of view of a random model, 2222222222 and 1974629487
are as you note equally compressible. The art of good compression
consists in building models which will select according to known
properties, those strings which are desirable for compression.
This of course is put very simply, but I hope it helps.
Regards.
| |
| SuperFly 2005-05-20, 8:55 pm |
| On 20 May 2005 10:37:05 -0700, "Matt Mahoney" <matmahoney@yahoo.com>
wrote:
-snip-
>the
>explains it
>solved the
>solved it.
>
>Sounds simple enough, but the Clay institute has their rules. You have
>to publish your proof in a peer reviewed mathematics journal, wait 2
>years, etc. etc. All the random compressionists know this is just a
>conspiracy to let the anonymous reviewers reject their paper and steal
>their ideas so they can claim the prize for themselves. That's why
>they keep their technology a secret.
>:-)
Yeah, i'm sure someone who just found a way to model random data and
compress it, really wants to convince a bunch of orthodox math guys
using only their lingo for a minor million bucks, and not just sell
out to some major tech company and get insanely rich right away :-D
-SF
| |
| Matt Mahoney 2005-05-21, 3:55 am |
| Claudio Grondi wrote:
least[color=darkred]
program[color=darkred]
>
> It looks to me as approaching infinity with other infinity.
If the program existed you could iterate it to show a 1-1 mapping
between the set of all strings and a finite set of size 2^N. In other
words, you could prove that infinity is finite. Once you've done that,
you could prove all sorts of things.
:-)
-- Matt Mahoney
| |
|
| "Matt Mahoney" <matmahoney@yahoo.com> ha scritto nel messaggio
news:1116634880.268592.286030@g44g2000cwa.googlegroups.com...
> If the program existed you could iterate it to show a 1-1 mapping
> between the set of all strings and a finite set of size 2^N. In other
> words, you could prove that infinity is finite. Once you've done that,
> you could prove all sorts of things.
lol, please, define "infinity", other than "a useful abstraction", for a not
well erudited guy like me.
Dictionary:
Infinity \In*fin"i*ty\, n.; pl. Infinities. [L. infinitas;]
1. Unlimited extent of time, space, or quantity; eternity;
boundlessness; immensity. --Sir T. More.
[1913 Webster]
There can not be more infinities than one; for one
of them would limit the other. --Sir W.
Raleigh.
[1913 Webster]
2. Unlimited capacity, energy, excellence, or knowledge; as,
the infinity of God and his perfections. --Hooker.
[1913 Webster]
3. Endless or indefinite number; great multitude; as an
infinity of beauties. --Broome.
[1913 Webster]
4. (Math.) A quantity greater than any assignable quantity of
the same kind.
[1913 Webster]
The one with "God" reminds me of when science - and math - were "blessed" by
the holy Church. ;)
The one that says "indefinite number" ...sounds ok to me, "endless" a bit
less though.
Moreover current math doesn't like Sir W.Raleigh apparently, by using
different "orders of magnitude" of infinity... basically every single day
that endless almighty God gives us in His infinite love and patience. :)))))
Best,
E.
| |
| jackokring@yahoo.com 2005-05-21, 8:55 am |
| people somehow seem to miss the complexity log2(bits)+C issue would
imply that a length proportional count and a model coding and some
model parameters would represent the data of length bits.
the concept is to ignore the statistics of the stream to be compressed,
and concentrate more on the statistics of the model. the fact that data
may be random is of no consequence to the chosen model would represent
an excellent model.
absorbtion codings will always absorb when statistical bias is greater
than a known threshold, just as they will not absorb but emit excess
below said threshold.
wouldn't it also be true that compression of such a nature would put
someone in front of their piers, and would they be suitable judges. i
submit they are just rich. even if the technology were free surely
there maybe be work in the changes which followed, and the profiteers
would say "i worked for my wedge, you lazy enlightented bast**ds. new
get back to slavin' or i'll reduce yer beans like was done in the
twenties." and all would be defined as well when sleep or lack of
population was declared.
cheers and have another! :)
jacko
| |
| Claudio Grondi 2005-05-21, 8:55 am |
| > If the program existed you could iterate it to show a 1-1 mapping
> between the set of all strings and a finite set of size 2^N. In other
> words, you could prove that infinity is finite. Once you've done that,
> you could prove all sorts of things.
No I couldn't, because I assumed N+1 as infinity, so
it doesn't matter how many times I decrease it by one,
it will remain infinity.
That's the trick and I think it is ok, but I fear the committee
will deny to hand out the money to me as the committee
who looked for shortest program able to output own
source code has denied to give the first prize to the
guy who sent following code in (see the code between
the quotation marks): "".
For me it is currently a piece of evidence, that the idea
of infinity leads to many weird things causing endless
confusion, doesn't it?
Claudio
P.S. same thing with 0/7 = 0 (i.e. zero divided
by seven is zero) .
If I have nothing, it makes not much sense
to give it out to seven other people, right?
It is maybe the principle of how some people
earn their money with, but it doesn't proof
that it makes sense ;-).
"Matt Mahoney" <matmahoney@yahoo.com> schrieb im Newsbeitrag
news:1116634880.268592.286030@g44g2000cwa.googlegroups.com...
> Claudio Grondi wrote:
> least
> program
>
> If the program existed you could iterate it to show a 1-1 mapping
> between the set of all strings and a finite set of size 2^N. In other
> words, you could prove that infinity is finite. Once you've done that,
> you could prove all sorts of things.
>
> :-)
>
> -- Matt Mahoney
| |
| Claudio Grondi 2005-05-21, 8:55 am |
| > What is the purpose of the whole thing if the decompressor will include
> all of the information that is going to be compressed? Instead of
> shuffling around with a compressor/decompressor simply transmit the
> repository.
The fact which makes it useful is, that people are usually
looking selectively only for a small part of what is available
at a time.
E.g. if what is currently available on the Internet were put
together with the appropriate compressor into a small chip
delivered with each computer to users home, it would for
sure help to decrease the traffic on the network
even in case new things are published (as e.g.
new version of a program or new text), because
new things are usually based on existing ones
sometimes beeing even only a new arrangement
of the already available.
If I could send any file I want to publish on Internet
to a central repository which would then return to
me the code of the compressor accessing the
repository, so, that I can put it on the Net instead
of the actual file, I suppose many sites were able
to cut down the required storage space from
some gigabytes down to some megabytes.
Such compression ratio can't be achieved by
any other compression method.
I suppose, that the problem which prevents that
this way of compressing becomes standard on
Internet is, that any new entry to the repository
would make it necessary to check the provided
content against all of already available one,
which will require very fast computing to make it
practicable. It seems to be so, that noone is
currently ready to provide such a service due
to its expected high costs in terms of storage
space and computing power.
Claudio
"guenther vonKnakspott" <apacur@gmail.com> schrieb im Newsbeitrag
news:1116621714.146354.25090@z14g2000cwz.googlegroups.com...
>
> Keith Thompson wrote:
> What is the purpose of the whole thing if the decompressor will include
> all of the information that is going to be compressed? Instead of
> shuffling around with a compressor/decompressor simply transmit the
> repository.
> Regards
>
| |
|
| "Claudio Grondi" <claudio.grondi@freenet.de> ha scritto nel messaggio
news:3f8dilF6g4q1U1@individual.net...
> The fact which makes it useful is, that people are usually
> looking selectively only for a small part of what is available
> at a time.
> E.g. if what is currently available on the Internet were put
> together with the appropriate compressor into a small chip
> delivered with each computer to users home, it would for
> sure help to decrease the traffic on the network
> .....
Uhmm...this could be an interesting test...for who's got the money to do
it - that's always the end point of ALL matters. ;)
Take the latest english dictionary, put it on a ROM chip, build a compressor
that uses indexes to single words - it should stay in a 32bit index
(4bytes) - are there more than 4 billion words in current english? :)).
Now, if you're smart enough packing bits and building an "index micro
language" for indexes of size smaller than 32bit - otherwise it's just
always 4bytes - you end up using only a maximum of 4bytes for *any* word
anyone would put in *any* text document generated. (a good move would be to
assign words of longer char lenght to the shorter indexes of course ;)
Words not present in the dictionary obviously go uncompressed - as single
chars - and need to be tagged when storing into the compressed format.
And...let's see...nothing prevents you also from zipping your - already
compressed - index file (so basically, "guess" or "predict" the next word as
an index)...since this "dictionary" compression quite surely contains
redundancies of indexes for same words - or spaces, or commas etc.
But, beware Claudio...this would just prove that "knowledge" - which is the
ultimate form/upper-limit of prediction - leads to optimal compression. ;)
Best,
E.
| |
| Claudio Grondi 2005-05-21, 3:55 pm |
|
> But, beware Claudio...this would just prove that "knowledge" - which is
the
> ultimate form/upper-limit of prediction - leads to optimal compression. ;)
I tried to supress the temptation to do
it, but I failed, so I repeat as reply here,
what I have stated in this thread
in "The Englightenment!" posting
using the form of a question:
"Maybe is compression in principle only a post-correction
of an erroneous approach to coding of the experience we
gain from our environment and want to process in
a computer? Who knows ... (please post here! ;)"
Claudio
P.S. What about this above expressed
in one sentence? :
"On the path to true knowledge you will
inevitable meet the optimal compression."
Claudio
| |
|
| "Claudio Grondi" <claudio.grondi@freenet.de> ha scritto nel messaggio
news:3f8opuF6idamU1@individual.net...
>
> "Maybe is compression in principle only a post-correction
> of an erroneous approach to coding of the experience we
> gain from our environment and want to process in
> a computer? Who knows ... (please post here! ;)"
>
> Claudio
> P.S. What about this above expressed
> in one sentence? :
> "On the path to true knowledge you will
> inevitable meet the optimal compression."
> Claudio
Ok, this might have slipped under my very eyes :)
BTW, I'd correct my previous statement...being picky with myself here:
[..."knowledge" - which is the ultimate form/upper-limit of *guessed*
prediction - leads to optimal compression] ;)
Real "prediction" would be - theorically - the upper limit for knowledge.
Sure, it is far simpler to "know" something rather than "being *always*
absolutely right on something that you don't actually "know" in the first
place".
Another point would be: assume you have the whole "knowledge" as a database.
Would it be useful - and for which use - to try and predict information
anyway?
Say you freeze the information in the universe (even just your own PC... as
a "universe" :)) and acquire the whole data in that moment. Would this
acquired data be of any benefit, when you restart the "universe" and get the
information flowing again, at guessing the new data being generated?
(storing the whole data at each moment is of no use in terms of compression,
since you want compression of the very same data you'd want to store at each
moment)
Of course you can't assume the whole data as static - otherwise static
knowledge would suffice in terms of optimal compression.
Best,
E.
| |
| Matt Mahoney 2005-05-22, 3:55 am |
| Claudio Grondi wrote:
other[color=darkred]
that,[color=darkred]
[color=darkred]
> No I couldn't, because I assumed N+1 as infinity, so
> it doesn't matter how many times I decrease it by one,
> it will remain infinity.
Here is an example. I will prove that 2+2 = 5.
There are an infinite number of integers. But since infinity is
finite, there must also be some largest integer. Call it N. This
means that N+1 cannot be larger than N. Also it is clear that N+1 is
not less than N, so N+1 = N. By simple algebra:
N+1 = N
By the commutative property of equality, N = N+1
Adding 4 to each side, N+4 = N+1+4
Rewriting terms, N+2+2 = N+5
Subtracting N from each side, 2+2 = 5.
-- Matt Mahoney
| |
| Claudio Grondi 2005-05-22, 3:55 pm |
| > But since infinity is finite,
Sorry, butI I can't get the point here.
Infinity is for me _not_ finite, because if it were,
I wouldn't need it at all as a concept.
My proof is _not_ an inductive one, because it
is apparent that you can't compress any two bit
data chunk into one bit, so already the starting
condition is not fulfilled.
> there must also be some largest integer
No, there isn't one, because for each finite one
you can find another which is larger, so it makes
no sense to speak about THE largest integer.
I assume, you have something other in mind
writing this reply.
What was then the true intention of your posting?
Claudio
P.S. there is sure a problem with my proof, but
the reason for it is probably, that I skip the underlying
axioms from consideration according to the quotes
"For each problem, exists a simple, obvious
solution which is wrong" and
" An undefined problem has an infinite number
of solutions."
"Matt Mahoney" <matmahoney@yahoo.com> schrieb im Newsbeitrag
news:1116722775.523449.316640@z14g2000cwz.googlegroups.com...
> Claudio Grondi wrote:
> other
> that,
>
>
> Here is an example. I will prove that 2+2 = 5.
>
> There are an infinite number of integers. But since infinity is
> finite, there must also be some largest integer. Call it N. This
> means that N+1 cannot be larger than N. Also it is clear that N+1 is
> not less than N, so N+1 = N. By simple algebra:
>
> N+1 = N
> By the commutative property of equality, N = N+1
> Adding 4 to each side, N+4 = N+1+4
> Rewriting terms, N+2+2 = N+5
> Subtracting N from each side, 2+2 = 5.
>
> -- Matt Mahoney
>
| |
| Matt Mahoney 2005-05-22, 3:55 pm |
| Claudio Grondi wrote:
>
> Sorry, butI I can't get the point here.
I didn't mean infinity is finite. I meant that random or universal
compression implies that infinity is finite. A recurring theme in this
group is that another member will claim to have a program that
compresses all | | |