Re: Entropy

Thomas Richter wrote:

This is not quite what I meant. You need to carry the limit of the input sequence going to infinity, that is, you consider codes for Turing machines that re-generate the truncation of the infinite sequence A up to N sequences, then stop. Then you carry that N->infinity.

In that limit, you have the two important classifications:

A) the size of the program remains finite. Then you have a computable sequence. For example, the sequence of Pi is computable.

B) the size of the program continues growing. In that case, the input is not computable. You can then, for example, consider something like the average number of program steps required per output symbol, should that limit exist.

This classification then is independent from the Turing machine chosen.
[snip]

Ah, I see an analogue of what you mean would be to evaluate pi using
some infinite series. If one knows that the given formulation of
the series for pi converges, then one can, depending on the quality
of convergence, more or less fast get a sufficient approximation
of what one want.

Now, in the case of computation of a series, the partial sum
that one computes at each time is mathematically correct (exact).
But in the present case, you question the validity of the result
of computation of any intitial segment of a given infinite string (because that's a finite string), don't you? And how do you know
that doing the analogue of the partial sums in the series
computation, here the computation of the complexity on initial
segments of the infinite string, is ok? You have to prove the
convergence of the process, just like you have to know the
convergence in the series computation. How could you do that?
If what is given is some unknown arbitrary random bit sequence,
I don't think you could do that at all.

That you refuse/fail to give a reference to a book or well-known
journal dealing with the finite vs. infinite string issue
clearly demonstrates that the issue has at least not been dealt
with todate seriously in the scientific field (for whatever reason,
including it could be a non-issue).

Finally, let me once again point out how textbooks define the
Kolmogorov complexity: For example, a fairly well-known textbook,
T. M. Cover, J. A. Tomas, Elements of Information Theory, 2nd ed.,
Wiley, 2006, on p.466 has a section on Kolmogorov complexity. It
begins with the sentence "Let x be a finite-length binary string and
let U be a universal computer". If the authors of such textbooks
are not all brain-damaged, it could be well expected that a few
would at least shortly mention the problematic nature of the
definition on finite strings. But since that is in fact not the
case and on the other hand you fail to give any literature
'explicitly' dealing with the issue you claimed, I must say that
this clearly means ample evidence to mistrust you claim as such.

M. K. Shen
.

Relevant Pages

  • Re: Review of Mueckenheims book.
    ... ....2222, they are actually infinitely distant elements of a sequence, ... smallest positive number, on the infinite scale. ... That's the ordering used by Cantor to prove their countability. ... If a set S is countable, then there is a total order < of S such that ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... I have always allowed that sequences can be countably infinite, ... like the sequence of standard naturals is. ... TO nor anyone else has produced any axiom system in which it can be ... at several removes from pure mathematics, ...
    (sci.math)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: Multiple infinities - one more look
    ... continued for lager length of digit sequences without limit. ... infinite digit sequences... ... so the resulting reals have an order. ... (i.e. having a finite program to output their digits in sequence). ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... distances that make it a curve instead of a straight line, ... In the above sequence, n is a (strictly ... the diagonal is the "infinite case" of the staircases. ... closer to 2*pi as n -> oo. ...
    (sci.math)
Loading