 |
|
| Science Forum Index » Compression Forum » Entropy... |
|
Page 5 of 6 Goto page Previous 1, 2, 3, 4, 5, 6 Next |
|
| Author |
Message |
| Mok-Kong Shen... |
 Posted: Wed Sep 16, 2009 2:17 pm |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:07cadabbe5]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.
[/quote:07cadabbe5]
I regret that I continue to have difficulties in understanding your
point. Please have patience with me, whose knowledge is very humble.
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.
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Thu Sep 17, 2009 1:37 pm |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:f4228dc728]
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.
[/quote:f4228dc728]
Here is a precise formulation: To have a well-defined Kolmogorov
complexity, you need to consider the limit case of "input string size
goes to infinity".
[quote:f4228dc728]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.
[/quote:f4228dc728]
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.
[quote:f4228dc728]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.
[/quote:f4228dc728]
Now, tell me why I should spend more time on this? You keep telling me
that you don't seem to understand the written material, but then ask me
to do work for you? Yet, you tell me that you don't understand what I
present, so even if I come up with a result, what would be the benefit?
Ok, here is a deal: First, try to understand the reference I posted.
Then we continue discussion, ok?
So long,
Thomas |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Thu Sep 17, 2009 3:08 pm |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:9cdeb53adb]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][/quote:9cdeb53adb]
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 |
|
|
| Back to top |
|
|
|
| Niels Fröhling... |
| Posted: Thu Sep 17, 2009 5:04 pm |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:b548dfaa91]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).
[/quote:b548dfaa91]
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.
Ciao
Niels |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Fri Sep 18, 2009 3:27 am |
|
|
|
Guest
|
Niels Fröhling wrote:
[quote:eb4fc3ff71]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.
[/quote:eb4fc3ff71]
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.
Thanks.
M. K. Shen |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Sep 18, 2009 6:59 am |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:28d1278755]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.
[/quote:28d1278755]
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.
So long,
Thomas |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Fri Sep 18, 2009 9:14 am |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:7ffdbe0d85]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.
[/quote:7ffdbe0d85]
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.
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Sep 18, 2009 9:57 am |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:cc74a535fe]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.
[/quote:cc74a535fe]
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.
[quote:cc74a535fe]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?
[/quote:cc74a535fe]
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.
[quote:cc74a535fe](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.
[/quote:cc74a535fe]
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.
So long,
Thomas |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Fri Sep 18, 2009 11:05 am |
|
|
|
Guest
|
Thomas Richter schrieb:
[quote:dc020d1f03]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.
[/quote:dc020d1f03]
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.
(Note that, while describing/classifying all finite strings of
a certain length is apparently not a simple job, doing this for
infinite strings would be evidently much harder. So one would
naturally be able to assert in general much less of theoretically
interesting stuffs in the case of infiniteness than in cases of
finiteness.)
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Sep 18, 2009 11:11 am |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:9d76039fa1]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.
[/quote:9d76039fa1]
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.
So long,
Thomas |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Sep 18, 2009 11:36 am |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:ef29abbe87]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.
[/quote:ef29abbe87]
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.
So long,
Thomas |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Fri Sep 18, 2009 11:43 am |
|
|
|
Guest
|
Thomas Richter schrieb:
[quote:f46d99a27a]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.
[/quote:f46d99a27a]
I wanted only to say that in 'any' case one can obtain a 'neutral'
'reference' machine, that is one that doesn't favour any 'known'
string, like "Lena". If there needs no requirement to ensure that
neutrality, then all the better!!! Otherwise, we make that to be
a requirement in the choice of the 'reference' machine, similar
to the case of a judge, who has to swear to be neutral. If you
still mean that no machine could be chosen to be neutral, then
please re-read my previous post and in particular kindly give a
literature reference showing that KC is indeed in principle unfair.
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Fri Sep 18, 2009 11:56 am |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:7a55d8ace7]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.
[/quote:7a55d8ace7]
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?
But anyway, that c affect all strings alike. Hence in my understanding
the c doesn't (much) matter in case of finite strings.
[quote:7a55d8ace7]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*.
[/quote:7a55d8ace7]
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.
[quote:7a55d8ace7]The reason for that is that a Turing machine has an internal state
machine with a *finite* number of states.
[/quote:7a55d8ace7]
Thanks,
M. K. Shen
P.S. There might be some little delay in my responding you next time. |
|
|
| Back to top |
|
|
|
| Thomas Richter... |
| Posted: Fri Sep 18, 2009 2:19 pm |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote:665c3e2c95]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?
[/quote:665c3e2c95]
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.
[quote:665c3e2c95]So why does
the 'unfairness' disappear by going from finiteness to infinity?
[/quote:665c3e2c95]
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.
[quote:665c3e2c95]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?
[/quote:665c3e2c95]
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).
[quote:665c3e2c95]And I also like to recall here the difficulties of dealing with
infinite strings I stated in a previous post.
[/quote:665c3e2c95]
You never deal with "actual infinities", but you check what happens if
you send the size to infinity.
So long,
Thomas |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Sat Sep 19, 2009 2:51 am |
|
|
|
Guest
|
Thomas Richter wrote:
[quote:9a72ee94d7]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).
[/quote:9a72ee94d7]
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 |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 04, 2009 1:26 pm
|
|