Well, we now enter the realm of "existence or not". Basically,
Kolmogorov complexity exists in the same sense dragons exist. As an
abstract concept. You cannot potentially measure it, or design an
algorithm for it, you can only use it as a mathematical abstractum to
prove theorems about it.

Thomas Richter wrote:

You can define the Kolmogorov complexity on finite sequences *given*
that you have a specific Turing machine. It is the size of the
shortest program *on this machine* that regenerates the message.

The problem is that this definition is always relative to the machine,
*unlike* - and this is the important part - you define it on infinite
strings. *Then* the machine doesn't matter anymore.

The problem with the finite-sized input - and why it makes little
sense there - is simply that for every finite sized message you can
define a Turing machine which generates this message simply by a
one-step program: Put the message into the state-apparatus of the
Turing machine.
(Aka: The "Lena compress" version of Kolmogorov complexity. True,
working, but useless).

Independence from the machine on infinite messages:

This is simply because any Turing machine can emulate any other Turing
machine by a finite-sized program, and the contribution of a
finite-sized program to an infinite string doesn't matter.

I am ignorant of the deep theory of Kolmogorov. Looking superficially
however at the definition given in a book I just got from a library:

T denotes a given Turing machine that generates a binary
sequence x_n of length n. Let P(T) be the program with
which the Universal Turing machine simulates T. Then we
define the Kolmogorov complexity of a sequence x_n by

k(x_n) = min { |P(T)| | T generates x_n }

I have a layman's question: Wouldn't in the "Lena compress" case,
with the message being put into the state-apparatus of T, |P(T)|
be of the order of the length of the message?

From another source, I find the definition:

k(x_n) = min { | P | | U(P) = x_n }

But here U is a universal Turing machine, not the special
Turing machine T with its state purposedly set to suit
"Lena compress".

Either way, it seems therefore highly
likely that you erred with your claim that finite-sized
input makes little sense for Kolmogorov complexity.

Mok-Kong Shen wrote:

From another source, I find the definition:

k(x_n) = min { | P | | U(P) = x_n }

But here U is a universal Turing machine, not the special
Turing machine T with its state purposedly set to suit
"Lena compress".

You seem confused. There is no "the universal turing machine", there are
many. In fact, the machine you're typing in is such a machine. A machine
that has a special instruction to generate "lena" could also very well
be a universal turing machine. Thus, the above definition is of course
*still* machine dependent, and not "less" dependent.

Thomas Richter wrote:
Mok-Kong Shen wrote:

From another source, I find the definition:

k(x_n) = min { | P | | U(P) = x_n }

But here U is a universal Turing machine, not the special
Turing machine T with its state purposedly set to suit
"Lena compress".

You seem confused. There is no "the universal turing machine", there are
many. In fact, the machine you're typing in is such a machine. A machine
that has a special instruction to generate "lena" could also very well
be a universal turing machine. Thus, the above definition is of course
*still* machine dependent, and not "less" dependent.

I don't yet understand. Please kindly explain how a machine with
its state specially set to suit "Lena Compress" could nonetheless
be "universal".

Mok-Kong Shen wrote:
Thomas Richter wrote:
Mok-Kong Shen wrote:

From another source, I find the definition:

k(x_n) = min { | P | | U(P) = x_n }

But here U is a universal Turing machine, not the special
Turing machine T with its state purposedly set to suit
"Lena compress".

You seem confused. There is no "the universal turing machine", there are
many. In fact, the machine you're typing in is such a machine. A machine
that has a special instruction to generate "lena" could also very well
be a universal turing machine. Thus, the above definition is of course
*still* machine dependent, and not "less" dependent.

I don't yet understand. Please kindly explain how a machine with
its state specially set to suit "Lena Compress" could nonetheless
be "universal".

"Universal" means nothing more than "being able to emulate any other
Turing machine" by a suitable program. Here is a receipt how to build a
universal "lena" Turing machine U2 from a given "universal" Turing
machine U1:

Consider that U1 has the command set c1...cn. Then, define the
instruction set of U2 d1...d(n+1):
The instruction dk has the encoding 00 ck for k<=n. The instruction
d(n+1) has the encoding 01.

The Turing machine U2 then has an additional internal state that
"decodes the pre-word".

The new instruction 01 then writes Lena to the tape.

U2 is clearly universal as it can do everything U1 can, just with longer
"instructions".

OK. Let me aks your favour to do one thing: In all the books
I have looked at, Komolgorov complexity is defined for finite
strings and no where is any inappropriateness of finite
input mentioned.

So your claim that for finite input Komolgorov
complexity makes little sense must be something new in the
field. Could you please give a reference to a book or a journal
that supports your claim, or is it a yet unpublished scientific
result of your own?

Mok-Kong Shen wrote:

OK. Let me aks your favour to do one thing: In all the books
I have looked at, Komolgorov complexity is defined for finite
strings and no where is any inappropriateness of finite
input mentioned.

None of the above stuff is new, it's just conclusions from the obvious.
While I generally don't appreciate Wikipedia for things like this, just
go there. You'll find there exactly the same elementary result I stated
above, namely that the complexity is language dependent, and that for
any two languages the complexity of a given string differs by a constant
(depending on the languages). The specific "lena" example is this
invariance theorem, just turned around. By making the machine pretty
smart, one can make the constant c as large as the language, and then
the complexity of *a specific* string very short.

For any *finite* string the complexity isn't a function of the input
string itself. However, if you approach the limit of longer and longer
strings, this constant becomes irrelevant, but only then.

There is no big science behind that, really.

So your claim that for finite input Komolgorov
complexity makes little sense must be something new in the
field. Could you please give a reference to a book or a journal
that supports your claim, or is it a yet unpublished scientific
result of your own?

Definitely not.

For example, go into Ray Solomonoff's work "A Preliminary Report on a
General Theory of Inductive Inference," Report V-131, Zator Co.,
Cambridge, Ma. Feb 4, 1960." cited there. Go to section 4, and read it.
It states exactly what I say - the constant in the above equation
becomes irrelevant for long strings, and only then - and *then* the
definition is machine-independent. Otherwise, it depends on the machine,
clearly. That I can set the complexity to one for a *specific* message
is a trivial corollary from the invariance theorem. Specific means here:

For any message A there exists a Turing machine U such that C_U(A) = 1.

quite contrary to:

There is a Turing machine U such that for any message A C_U(A) = 1.

which is a different statement, and clearly wrong. As I might have said
already, it depends on the position of the quantors. As the description
of a Turing machine is by definition finite, the second statement is
clearly wrong since I can always set the message just considerably
longer than the description of the machine to be on the safe side. This
does not hold for the first statement.

Really, it's just about reading the statement carefully.

1. In the Wiki page there is no mention of "infinite string". This,
together with the use of computer programs (in the common style) to
illustrate, seems to indicate that there the term "string" is employed
in the sense 'normally' understood, i.e. a finite string.

2. You seemed to mean that Sec. 4 of the the paper of Solomonoff
(referenced by Wiki) would easily clear up the issue of "infinite
string" vs. "finite string". However, firstly, I don't see there
the word "infinite" and secondly, I regret that that paper is at
a too high level for me to understand.

3. I spent today several hours in two libraries to search for a
book where "infinite string" is mentioned in connection with
Kolmogorov complexity but unfortunately failed. On the other hand,
I found the word "finite" being explicitly mentioned in several
places. Below are a few examples:

(a) Kolmogorov [41], and independently Chaitin [18], established
a mathematical notation of the complexity of finite sequences.
([41] refers to a paper of Kolmogorov of 1965.)

(b) The Kolmogorov complexity of a finite object x is the length
of the shortest effective binary description of x.

(c) Apart from showing that complexity is an attribute of the finite
object alone, the Invariance Theorem has also another most important
consequence: it gives an upper bound on the complexity.

4. In the case of a finite string, each P of the expression | P |
that enters into min { .... } of the formula for complexity is,
if I don't err, a program that 'successfully' ran on the Turing
machine with respect to that given string. That is, the machine
finishes its work and halts. Now, in the case of an infinite string,
the machine either must continue to work, because there always
remain symbols to be processed, and hence not halt, or stops before
everything has been processed, which would mean that that particular
P is not correct for the given string and hence the corresponding
| P | could not be used in min { ..... }. So, either way, I don't
see how one could deal with infinite strings at all similar to the
way one does with finite strings, when min { ......} is to be
evaluated in the formula for complexity.

5. In view of the above I would like to ask your favour to give a
reference to a book or a well-known journal where the use of infinite
strings in Kolmogorov Complexity is 'explicit' and thus could convince
laymen like me, who may not even be able to capture a small fraction
of the deep theoretical materials contained therein.

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

Mok-Kong Shen wrote:

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

There is quite some material out there which proves that computing KC
on any *finite* sentence is not possible (including Kolmogorov and
Solomonoff themself BTW). So it makes no difference for the
"incomputability" if you take finite or infinite inputs. As you take
infinite time to (try to) compute KC, it's not determinable if you have
final KC or not.
Mind that it's about exact KC.
The moment you put restrictions (for the sake of handling a problem in
reality) onto the definition of KC (like: just run 2 years), you're
doing (computing) something else.

So of course it's possible to compute approximations, but in effect
because KC is formulated in such a free way (universal), we have real
problems to determine the (universal) quality of the approximation.
So you most often step back and for example search for an approximation
of some sort of KC which runs on a real machine, and you see we go more
and more away from the original KC, making any real world attempt by a
real "mechanic" or "electronic" machine sort of useless or doubtful in
respect to computing or measuring (universal) KC.

Just to promote the wiki-movement, here is another wiki ;^):
http://www.scholarpedia.org/article/Algorithmic_complexity

But you can use the KC formulation as a good guide to create or reflect
or muse about real world algorithms to tackle real world problems.

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:

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.

You still don't understand what 'universal' means. Look this up,
then check my post above how to construct a universal machine with
specific properties. There is no contraction of having a turing machine
that is both universal, but yet very efficient in generating a specific
output.

Thomas Richter wrote:
Mok-Kong Shen wrote:

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.

You still don't understand what 'universal' means. Look this up,
then check my post above how to construct a universal machine with
specific properties. There is no contraction of having a turing machine
that is both universal, but yet very efficient in generating a specific
output.

I suppose I don't need in this connection to exactly know whether
my 'personal' understanding of 'universal' is correct or not. It
might be wrong. But in the previous post answering Fröhling I was
simply relying on the apparently correct assumption that the authors
of the book I cited 'do' understand that term and hence have used
the word in the three paragraphs I cited correctly. There, U is a
'reference' 'universal' Turing machine chosen for the 'general'
purpose of computing KC (general for 'all' strings), hence it
couldn't have anything to do with "Lena" from the very beginning.

One can certainly at least without restriction of generality
require in the choice of a 'reference' machine that no specific
knowledge/data should be taken into consideration, can't one?

(I understand 'reference' in the sence of the 'previous' standard
metre located in the Bureau of Standardization in Paris, which
was a 'reference' for all length measurements (being sort of
neutral and independent). Is there anything logically wrong with
my thinking here? Please kindly point out, if any.

Mok-Kong Shen wrote:
Thomas Richter wrote:
Mok-Kong Shen wrote:

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.

You still don't understand what 'universal' means. Look this up,
then check my post above how to construct a universal machine with
specific properties. There is no contraction of having a turing machine
that is both universal, but yet very efficient in generating a specific
output.

I suppose I don't need in this connection to exactly know whether
my 'personal' understanding of 'universal' is correct or not. It
might be wrong. But in the previous post answering Fröhling I was
simply relying on the apparently correct assumption that the authors
of the book I cited 'do' understand that term and hence have used
the word in the three paragraphs I cited correctly. There, U is a
'reference' 'universal' Turing machine chosen for the 'general'
purpose of computing KC (general for 'all' strings), hence it
couldn't have anything to do with "Lena" from the very beginning.

That is not the case, and not a requirement. The machine really doesn't
matter, as long as it is complete enough to carry out any computation,
i.e. is able to compute anything any potential other machine can
compute. This is a *universal* machine. It is in so far a "reference" as
you need to compute KC relative to this reference, keeping in mind that
it depends on the reference. But you have a choice there.

The important fact about KC is *not* that it is independent of the
reference - which it isn't - but rather, that for *two* different
references, the KC only differs by a constant depending on the machines,
but not depending on the string the machines must generate. *This* is
where universality comes into play.

One can certainly at least without restriction of generality
require in the choice of a 'reference' machine that no specific
knowledge/data should be taken into consideration, can't one?

There is no need to *require* that. It is just not necessary. Any
machine dependence enters into the constant C by which KCs with respect
to different references will differ.

Anyhow, every Turing machine will have "special" strings it can
represent most efficiently, and in general, strings that belong to
"short programs" will differ, and depend on the machine. That is, every
machine has a set of "preferable (finite) strings" for which short
programs exist that generate those. That the "lena machine" has an
efficient mechanism to generate "lena" doesn't make this make "more
special" than a Turing machine that is very efficient at creating a
string consisting of 1000000 zeros. Both strings can be obtained by
universal machines.

(I understand 'reference' in the sence of the 'previous' standard
metre located in the Bureau of Standardization in Paris, which
was a 'reference' for all length measurements (being sort of
neutral and independent). Is there anything logically wrong with
my thinking here? Please kindly point out, if any.

The "meter" is a convention picked by pure chance and "historic
accident". There is no such thing as an "ISO Turing Machine" which you
use for measurement, and no such convention. There are *several*. The
important fact is that it doesn't really matter which reference you
pick. For two references, the KC will at most differ by a constant.

Why, for example, should we declare a Turing machine "using the x86
instruction set" (just to give it a name) *the* reference? Why not "the
6502 instruction set"? Programs for the former will in general be
shorter than programs for the latter, but nevertheless, if we grow the
size of the strings we want to create by the two machines (a x86 and a
6502), it won't matter since difference in size of the two programs will
at most differ by a constant and stay bounded. And that is simply
because a 6502 is powerful enough to emulate an x86 (at pretty low pace,
of course, but we don't care), and a x86 is surely powerful enough to
emulate a 6502. So *one bound* given for the difference of the KC
measured relative to 6502 and x86 is simply the size of the emulator
program for the corresponding other architecture.

"Lena compress" is in no way different from that, it is just a very
special "CPU" that has been explicitly designed to do one specific
purpose. Consider it as an x86 processor with a single extra instruction
that says "write lena to disk". And again, we have clear bounds to
estimate the KC with respect to this machine compared to the KC using
the "original x86". The bound is the size of a program generating lena
on an "original x86". Other than that, complexity wise both machines are
equally powerful.