Re: Attention Sean - question about CSI

On 2007-08-06, R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <email@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f92pp9$2a9$1@xxxxxxxxxxxxxxxxx
On 2007-08-03, R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <email@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8un4l$9gq$5@xxxxxxxxxxxxxxxxx
On 2007-08-03, R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <email@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8ssa8$2g6$9@xxxxxxxxxxxxxxxxx
On 2007-08-02, R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <email@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8s40v$2g6$3@xxxxxxxxxxxxxxxxx
On 2007-08-02, R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
Compressing arbitrary strings to 1 bit depends on being able
to choose the computer. If you are stuck with an 8086 or
68030 derivative computer, that choice limits which strings
are compressible. Across the infinite set of all possible
computers, however, there are an infinite number on which it
is possible to compress any given string to 1 bit.

In that case, selecting the right computer to decompress is part of
the algorithm. How are you going to tell what computer to use with
just 1 bit?

That depends entirely on context. We could conceive, for
example, of a special cryptography computer being designed and
produced in a limited number, having a built-in set of large
random numbers. These computers would compress algebraic
combinations of large random numbers to readable text, and
decompress readable text to algebraic combinations of large
random numbers. The algorithms could be represented on the
computer by very short programs, such as "execute #1",
"execute #2", "execute #3", etc. The shortest algorithm
(execute #1) could be a 1-bit program. The shortest text
string can be a null string. There will be one really long
string on this machine that compresses to 1 bit, and the
design of the computer determines what that string is. The
choice of computer is made simply by handing copies of the
computer to the appropriate spies with a knowing wink.

You misunderstand me. You are not allowed to transmit anything,
except the compressed data and the description of the algorithm,
so "handling copies of computers" is not allowed here. If you
do that, you're just splitting the data transmission in two
parts, and you have to include both when comparing data sizes.

You are free to use any language to describe the algorithm. For
simplicity, let's say you are transmitting the algorithm and the
compressed data to an intelligent extra terrestial alien with
whom you have never communicated before. You can assume that
the alien is intelligent, and knows that the data you sent has
an algorithm description and compressed data.

Now, if the alien can *theoretically* figure out the algorithm
from the binary code, and use it to decompress the data, then
you sent enough to meet the requirement I meant above.

If, on the other hand, the alien is missing some crucial data,
and can't even theoretically decipher the data, you did not send
enough information.

Well, that is a bit silly. If the sender and receiver do not have
compatible computers, the description of the algorithm will be
meaningless for one of them, won't it?

All it takes is that they have compatible enough universes, that
"laws" of maths and logic are the same... You can carry out any
algorithm by hand, no automated computer is even needed... So
obiviously you do not get what I'm saying. I don't think I can
explain it any beter, so I have to give up.

You've already insisted that the size of the algorithm in bits has
to be included with the compressed data, so you've ruled out
carrying it by hand.

Of course not, you are talking nonsense... Sound like you do
not know what "algorithm" is. Look it up.

I refer you to your own words: "A side note: generally, in this kind of
context you need to include the compression algorithm in your size estimate,
ie you need to give the size of the decompression program plus the
compressed data."

In other words, the size of the compressed data must include the
size of the decompression algorithm. Isn't that what you were
saying?

How does "including the algorithm with the data" prevent
the one doing the uncompression to carry out the algorithm
by hand?

Isn't it almost the opposite. Even if you want to use a
computer to do the processing, you first must convert the
algorithm to a form your particular computer understands.
It is pretty much same as doing the algorithm by hand at
least once (not quite the same, but almost).

It's enough that there is universal way of representing binary
code, and universal "laws" of maths and logic. Intelligence can
figure out the rest, especially if the algorithm is converted to
symbols and symbols are converted to binary code while keeping in
mind that somebody would have to decipher it from scratch.

There is not a universal way of representing binary code, and not all
computers use binary.

Binary code is nice, because there are just 2 symbols. So if a signal
has just 2 symbols (say, laser on, laser off, or current on, current
off, or carrier wave modulated with frequence x or 2*x), any
intelligence can interpret it as binary code.

Yes, two-state modulation in a variety of forms is likely to be used by any
industrialized society for obvious technical reasons. What is not universal
is the mapping of the two-state modulation to a particular mathematical
numeral system and underlying algebra.

Yet, if the algorithm is meant to be figured out "from scratch",
it'd be smart to use as simple as possible encoding, and there
are not that many different encodings that could be called "the
most simple".

Again, computers have nothing to do with this (except they are a fast
way to carry out an algoritm). If you honestly believe that you need
a computer to have an algorithm, I think we can not find a common base
for this discussion, since (from my point of view) you just don't have
the basic knowledge of the subject.

Where did I say that you must have a computer to have an algorithm?

You seem to think, that if data has a description of algorithm, one
must have a computer to carry it out. I draw this coclusion from
*your* text "You've already insisted that the size of the algorithm
in bits has to be included with the compressed data, so you've ruled
out carrying it by hand." You wouldn't say that if you thought that
an algorithm could be carried out by hand based on a description, as
far as I can see.

I'm familiar with quite a few number systems in binary. The least
significant bit can be on the left or the right. It can be fixed
point, floating point, binary coded decimal, Gray Code, etc. It
can be a unary system with the addition of zero (I've used that in
a custom chip design before). Or, we can use a positional system
with a non-standard sequence of position value.

There are not universal laws of maths, either. Gödel proved this to be
impossible.

There are universal enough laws. I don't believe there is a place in
this universe, where taking one rock and then second rock (ordinary
solid rocks), you end up with anything but two rocks. You may believe
differently, which again of course proves that our basic thinking is
too different for this conversation to make any sense.

There are many possible algebras. Each is defined by axioms. The statement
1+1=2 is not valid in all algebras. Math does not have to operate on the
natural numbers. Peano arithmetics do, but math is much broader than that.

Ok, so I must add one more requirement for the receiver and
uncompressor: they must be not so far transcended from physical
existense, that they have forgotten natural mathemtacial truths
like "1 solid ordinary rock + 1 solid ordinary rock = 2 solid
ordinary rocks".

But this has nothing to do with my requirement for testing if a
piece of data is compressible...

All finite data is compressible. No computer can compress a larger set
of
strings than the pigeonhole principle allows, but the set varies from
computer to computer.

If all data was compressible, you could do this:

1. You give me a computer of any kind.

2. I give you a DVD *full* of bits.

3. You compress that data, and give it back to me on a DVD of same
size, that also *with free space*, ie the compressed version takes
less space.

4. I pop the disk into the computer from step 1, and can decompress
the data, and get data identical to step 2.


Do you *really* think you can do this, even if the DVD of step
2 containts bits generated from eg. thermal noise, with equal
probability for 0 and 1?


No, I do not think I could do this, because you are forgetting that the
computer design must be selected *post hoc* for any arbitrary string to
be
compressible. If the computer is selected before knowing the string to
compress, the probability that the string is not compressible is nearly
1.

Switch the order of steps 1 and 2, and then yes, it can be done.

Yes, if you have already given the data to the receiver, then you
do not need to send it again, all you need to send is request to
use the pre-sent data... What I do not understand is, why do you
think it is somehow interesting, or somehow relevant here...

I've already provided an example of where that kind of a system
might come in handy - cryptography. Hash tables would be another.

The thing is, compression/decompression involves three things: the
data, the algorithm, and a reference computer or language against
which the algorithm works. All of these things can be expressed as
strings, but we cannot universally express all three. We can express
the data and the algorithm with respect to a reference computer or
language, and measure its compressed/uncompressed length against
that reference. The choice of reference affects the length rather
dramatically. We can simulate the reference on a different
reference, and measure its relative size that way - but there are an
infinite number of possible references. This is quite similar to
having a Gödel numbering for all computable functions. Any
computable function can be assigned to the shortest integer, just as
any computable function can be assigned to the shortest possible
program on some reference computer.

In our universe, there is one common reference: the universe.
Even if natural laws change over time etc, as long as there is
at least enough similarity between the universe sender observes,
and the universe the receiver observes, there is a starting point.
Therefore both the data and the algorithm to interpret the data
can be contained in a bit stream. And then the receiver, using
the universe as a reference, can figure out the algorithm and
interpret the data.


--
"Ja pilkut huusivat tuskissaan: 'Lisää vaseliinia, lisää vaseliinia!'"

.

Relevant Pages

  • Re: Attention Sean - question about CSI
    ... the best compression algorithm you have. ... It should compress very ... which compresses that string to a single bit. ... from the binary code, and use it to decompress the data, then ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... the best compression algorithm you have. ... It should compress very ... which compresses that string to a single bit. ... already there uncompressed, why would you want to uncompress it ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... or the same CSI as a string of the same length where the ... the best compression algorithm you have. ... It should compress very ... which compresses that string to a single bit. ...
    (talk.origins)
  • Re: compression type
    ... occurance of what repeats, for there to be a token, for how tokens ... see its construction algorithm. ... It's very limited to think that's the only way to compress, ... made different, to the other shape, where the math to say one shape ...
    (comp.compression)
  • Re: Attention Sean - question about CSI
    ... is possible to compress any given string to 1 bit. ... except the compressed data and the description of the algorithm, ... In our universe, there is one common reference: ...
    (talk.origins)