Re: Attention Sean - question about CSI

On Aug 4, 2:06 pm, Ari H <em...@xxxxxxxxxxxxxxxxxxxxx> wrote:
On 2007-08-03, R. Baldwin <res0k...@xxxxxxxxxxxxxxxxxxxx> wrote:





"Ari H" <em...@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8un4l$9gq$5@xxxxxxxxxxxxxxxxx
On 2007-08-03, R. Baldwin <res0k...@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <em...@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8ssa8$2g6$9@xxxxxxxxxxxxxxxxx
On 2007-08-02, R. Baldwin <res0k...@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <em...@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8s40v$2g6$3@xxxxxxxxxxxxxxxxx
On 2007-08-02, R. Baldwin <res0k...@xxxxxxxxxxxxxxxxxxxx> wrote:
"Ari H" <em...@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:f8q7rv$v7d$1@xxxxxxxxxxxxxxxxx
On 2007-08-01, TomS <TomS_mem...@xxxxxxxxxxx> wrote:
"On Tue, 31 Jul 2007 19:12:04 -0600, in article
<O4Kdnbhd6Ix7QDLbnZ2dnUVZ_g6dn...@xxxxxxxxxxx>, dkomo stated..."

Bobby Bryant wrote:
If I have a string of 1,000,000 random binary digits -- genuinely
random, not created by a deterministic RNG -- does it have more,
less, or the same CSI as a string of the same length where the
bits have deliberately been set, e.g. by copying a pattern?

Consider the 1,000,000 random binary digits as a file and run it
through
the best compression algorithm you have. It should compress very
little. On the other hand, a file which has strong patterns will
compress a lot. Maybe the degree of compression can serve as a
measure
of the "pattern-ness" of the file. What relation this would have
to
CSI
I'm not sure because I haven't been following the raging CSI
debates.

If I am allowed to choose the compression algorithm *after*
seeing the million random digits, then I can choose one
which compresses that string to a single bit.

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.

Good luck doing that with 1 bit... :-)

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.

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.

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.

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.





This concept of compressing arbitrary strings to 1 bit with a
computer selected post hoc is well known in algorithmic information
theory.

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...

Hint: stop thinking about conventional computers and think about
Universal Turing Machines.

Based on above, I don't think you're in a position to give me hints.

It's interesting enough that he thinks Godel "proved" anything to be
"impossible".


.

Relevant Pages

  • Re: Attention Sean - question about CSI
    ... It should compress very ... If I am allowed to choose the compression algorithm *after* ... 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
    ... It should compress very ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... and decompress readable text to algebraic combinations of large random ...
    (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: 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)