Re: an true information theory

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 02/25/05 

Date: Fri, 25 Feb 2005 22:48:30 GMT

<borges2003xx@yahoo.it> wrote in message
news:786b0608.0502250652.5fa90f89@posting.google.com...
> "Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message
> news:<aozTd.7045$OU1.1069@newssvr21.news.prodigy.com>...
>> <borges2003xx@yahoo.it> wrote in message
>> news:1109235520.574476.33110@l41g2000cwc.googlegroups.com...
>> > i'd be happy of a theory of structure in messages
>> >
>>
>> I have no idea why you think there isn't.
>
> Can you distinguish if a message has structure or not? How?

If a message has meaning then it has structure and will show a pattern.
Suppose a message with meaning is encoded as numbers. There are
several tests mostly having to do with frequency and distribution to see
if there is a pattern in the sequence of numbers. Changing the numbers
into letters, supposing the message is a text message, is part of
cryptography.
> (i could suggest that is compressible). And the ocean of
> uncompressible number what in fact are?

Meaningful messages have the property of redundancy, the meaning
is repeated. Also some compression is quite likely. For instance in
English, the vowel "e" is the most common. So a native English speaker
could parse "rmov" as "remove" without much trouble as part of the code.

Randomness is an interesting concept. There can never be an exact
definition or criteria given for randomness. A definition says something
conforms to some certain pattern of properties. Randomness can never
have an exact definition because then it would be following a pattern and
that contradicts the meaning of randomness: not having a pattern.

Randomness applies to infinite sequences, not finite ones. For instance you
can flip a coin ten times and randomly get a sequence of heads and tails of
0101010101 (a perfect alternation)
That sequence, when examined by somebody who doesn't know the source
was random, will probably think it is part of a pattern. Just like rarely,
you
can flip ten heads in a row, 0000000000, a possible random result, but it
does not appear random to an outsider.

Randomness only truly applies to infinite sequences. And because the
sequence is infinte, there is never a proof that a specific sequence is
random. Though they can prove there are classes of truly random reals.

So take for instance Pi. Pi used to be considered random before the
Algorithmic Information Theory (AIT) was invented. That was because
very large finite samples were analyzed for a pattern using several tests
which measured the overall frequency of digits. Pi passed the tests so
it appears random. But Pi is not proven as random.

> What are random data without patterns or structure.? Are they oracle
> of halting problem?

Andrew Hodges wrote:
"Turing defined the 'oracle' purely mathematically as an
uncomputable function, and said, 'We shall not go any
further into the nature of this oracle apart from saying
that it cannot be a machine.' The essential point of the
oracle is that it performs non-mechanical steps."

SH: An oracle is a hypothetical mathematical entity, I don't think
it is physically realizable, ever. It is a _theoretical_ device that can
solve the halting problem, which is uncomputable. I think a hierarchy
of halting problems and oracles is part of this theory.

Most real numbers are random and uncomputable. Here is a more
technical article: http://szabo.best.vwh.net/perfect_compression.html

> Can u measure a "structurality" parameter? There are message with
> different data and same structure?
> The meaning is the same (if they have)?
>

I am not sure what your question means. There are sequences which
have patterns that can never be discovered. There are no machines
which can always find/discover a pattern so that some patterned sequences
cannot be distinguished from a random sequence.
http://www.cis.udel.edu/~case/colt.html
"Interestingly, it is mathematically proven that there can be
no computer program which can eventually find (synonym: learn)
these (algorithmic) rules for all sequences which have such rules!"

> Omega , the perfect oracle has structure?
>

Perhaps you are thinking that Omega, as an oracle, has some
connection to reality and meaning. I don't think it does, nor is
it intended to be understood in that way.

Chaitin:
"My Omega number has no pattern or structure to it whatsoever," says
Chaitin. "It's a string of 0s and 1s in which each digit is as unrelated to
its predecessor as one coin toss is from the next."

SH: In real life, we do not have infinite precision. Chaitin:

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/summer.html
Omega Number
"Halting Probability"

And some people are nice enough to call this "Chaitin's number". I
call it Omega. So let me try to give you an idea of how you get to
this number. By the way, to show you how much interest there is in
Omega, let me mention that this month there is a very nice article
on Omega numbers by Jean-Paul Delahaye in the French popular science
magazine Pour la Science, it's in the May 2002 issue.

Well, following Vladimir Tasic, Mathematics and the Roots of
Postmodern Thought, the way you explain how to get to this number
that shows that some mathematical facts are true for no reason,
they're only true by accident, is you start with an idea published
by Émile Borel in 1927, of using one real number to answer all
possible yes/no questions, not just mathematical questions, all
possible yes/no questions in English---and in Borel's case it was
questions in French. How do you do it? ...

"So this one number would answer all instances of Turing's halting
problem. And this number is uncomputable, Turing showed that in
his 1936 paper. There's no way to calculate this number, it's an
uncomputable real number, because the halting problem is unsolvable.
This is shown by Turing in his paper.

So what's the next step? This still doesn't quite get you to
randomness. This number gets you to uncomputability. But it turns
out this number, Turing's number, is redundant. Why is it redundant?

Redundant

Well, the answer is that there's a lot of repeated information in
the bits of this number. We can actually compress it more, we don't
have complete randomness yet. Why is there a lot of redundancy? Why
is there a lot of repeated information in the bits of this number?
Well, because different cases of the halting problem are connected.
These bits bN are not independent of each other. Why?

Well, let's say you have K instances of the halting problem. That
is to say, somebody gives you K computer programs and asks you to
determine in each case, does it halt or not.

K instances of the halting problem ?

Is this K bits of mathematical information? K instances of the
halting problem will give us K bits of Turing's number. Are these
K bits independent pieces of information? Well, the answer is no,
they never are. Why not? Because you don't really need to know K
yes/no answers, it's not really K full bits of information. There's
a lot less information. It can be compressed. Why?

Well, the answer is very simple. If you have to ask God or an
oracle that answers yes/no questions, you don't really need to ask
K questions to the oracle, you don't need to bother God that much!
You really only need to know what? Well, it's sufficient to know
how many of the programs halt. ..."

> on http://home.wxs.nl/~gkorthof/kortho44a.htm

Yes, I've read that and agree with,

Warren Weaver
  "The word information, in Shannon's theory, is used in a special sense
that must not be confused with its ordinary usage. In particular,
information must not be confused with meaning..." [5]

SH: This distinction is known at a certain level of education. Information
is used like one would use the word data. Language, especially English
uses the same words with different meanings all the time as long as the
difference in meaning is clear from the context or *announced* like
Shannon did. A panel is a kind of board can mean there is a piece of
wood cut a certain way, or, boards are composed of people to make
decisions and a panel arrives at a decision in a particular way.

Chatin's Omega/oracle, number of wisdom, has nothing to do with
meaning in the ordinary sense. It does not really answer practical
questions which is explained in the urls I've included (borel/omega).

>
> I am not sure if Crutchfield succeeded, but he tries to avoid the
> paradox.
>
>
> [snip]
>
> do you think that is pleonastic?

I'm not sure about this, I don't really know. I understand this term
to describe a "slot filler" with no semantic/meaning content. But this
is in real communication. So that is a kind of redundancy. But I
am not sure how the concept applies across, what are to me,
different categories. Maybe some expert knows the answer?

I think "pleonastic" is term which applies to actual reality.
I don't know how it applies to Chaitin's Omega or an oracle.
Because Omega doesn't physically realize answers, it is
uncomputable. I'm not sure of the meaning of the term in
Omega's context.

I did find another interesting article that goes into Chaitin
and Borel's number answering questions yes or no.
http://www.paginar.net/matias/articles/formalthought.html
>
> where are the "structured" string in chaitin?
>

Few and far between :-)-- I mean Chaitin says no structure.
There are interesting enumerable distinctions around this.

Regards,
Stephen

Relevant Pages

  • Re: an true information theory
    ... > Kolmogorov, Chaitin, Wolfram and so on, consider a non random>sequence, ... > a small program that generate pi, for example, which has no pattern, no ... is already interested in meaning within a statistically emergent mentality. ... Can the rule finding itself be done by some computer program? ...
    (sci.math)
  • Re: Snowflakes with High CSI
    ... figures will be construed as proof that you cannot measure CSI. ... or not detect a bias in a pattern is the same thing IDists claim to be ... IOW, the sequence not only has to have a specific sequence, but that ... my zip code +4 would, of course, have meaning for *me*, but might not ...
    (talk.origins)
  • Re: Choice sequences, intuition, etc
    ... specifying a different method of constructing the sequence, ... Regarding Bishop, ... axiom systems for mathematics that are weaker. ... Somehow the distinction in meaning between an implication ...
    (sci.logic)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... If the phenomenon in question shows a random-type pattern, ... have access to a code that contains a much longer sequence. ... Your model of single bit compression does not seem to me to be a ... strings with shorter input strings depends on the reference computer. ...
    (talk.origins)
  • Re: On Well-Ordering(s) and Sets Dense in the Reals, Infinity
    ... >> except equipollent may have a different meaning than that there ... > sequence of application of derivation rules; ... > ordering is a well-ordering? ... "uncountability of the reals", or rather, I do. ...
    (sci.math)