Re: Predicting the Future and Kolmogorov Complexity

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

< snip >

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: 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: 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: 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: FUD about CGD and GBDE
    ... >government has approved the use of AES with 256 bit keys for very ... that stress on the algorithm and maintain 256 bits of margin. ... I don't seriously think that either of CGD or GBDE will be broken ... The first reason is that it adds complexity. ...
    (freebsd-hackers)
  • Re: Hooray: the Church of Scotland shows the way
    ... If you are simply pointing out the limitations of algorithmic machines then I agree completely. ... any Turing machine could print out the solution to a non-computable problem if that solution were part of the machine's algorithm. ... Given the complexity of the universe it doesn't seem unlikely that the solutions to all manner of non-computable problems have been physically realised in some form and lie there waiting for us to latch on to them somehow. ... Whilst it's true that fundamental physics are essentially algorithmic in nature, ...
    (uk.religion.christian)
Loading