Re: For Sean Pitman: Review of "Meaningful Information"

On Mar 13, 6:59 pm, "R. Baldwin" <res0k...@xxxxxxxxxxxxxxxxxxxx>
wrote:

That's it. The length. Period. Nothing about predicting the sequence.

Consider the basic reason why those like Martin-Lof, Claus-Peter
Schnorr, Kolmogorov and Chaitin started thinking about the notion of
"randomness". It seems to me that it all started off on the question
of being able to predict the future nature of an as yet unknown
portion of a sequence or pattern based on what was already known.
This problem is described in terms of gambling - of not being able to
make money betting on a truly random sequence while being able to do
so when betting on a non-random sequence.

It doesn't matter how it seems to you. It matters what they wrote, and they
did not write what you seem to think they did.

For example, Chaitin:

"For four decades I have been using the idea of complexity to try to
understand the significance of Gödel's famous incompleteness theorem. Most
logicians and mathematicians think that this theorem can be dismissed. I, on
the contrary, believe that mathematics must be conceived of and carried out
differently because of Gödel.

"The fundamental question: What is a proof? Why is it convincing? What is
mathematics? In fact, Gödel's proof is a reductio ad absurdum of the idea of
a formal axiomatic math theory. Gödel, Turing and myself, what we do each in
our own unique way, is to assert increasingly emphatically that math is not
a formal theory, it is not mechanical. What then is math? Where do new
truths come from?

"Instead of saying what math isn't, how about a new, optimistic
metamathematics that says what math is, and how creativity, imagination and
inspiration make it progress? For like any living organism, math must
progress or it withers and dies. It cannot be static, it must be dynamic, it
must constantly evolve. And there are other pressing questions, particularly
for those of us who feel so attracted, so obsessed by mathematics. We
sometimes wonder: Why is it so beautiful? What precisely attracts us? Why do
we feel so attracted? Is there no end to such beauty?"

Nothing here about predicting the next symbol of a sequence, or about
gambling.

I agree with Chaitin here. However, these aren't the only questions
that are relevant. Even though Chaitin is asking were new truths come
from and how one is able to know that a new truth is likely to be in
fact "true" doesn't mean that he is questioning the notion of there
being anything that is in fact "true", predictable, or more or less
likely.

What we are talking about here is the concept of "algorithmic
complexity" as defined and modified by those like Kolmogorov, Chaitin,
and Solomonov (KCC). You argue that any KCC can compress any finite
sequence to a single bit depending on which UTM is chosen - which is
true. "For any string S, there is a universal machine Us such that
the complexity of S relative to Us is zero."

http://www.princeton.edu/~adame/teaching/PHI322_S2003/handout/kolmogorov.pdf

However, this isn't the end of the issue. As it turns out, the choice
of the UTM doesn't matter much when it comes to the KCC of longer and
longer sequences. "Suppose that U and U0 are both universal machines.
Then there is a constant k such that for any s, the complexity of s
relative to U never differs from the complexity of s relative to U0 by
more than k. So: fixing U and U0, in the limit as the strings get
larger, the particular choice of UTM matters less and less."

http://www.princeton.edu/~adame/teaching/PHI322_S2003/handout/kolmogorov.pdf

So, you see, if your selected UTM has to increase its size as the size
of the string increases in order to make the string's KCC equal to
zero, then there seems to be a relationship here to predictability.
For example, certain UTMs do not have to increase in size to reproduce
a specific sequence of increasing size. Such a situation is capable
of providing a great deal of predictive value with regard to what will
come next.

"Pi has low Kolmogorov complexity as it can be specified by a short
algorithm, whether it's Gauss's summation or one of the newer digit-
specifying algorithms. On the other side of the spectrum, the million
random digits can't be derived in any other way besides specifying
them in their entirety. The algorithm used to compute pi doesn't
change in size depending on how many digits are needed, it has a
constant Kolmogorov complexity. Since the algorithm used to determine
the random digits is in fact the digits themselves, it gets larger
with each additional digit -- it has a linearly increasing Kolmogorov
complexity."

http://everything2.com/index.pl?node_id=763572&lastnode_id=0

"Algorithmic complexity: A.K.A. Kolmogorov-Chaitin-Solomonov
complexity.

KCC does in fact play a significant role in this concept. Those like
Wallace and Dowe (see following excepts from their interesting 1999
paper) show the connection between KCC and sequence prediction:

C.S. Wallace and D.L. Dowe, Minimum Message Length and Kolmogorov
Complexity, The Computer Journal, Vol. 42, No. 4, 1999.

[snip extract]

I already informed you that Kolmogorov Complexity is related to MML. What I
told you in the previous post is still factual. Kolmogorov Complexity cannot
be used to predict the next symbol in a sequence.

All that is needed to use KCC for prediction is knowledge that the UTM
size doesn't need to be increased in order to keep the KCC of a
growing sequence the same. I'd say that is a very fine hair you are
splitting. MML, though not exactly the same as KCC, seems very
closely related.

< snip >

"No random sequence is decidable, computably enumerable, or
co-computably-enumerable." and "Every random sequence is normal."
Yet, finite strings cannot be normal, and they are decidable.

Just because a finite string cannot be normal doesn't mean that it
cannot be algorithmically random.

That depends on which concept of random you have under discussion.

The various concepts are all very closely related to each other. Why
all this hair splitting?

"Finite-length strings are allowed to be algorithmically random by
definition. Any finite-length string can be taken as a rational number
in some base, and rational numbers cannot be normal in any base. . .
Algorithmically random strings are either computable and
deterministic, or uncomputable."

http://www.talkorigins.org/faqs/information/algorithmic.html

I am well aware of that paragraph. I wrote the article. The article was
strictly about algorithmic information theory as defined by Kolmogorov,
Chaitin, and Solomonoff. It does not address Martin-Löf or Schnorr. Yes,
finite strings can be algorithmically random under Kolmogorov's definition.
I was attempting to show you that your previous post confused three
mathematically distinct concepts of algorithmic randomness: Kolmogorov,
Martin-Löf , and Schnorr. Apparently you did not understand.

Apparently you do not grasp the basic point of this whole discussion.
Different types of sequences and patterns do indeed exhibit features
that can be used to predict if their origin was likely random or
biased. That's the whole point here. Can you make money betting on
your prediction based on nothing more than mathematically evaluating
the pattern or sequence that is already there in front of you? The
answer to this question is clearly "yes". Hair splitting on if the
pure definition of Kolmogorov complexity or some other strongly
related concept can be used to answer this question is basically a red
herring.

Sean Pitman
www.DetectingDesign.com



.

Relevant Pages

  • Re: Predicting the Future and Kolmogorov Complexity
    ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ... cannot be algorithmically random. ...
    (talk.origins)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... You argue that any KCC can compress any finite ... "Martin Lof took the approach that a sequence of heads and tails ...
    (talk.origins)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: Fasctode - Sort estimating complexity and B&V
    ... > Estimating complexity and needed time for N elements according ... > upper measurments we can stop original worst case sequence ... > since any algorithm is allowed to challange. ...
    (borland.public.delphi.language.basm)
Loading