Anyway, one can certainly 'require' (if that's not necessary, then
all the better), as I said, that the person choosing the 'reference'
machine to be 'neutral', i.e. not employing any special knowledge,
neither of "Lena", nor of any other special string, to bias his
choice, pretty much like what one requires of a judge in court
or in a football play. Under this condition, there evidently cannot
be any bias favouring "Lena" when the 'reference' machine is run
and hence your previous critique on the use of finite strings, which
was argued with "Lena" in view, no longer applies in my humble
understanding.

Perhaps you would still say that the 'reference' machine chosen
would favour some 'unknown' particular string. But that would mean
in my view that the entire idea of KC was unfair 'in principle'
(is there any literature over that topic?) and I would think
that it is unlikely that by disregarding finiteness and requiring
instead infiniteness that 'inherent' defect would disappear.

Mok-Kong Shen wrote:

Anyway, one can certainly 'require' (if that's not necessary, then
all the better), as I said, that the person choosing the 'reference'
machine to be 'neutral', i.e. not employing any special knowledge,
neither of "Lena", nor of any other special string, to bias his
choice, pretty much like what one requires of a judge in court
or in a football play. Under this condition, there evidently cannot
be any bias favouring "Lena" when the 'reference' machine is run
and hence your previous critique on the use of finite strings, which
was argued with "Lena" in view, no longer applies in my humble
understanding.

No, and no again. There *is* no such requirement, and I wonder how you
read that into the definition. Once and for all. "Lena" is *not* a bias.
Any type of bias in favor for a finite string does simply not matter.

Mok-Kong Shen wrote:

Perhaps you would still say that the 'reference' machine chosen
would favour some 'unknown' particular string. But that would mean
in my view that the entire idea of KC was unfair 'in principle'
(is there any literature over that topic?) and I would think
that it is unlikely that by disregarding finiteness and requiring
instead infiniteness that 'inherent' defect would disappear.

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.

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*.

The reason for that is that a Turing machine has an internal state
machine with a *finite* number of states.

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?

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

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?

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

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).

From all what I have read, I don't have the impression that KC is
intended (or, equivalently, can be) applied to 'real world' problems
in the sense that given a string one 'actually' switches on a PC and
obtains a concrete number.

(In contrast, Shannon's entropy can
be computed for real world problems, if one has a model that is
or is assumed to be correct.) KC is thus merely for theoretical
argumentations. For, I would think at least, that the expression
min { | P | ..... } would give inherent 'practical' problems when
a 'real' computation is done, because it demands one's finding
'all' possible programs P that corresponds to the given string x
and take the minimum of their lengths. However, having successfully
written a finite number of such programs, one evidently couldn't
yet 'practically' (nor even theoretically in my view) exclude the
possibility that there 'may' exist other programs that are shorter.
But 'conceptually' it is clear that there must exist a minimum
value and it is this that in my understanding gives the definition
of KC its proper sense.

In the previous post I have pointed out the 'inherent' difficulties
of applying the definition of KC to an arbitrary infinite string.

Despite the above mentioned fact that KC is sort of gedanken-
experiment and never actually evaluated on a PC, these difficulties
would render the concept as such questionable. For a gedanken-
experiment must be such that it is 'reasonably' doable (have

similarity to one's procedures in real world experiments) at least
in one's thought and cause no 'essential' problems in the imagined
world. On the other hand, I have, for lack of knowledge, till now
not been able to counter Richter's critique on the application of
the concept of KC on finite strings (even though all textbooks I

have seen define KC on finite strings, some explicity, others
apparently implicitly). I believe that I have now found that his
issue is highly probably a non-issue. Let me argue in the following:

Richter uses "Lena compress" to support his claim that KC makes
little sense for finite strings.

As far as I understand, he
means that, if the Turing machine's state is 'purposedly' set to
suit "Lena", then the string of "Lena" would have an extremely
low computed complexity value and that's evidently not fair for
the other strings. Reading however the book "Introduction to
Kolmogorov Complexity" by Li and Vitanyi, I found that the
scientists in the field have apparently already taken care of
such problems through introducing a reference universal Turing
machine. As said, my knowledge is very humble. So I would like
to quote something from that book (p.97-9 and ask you to judge
whether this is indeed the case. (I have used f for the Greek
letter phi in the following three paragraphs taken from the book.)

Theorem 2.1.1. There is a universal partial recursive function
f_0 for the class of partial recursive functions to compute x
given y. Formally this says that
C_f_0( x | y ) <= C_f ( x | y ) + c_f for all partial recursive
functions f and all x and y, where c_f is a constant dependent
on f but not on x or y.

The key point is not that the universal description method
does necessarily give the shortest description in each case,
but that no other description method can improve on it
infinitely often.

Definition 2.1.2 Fix a universal f_0 and dispense with the
subsript by defining the conditional Kolmogorov complexity
C(.|.) by C(x|y) = C_f_0(x|y). This particular f_0 is called
the reference function for C. We also fix a particular Turing
machine U that computes f_0 and call U the reference machine.
The unconditional Kolmogorov complexity C(.) is defined by
C(x) = C(x|epsilon).

Now, while Richter's argument is based on a special machine T that
has a special state favouring "Lena", this is by definition not
the case with the reference machine U above. Therefore I think
that Richter's claim that KC makes little sense for finite strings
is apparently invalid.

Mok-Kong Shen wrote:

From all what I have read, I don't have the impression that KC is
intended (or, equivalently, can be) applied to 'real world' problems
in the sense that given a string one 'actually' switches on a PC and
obtains a concrete number.

I think paq's development over to zpaq is a good example of how it can
"materialize" in reality. Matt defined an "instruction set" which
controls the context-selection mechanisms of the paq-NNs. With that you
have the possibility of actually searching through all context-spaces
for the "program" with the shortest output.
It's not completly free, as the "machine", the interpreter still has
fixed size, but you can select the optimal parameter-set for the given
fixed length "machine".
I think one can relate it to LZ, which is a fixed size "machine", who's
"instruction set" are length/offset pairs, you may search for the
optimal parameter-set giving the smallest output.
Even though I think not much people think of LZ that way (as a
"machine" with an "instruction set"). I believe Matt was pretty much
inspired by KC when he made the step towards zpaq.

Despite the above mentioned fact that KC is sort of gedanken-
experiment and never actually evaluated on a PC, these difficulties
would render the concept as such questionable. For a gedanken-
experiment must be such that it is 'reasonably' doable (have

KC isn't reasonably doable. Worm-holes aren't reasonably doable, still
it doesn't stop a serious physicist to make the gedankenspiel. Strings
probably aren't reasonably provable by real-world devices, still they
are part of serious physical theories with real-world implications.

similarity to one's procedures in real world experiments) at least
in one's thought and cause no 'essential' problems in the imagined
world. On the other hand, I have, for lack of knowledge, till now
not been able to counter Richter's critique on the application of
the concept of KC on finite strings (even though all textbooks I

Thomas just thinks it's not very interesting to think about machine
dependent KC. It contradicts sort of the universality of KC. And as he
said, if you look to eliminate the machine dependency, you marginalize
it (you don't want to consider all machines, because then you have to
look infinite time on infinite machines for a finite string, that's even
worst). You can marginalize it by setting finite algorithm size vs.
infinite string size.
Maybe you have to understand that the instruction set of a turing
machine is free to be defined. If you focus on finite strings you sort
of fall into a local minimum, you start to pay attention to the machine,
which you shouldn't as you're looking or thinking about universal KC.
Well and Thomas didn't say you can't do it, it's forbidden, or pervert.
He just stated as his personal opinion, that it's not very "interesting"
in comparison.

I hope I got this right.

have seen define KC on finite strings, some explicity, others
apparently implicitly). I believe that I have now found that his
issue is highly probably a non-issue. Let me argue in the following:

Richter uses "Lena compress" to support his claim that KC makes
little sense for finite strings.

Yes, his machine got 1 instruction, is still universally usable for any
other string than "lena", but sucks.

Now, while Richter's argument is based on a special machine T that
has a special state favouring "Lena", this is by definition not
the case with the reference machine U above. Therefore I think
that Richter's claim that KC makes little sense for finite strings
is apparently invalid.

Uhm, as I understood Thomas, his instruction set is the crucial point,
not the state (you can replace "lena" by any finite string, that's
really boring to define a special instruction set for every finite
string, right?).

I hope I got this right. :)

But for finite strings, KC, in using a 'reference' 'universal'
machine, does attempt to achieve machine independence, at least
in some sense, as far as I can understand from the three paragraphs
I quoted from the book of Li and Vitani.

I can, for example, proof that the divergence rate of the input "Pi"
is non-existent. It doesn't diverge. I don't come to this conclusion
by feeding an actual machine with the digits of Pi. I come to this
conclusions by thinking about how I could possibly build such a
machine, and then see that it takes only finitely many algorithmic
steps to compute any digit of Pi, no matter how far to the left this
digit is.

But how do you do with an 'arbitrarily' given infinite string (you
have only the data, no other informations concerning the string)?
Simply say 'Sorry, forget KC!', or what?

The *computation* means nothing. The concept means all. In the same
sense, *what does the computation of Pi* tells you? What is the
meaning of the 100th digit of Pi? This is pointless. The point is that
Pi is a useful tool in trigonometry. *That* is the useful property of
Pi. Not its precise value.

I am quite sure that to date nobody has seriously tried to employed
a PC to actually (concretely) compute KC. That 'computation' is
however evident in the sense of a gedanken-experiment. In fact,
the definition as given in all textbooks I have seen plainly
implies a concept of 'computation', e.g. in one book: "length of
the program P that generates x".

But how can you know it converges? You can definitely not do that by
*observation*. It requires a proof *on* the series, not an observation
*of* the series. Quite the same with KC.

As I said above, in the case of evaluating a series I have to know
(a proof of) the convergence. That however is an 'inherent' problem
with (in particular 'arbitrarily' given) infinite strings for KC.
That's why I continue to doubt the sense of application of KC to
infinite strings.

Yea, right, and then what? The upper bound for a given machine is the
size of the string plus a constant. The upper bound for it if I can
choose the machine is one. (As already demonstrated).

That's why I said in previous posts that one should 'require' that
the reference universal machine should be chosen in a 'neutral'
way, i.e. not purposedly (consciously) favouring any particular
string.

You might counter that, even though one picks a machine
randomly, one might by pure chance choose a machine favouring e.g.
"Lena". I can't exclude that with my humble knowledge without
persuing further study on the topic of KC. However, that chance,
I suppose, could be regarded as negligible, much like the non-zero
chance of my being hit by a bolt that happens to fall down from
an airplane flying over me.

So what? It neither tells you anything interesting about the machine
and the string. If I take a specific string, and vary it over all
possible values of Turing machines, I get all natural numbers as upper
bounds. So why is that a valuable information?

I would think that, if one chooses randomly a reference machine,
one may get at least some useful informations. In fact, statistical
quality control is based on that idea, if I don't err.

As I said, this seems to be something that one could deal with
using something maybe simpler in theory and more comfortable
in practice. (I am not sure, but off hand I would think of
Shannon's entropy.)

There is no such statement for finite strings - the example only makes
sense for infinite (potentially infinite) inputs.

If there were no problems of convergence as I argued, I might have
agreed with you on your valuation of applications of KC to infinite
strings.

Anyhow, KC can *clearly* tell this series apart from an iid random
source. This is not so easy at all in the Shannon settings. As said, I
believe its an open problem there.

I am interested in the applications of KC and would like to ask
you to provide a literature reference with respect to Pi above.

Thomas Richter wrote:

Mok-Kong Shen wrote:

I hope I got this right. :)

Just to avoid misunderstanding: This sentence you quoted above,
appearing as though it stemmed from a post of mine, is not from me
but has been extracted by you from a post of Fröhling.

But for finite strings, KC, in using a 'reference' 'universal'
machine, does attempt to achieve machine independence, at least
in some sense, as far as I can understand from the three paragraphs
I quoted from the book of Li and Vitani.

*NO*. "Universality" does not disallow "lena compress". Such a machine
is still "universal".

Which part of "universal" don't you understand?

Maybe I even don't understand 'universal' at all. But, as said in a
previous post, I don't 'need' to know how good or poor I understand
'universal' in the present context.

I think paq's development over to zpaq is a good example of how it
can "materialize" in reality. Matt defined an "instruction set" which
controls the context-selection mechanisms of the paq-NNs. With that
you have the possibility of actually searching through all
context-spaces for the "program" with the shortest output.
It's not completly free, as the "machine", the interpreter still has
fixed size, but you can select the optimal parameter-set for the given
fixed length "machine".
I think one can relate it to LZ, which is a fixed size "machine",
who's "instruction set" are length/offset pairs, you may search for
the optimal parameter-set giving the smallest output.
Even though I think not much people think of LZ that way (as a
"machine" with an "instruction set"). I believe Matt was pretty much
inspired by KC when he made the step towards zpaq.

Sounds nice, but I somehow doubt that this algorithm comes up with the
*smallest possible* program required to regenerate the output. Because
simply if it would, one could take the size of this program and would
then have KC(input). However, KC is provably incomputable, so such a
program does not exist.

Sounds nice, but I somehow doubt that this algorithm comes up with the
*smallest possible* program required to regenerate the output. Because
simply if it would, one could take the size of this program and would
then have KC(input). However, KC is provably incomputable, so such a
program does not exist.

In practical applications, one can at best consider approximations or
upper bounds of KC(s).

Despite the above mentioned fact that KC is sort of gedanken-
experiment and never actually evaluated on a PC, these difficulties
would render the concept as such questionable. For a gedanken-
experiment must be such that it is 'reasonably' doable (have

KC isn't reasonably doable. Worm-holes aren't reasonably doable,
still it doesn't stop a serious physicist to make the gedankenspiel.
Strings probably aren't reasonably provable by real-world devices,
still they are part of serious physical theories with real-world
implications.

Exactly. It is a theoretical concept, a tool, and by thinking about it
you can come up with reasonable results that are of interest of the
field, but you shouldn't expect to find a program that provides you with
the KC of a given string. That is, provably, impossible.

similarity to one's procedures in real world experiments) at least
in one's thought and cause no 'essential' problems in the imagined
world. On the other hand, I have, for lack of knowledge, till now
not been able to counter Richter's critique on the application of
the concept of KC on finite strings (even though all textbooks I

Thomas just thinks it's not very interesting to think about machine
dependent KC. It contradicts sort of the universality of KC. And as he
said, if you look to eliminate the machine dependency, you marginalize
it (you don't want to consider all machines, because then you have to
look infinite time on infinite machines for a finite string, that's
even worst). You can marginalize it by setting finite algorithm size
vs. infinite string size.
Maybe you have to understand that the instruction set of a turing
machine is free to be defined. If you focus on finite strings you sort
of fall into a local minimum, you start to pay attention to the
machine, which you shouldn't as you're looking or thinking about
universal KC.
Well and Thomas didn't say you can't do it, it's forbidden, or
pervert. He just stated as his personal opinion, that it's not very
"interesting" in comparison.

I hope I got this right. :)

I would say so. I'm saying it is not very interesting because you cannot
derive anything interesting about such a finite string. Every finite
string is "special", and you can design machines that are good at
generating such special strings. This "loop hole" is closed by taking
the limit and applying the idea to longer and longer strings, and the
reason why this loop hole is closed is that the Turing machine can only
have a *finite* internal state machine. Thus, "if the input is
considerably longer than the internal state machine", your machine can
no longer be tuned to the specific input.

Thomas Richter ha scritto:

Sounds nice, but I somehow doubt that this algorithm comes up with the
*smallest possible* program required to regenerate the output. Because
simply if it would, one could take the size of this program and would
then have KC(input). However, KC is provably incomputable, so such a
program does not exist.

In practical applications, one can at best consider approximations or
upper bounds of KC(s).

Yes but this is an absolutely practical application where the KC concept
is used successfully.

I would say so. I'm saying it is not very interesting because you
cannot derive anything interesting about such a finite string. Every
finite string is "special", and you can design machines that are good
at generating such special strings. This "loop hole" is closed by
taking the limit and applying the idea to longer and longer strings,
and the reason why this loop hole is closed is that the Turing machine
can only have a *finite* internal state machine. Thus, "if the input
is considerably longer than the internal state machine", your machine
can no longer be tuned to the specific input.

I think is too simple to define the problem related to the finitary of
the string in exam. Also infinite strings are special for example an
infinite sequence of "...01010101..." can be special becouse is possible
to construct an universal machine that output such string for an
arbitrary input .