Re: Entropy

Mok-Kong Shen wrote:

Exactly *that* is the central point. It *does* disappear - if you call the dependency on the specific machine an "unfairness". This is the "Invariance Theorem", and there is a proof for this in the literature - but I already almost stated its proof (see above). I already said that a couple of times, but here again: If you have two such machines, then for any string A, the KC for the two machines differs at most by a constant c, independent(!!!) of A. Thus, you can carry the limit of A to infinity.

There is a c for the case of finiteness. Do you claim that for
the case of infinity c would be zero, or what?

Of course not. I claim exactly what I said before: c is a constant that
does *not* depend on the string. Which is the important property:

It does not depend on the target string.

So what does that mean?

It means that if I send the length of A to infinity, then either:

a) KC also tends to infinity - or -
b) KC stays bounded.

And this is *independent* of the Turing machine chosen, *because* such a c exists. If such a c would not exist, then whether KC diverges or not could depend on the machine.


So why does
the 'unfairness' disappear by going from finiteness to infinity?

Because it doesn't change the property of KC of diverging or not diverging, and if KC diverges, it doesn't change the rate by which it diverges. It is only an additive constant.

By "disappearing" I mean that the property of the KC diverging with string A length going to infinity does not depend on the language. The actual numbers, of course, stay different, but behavior for larger and larger strings is *not*.

I doubt I understand what you mean by "KC diverging with string A
length going to infinity" as such. Could you please explain a little
bit more?

Ok, so here are two typical examples of what can happen with KC:

Case a: The target string A consists of the digits of Pi.

In that case, for every universal Turing machine we find a *finite* program Y that generates the first N letters of A, and the size of this program *does not* depend on how many digits of A we asked for.

That is, if you generate 10000 digits of Pi or 1000000000 digits - you run essentially the same program, just tell it how many digits to generate.

In that case, KC stays bounded for N->infinity, and it stays bounded regardless of which Turing machine you pick. If this is the "lena" machine or a sane machine does not make any difference. The program size will differ, but the property that a *finite* program is sufficient to create Pi up to any digits you like stays the same.


Case b: Consider a string that is generated by an i.i.d. random generator over an alphabet of {0,1}, no memory, and p(0) = p(1) = 1/2.

In that case, if you want to reproduce an input string (a realization) of this random source up to N digits, you have basically no better chance than simply to put those digits into the program because the digits follow no rule at all, they are random.

That is, if you want to write a program that regenerates the 100000 digits of such a realization, then you basically have to write a program whose size is in the order of 100000. If you want to regenerate the first 1000000000 digits, then you have no better chance than to make the program also larger because there is no algorithm behind such series.

Which means that in case b, the KC *diverges* as N->infinity because the required program size to reproduce such a string grows. And whether it diverges does not depend on the Turing machine chosen. I do *not* have a
"magic Turing machine" that allows me to generate a random string of 10^20 digits in considerably less instructions than 10^20.

And again, the constant c is only a constant and doesn't change this behavior.

(Interestingly, from this almost trivially follows that the number of
computable strings, i.e. those of type a) is a zero-set in all other
strings - or rather, the "amount" of non-computable numbers is seriously larger than the "amount" of computable numbers. The first is aleph_1, the second is aleph_0. But that only as a side-remark).

And I also like to recall here the difficulties of dealing with
infinite strings I stated in a previous post.

You never deal with "actual infinities", but you check what happens if you send the size to infinity.

So long,
Thomas
.

Relevant Pages

  • Re: Cantors diagonal proof wrong?
    ... Infinity is not an integer, ... just a string of digits, ... >possible to prove anything by contradiction. ...
    (sci.math)
  • Re: How to convert extra long strings into their equivalent Hex Strings in VBA (Word 2K)
    ... numbers (upto 18 digits max) into its equivalent Hex String ... Public Function ExpressServiceCode(ByVal ServiceTag As String) As String ... 'the number dblTemp in the specified base, ... Dim lngTemp As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: BigNum -- Floating Point
    ... The 'N' is the number of decimal digits. ... The internal representation is really just a string of bits. ... the number of shifts for various multiples of ten: ... The 'exponent' is very closely related to ...
    (comp.programming)
  • Patterns in pi, copyright law, and philosophy
    ... Whether the offset of a string found in pi can be used as a form on ... then calculate how many digits of pi one would need to raise the ... "An infinite series of numbers is not an exhaustive set of numbers. ... finite string of digits occurs within the decimal expansion of pi, ...
    (sci.math)
  • Re: Patterns in pi, copyright law, and philosophy
    ... The digits of pi are widely believed to be "normal", in the sense that every n digit combination of digits is equally likely, and pass all reasonable tests of randomness. ... The mean length of the offset must at least be equal or greater than the length of the string you are looking for. ... Pi has an infinite representation as a decimal. ... finite string of digits occurs within the decimal expansion of pi, ...
    (sci.math)