Re: Entropy

Thomas Richter wrote:

Mok-Kong Shen wrote:
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).

Let me roughly state what I have understood from you till the
present: Given U1 and U2 that work on an infinite string, either
KC1 and KC2 will come out to be both finite and of the same order
or, during the computation process (increasing the string length
at each step) both machines will show growth behaviours that are
'somehow' comparable. Is that ok?

But I don't yet see what this buys me. If I want to know the KC
of an arbitrarily given infinite string, I want a numerical value.
I choose a U and start computing. but I can evidently never finish
my work. If, when I increase the length investigated from L=1000 to
L=10000000000 by step of 1 the temporary result KC remains exactly
constant, do I know at all that this remains so thereafter? On the
other hand, if in that same interval the temporary result KC shows
an apparently exponential growth or is quite erratic (growing
sometimes very mildly and sometimes very strongly), do I know that
it can never be the case that that growth entirely vanishes
sometime later? I would need infinite time to know that in either
case, and that would render the concept of KC as such useless even
if the computation of KC is (if I don't err) to be regarded in
the sense of a gedanken-experiment. Note that in computing
a function that is represented by a convergent series, we know
that the process converges and can thus sensibly decide when to
stop. But here we are dealing with an arbitrarily given infinite
string, we know a priori nothing of its property.

Thanks,

M. K. Shen
.

Relevant Pages

  • Re: Calculus XOR Probability
    ... as is true for the other 9 digits, and finally, reminded you that my infinite ... The center-infinite string has its left string all zeros, ... that can't be determined in such an infinite division. ... and if you have any memory of the response which I describe ...
    (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: Cantor Confusion
    ... >> adding more and more digits to the number that you are constructing. ... That a infinite string of decimal ... Note that all digit positions in ...111 are finite. ...
    (sci.math)
  • 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)
Loading