Re: What is complexity?

In article <xY2ff.21723$w85.17888@trnddc02>,
R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
>
>It is true that when string length gets long, the effect of the constant
>becomes less significant. We are, however, in the realm of finite strings
>when describing molecules, and no matter what length of string you pick, I
>can find you a machine for which the description on your Rule 110 machine is
>incredibly long.

And my conjecture to this, is that those machines, when described in
machines described on them... Hmmm. That sentence would have been awful.
Better to rephrase:

And my conjecture to this is:
Consider a reference machine x.
On x one implements other reference machines, Y={y1,y2,...}.
One then describes x on all y.
A measure for the complexity of x is: One averages the complexity of x
described an all y weighted by 2^-l(y), the complexity of y in x,

The conjecture is then that those machines with very large c you talk
about, will also have large complexity as described by double
selfdescriptions like in said measure.


In other words: The reference machines that are complex are less
probable, and thus do not affect the measure of complexity. Thus,
there is a real absolute approximable objective measure of complexity.


>How to drive up Kolmogorov complexity? No noise is needed. You are probably
>familiar with self-delimiting codes? For example, you can code 00 for 0, 11
>for 1, and either 10 or 01 for end of string. This can be a way to delimit
>the simulated state table from a program when feeding the program tape into
>a Universal Turing Machine. Well, you could also use 000 for 0, 111 for 1,
>and 01 or 10 for end of string. Or you could use a chain of N zeros for 0, N
>ones for 1, and 01 or 10 for end of string. N can be as large as desired,
>and the result is a rediculously inefficient UTM.

That is not a valid thing to do with universal machines. That removes
their universality. It must be possible for the reference machine to
somehow access individual bits on the input tape. Your padding of bits
thus removes universality.


>We can also make the description of a UTM arbitrarily large by loading its
>state table with pre-defined, arbitrarily long constants that output on
>certain programs. This makes the Kolmogorov complexity of those particular
>programs very small, by the way.

Or even simpler:
The reference machine require a particular string on the beginning of the tape.

But all these 2 valid examples has in common, is that they add
complexity to the machine in order to add complexity to the programs,
and thus makes them irrelevant for the measuring of absolute
complexity.

You need to find simple reference machines that require complex programs.

And that is an interesting and difficult problem.

Kim0

.