Re: Algorithmic Randomness is Universal (Was Re: Godel's Dualism ...)

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 05/18/04 

Date: 17 May 2004 19:41:28 -0700

"Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message news:<Zsaqc.50014$c43.42802@newssvr29.news.prodigy.com>...
>
> Is it ok if I accept Chaitin's description?
>

Of course, it is okay.

> http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html
> ..."But a young Swede visiting Kolmogorov in Moscow, P. Martin-Löf, realizes
> that something is wrong, because Kolmogorov's proposal for defining infinite
> random strings turns out to be vacuous. Kolmogorov had required infinite
> random strings to have all prefixes be incompressible, but this fails
> because Martin-Löf notes that long runs of 0's and 1's produce logarithmic
> complexity dips. (I also noticed this problem, and proposed a different
> complexity-based definition of infinite random string, a more permissive
> one.
>
> *This leads to the opposite problem, namely that it accepts some non-random
> strings.) *

I hadn't thought of that.

>
> So Martin-Löf abandons program-size complexity and proposes a
> constructive measure-theoretic definition of random infinite string. [A real
> number is Martin-Löf random iff it is not contained in any constructively
> covered set of measure zero.]
>
> What do I do? I don't abandon program-size complexity, I stick with it.
> I change the definition to use self-delimiting binary programs."

 I understand your concern. I also understand that Kolmogorov
complexity, as a subject, has a greater scope than Chaitin's work. I'm
a beginner in this area, and I'm learning still. I was trying to say
that the variations in definitions of Kolmogorov complexity has some
affordances, such as removing that logarithmic term in the
subadditivity of information, etc., but the main results in
incompressibility seem to remain intact. By the way, I have been
reading these rather excellent lecture notes of Alexander Shen. I have
learnt a lot of things from these concise notes that cannot be gleaned
from the entire text of Algorithmic Information Theory. There are
lectures on randomness, but I didn't read that part fully yet.

http://user.it.uu.se/~vorobyov/Courses/KC/2000/

(A great part of the text was the axiomatization of Kolmogorov
complexity...)

Best Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: What is complexity?
    ... >>>is infinite no matter what UTM you use for a reference. ... > Since the number of Turing Machines is infinite, the sum of Kolmogorov ... > complexity for all programs on all Turing Machines is also infinite. ...
    (talk.origins)
  • Re: Anyone wanna help with a compression routine (new type)
    ... we would believe in its randomness and its infinite information ... knowing Kolmogorov complexity but not being aware of pi. ... their infinite Kolmogorov complexity to a small amount and it would ...
    (sci.math.research)
  • Re: use of real numbers in mathematics and physics
    ... with an infinite amount of information. ... ::> And this will be so in any reasonable form of physics. ... complexity and computable real numbers demonstrate that ... itself requires similarly infinite precision. ...
    (sci.physics.research)
  • Re: Proof 0.999... is not equal to one.
    ... defining it as a limit is all but directly saying that it ... that does not directly correspond to an element in the other copy. ... or T that we attempted to map with U. ... mappable in one-to-one correspondance in infinite completion. ...
    (sci.math)
  • Re: Distinct linear orderings on Z
    ... >>constant distance from a fixed point. ... specified moving only. ... defining anything without sets, including 'infinity' and ... 'infinite'; and apparently 'circle'. ...
    (sci.math)