Re: What is complexity?


R. Baldwin wrote:
> "Nic" <harrisondalen@xxxxxxxxxxx> wrote in message
> news:1132157494.206230.21130@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> >
> > R. Baldwin wrote:
> >> "Kim G. S. Øyhus" <kim@xxxxxxxxxxx> wrote in message
> >> news:dlcfa8$msm$2@xxxxxxxxxxxxxxxxxxxxx
> >> > In article <Waeef.7144$%t4.5615@trnddc07>,
> >> > R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
> >> >>"dkomo" <dkomo871@xxxxxxxxxxx> wrote in message
> >> >>news:P-6dnen1wa1TO-XeRVn-oQ@xxxxxxxxxxxxxx
> >> >>> R. Baldwin wrote:
> >> >>>>
> >> >>>> The longest description on what reference computer?
> >> >>>
> >> >>> It doesn't matter. The description is in ASCII, which would make its
> >> >>> length independent of what computer it was read or written on. If
> >> >>> the
> >> >>> description involved graphics, then it might be a PDF file, or the
> >> >>> ASCII
> >> >>> description might be compressed, but the length of these files would
> >> >>> still be relatively independent of the computer.
> >> >>
> >> >>It does indeed matter, whether or not it is in ASCII (which you hadn't
> >> >>mentioned before). Minimum description length depends on the reference
> >> >>computer, always. ASCII file compression is usually described with
> >> >>respect
> >> >>to essentially similar general purpose Von Neumann computers, so the
> >> >>choice
> >> >>of reference computer tends to be ignored- but it is an essential part
> >> >>of
> >> >>the problem.
> >> >
> >> > Why do a constant converging to zero matter?
> >> >
> >> > Are you not familiar with the proofs showing the irrelevance of the
> >> > reference computer? All they can do, is to change the description
> >> > length by a small constant, smaller that the complexity of the
> >> > computer. Considering that an universal computer can be done with the
> >> > rule No.110 cellular automata, and how simple this is, the small
> >> > constant will indeed be small.
> >>
> >> I am familiar with those proofs, and they don't exactly say that the
> >> reference computer is irrelevant at all. The reference computer is
> >> irrelevant for certain kinds of problems.
> >>
> >> The change in description length is not necessarily small, because the
> >> complexity of the computer may be large, and therefore the constant in
> >> the
> >> invariance theorem can be large. Arbitrarily large, in fact. The
> >> reference
> >> computer need not be one of the minimal ones described by Wolfram and
> >> others. It can be grossly inefficient.
> >>
> >> >
> >> >
> >> >>The pigeonhole principle tells us that only a handful of all possible
> >> >>strings are compressible on a given reference computer - but the number
> >> >>of
> >> >>possible reference computers is infinite.
> >> >
> >> > An infinite number of strings are compressible, not a handful.
> >>
> >> At least 99.9% of strings of length N cannot be compressed to more than
> >> N-10. There are fewer short strings than long ones. That means any given
> >> reference UTM that compresses some strings must make others longer.
> >>
> >> >
> >> >
> >> >>> Generative complexity is more applicable to mathematical systems than
> >> >>> physical ones. When the discussion switched to fractals and the
> >> >>> number
> >> >>> pi, then we were talking generative complexity. And, AFAIK,
> >> >>> generative
> >> >>> complexity is the same as Chaitin-Kolmogorov complexity.
> >> >>>
> >> >>
> >> >>The definition you gave is not a very good description of
> >> >>Chaitin-Kolmogorov
> >> >>complexity. A system might not be computable, in which case you can't
> >> >>generate it with a Universal Turing Machine (UTM) and can't define it
> >> >>in
> >> >>terms of Kolmogorov complexity. But if a system is computable, it can
> >> >>be
> >> >>computed with a UTM and desribed by a minimum length descriptor against
> >> >>a
> >> >>reference UTM. The length of the descriptor depends on the choice of
> >> >>UTM.
> >> >>By
> >> >>post hoc selection of UTM, the descriptor for a given string can be as
> >> >>short
> >> >>as 1 bit or arbitrarily long.
> >> >
> >> > Do you really have problem with uncomputable systems, or are you just
> >> > doing som irrelevant unnecessary nitpicking? Many uncomputable systems
> >> > are the limit of computable systems.
> >> >
> >>
> >> I have no problem with uncomputable systems, and haven't a clue why you
> >> might think so. I was taking issue with a poor description of Kolmogorov
> >> Complexity.
> >
> > Are you saying that the 99.9% of arrangements of atoms in space that
> > appear to us as just mush, really *are* just mush? Or are you saying
> > that is relative to what kind of creature one happens to be?
> >
>
> No. I'm saying it is a mistake to assume that strings representing nature
> have inherent complexity, because nature has no preferred reference against
> which to measure that complexity. Let alone that there are many ways to map
> the same natural object into a string.
>
> > Perhaps the question in this thread is more about patternedness than
> > complexity. I'm asking because I really don't know. If patterndness
> > is not absolute, then what is it that science actually does?
> >
> >
>
> Patterns are not absolute. I'll give you an example. Say we have a cable
> with 16 wires. We'll put 5 volts on a wire to represent "1" and "0" volts to
> represent 0 just like our conventional, old fashioned digital circuits. We
> encode a 16-bit word onto the wires. We designate the first wire as the
> least significant bit and the 16th wire as the most significant bit. We put
> the following pattern onto the wires: 1111000011110000. This is a nice
> regular pattern representing F0F0 hexadecimal or 61680 decimal in the most
> human mathematical notation. Now at the other end of the cable, we twist the
> wires around and lose track of which bit is which. We measure the data as
> 1000110101001110. This is an irregular pattern representing 8D4E hexadecimal
> or 36174 decimal. Did we change the voltages in the wires? No. We just
> looked at them differently, and the data showed a different pattern.
>
> This is not to say that we can't study patterns, or that they have no value.
> But the pattern does depend on a frame of reference.

Thank you for not being big endian with the hex.

I understand your example, and therefore hopefully, what you are
saying.

So it seems we need to _standardise_ on a particular frame of
reference, and then we detect the patterns in nature that are somehow
worth detecting (these have short descriptions, and high chances of
recurrence - e.g. my visual field is occupied by the pattern of a
predator coming to get me), and we can ignore the rest (these have long
descriptions, and low chances of recurrence - e.g. the smoke from that
cigarette veers a bit to the left but has a side-swirl coming off it
that veers to the right, which in turn has a tiny top-swirl on it
rotating the other way, etc ad nauseam).

This standard frame of reference seems to be the same one used by
animal brains, natural selection, science, and I think you mentioned
Von Neumann architecture computers somewhere above.

But you *seemed* to be saying that despite all this, it is never the
less an arbitrary choice of frame, and that patterns are neither
absolutley nor objectively present in the world.

Sorry if I'm strawmanning you a bit there, but I wanted to get to the
point of whether you suffer from a kind of pattern skepticism, along
the lines of what philosophers call colour skepticism.

To get to the subject of complexity (which this thread is actually
about).
Quantifying complexity seems to be a 'how far can a dog run in to a
wood' sort of problem. At first, as the descriptions get longer, the
complexity does indeed appear to get higher. Then it passes the half
way point and the longer descriptions seem to become less and less
about complexity until in the limit one is just defining one precise
state of a box of uniformly and randomly mixed, warm molecules.

Nic


.

Relevant Pages

  • Re: Evolution increases the computational ability of organisms.
    ... interviews Norman Packard and there is the following exchange: ... of the utility of increased computational complexity in evolution. ... conscious mind to perceive, much less appreciate, the pattern. ... The up and coming paradigm in physics is to view the whole universe as ...
    (sci.bio.evolution)
  • Re: Evolution increases the computational ability of organisms.
    ... interviews Norman Packard and there is the following exchange: ... of the utility of increased computational complexity in evolution. ... considers information processing as a measure of complexity. ... conscious mind to perceive, much less appreciate, the pattern. ...
    (sci.bio.evolution)
  • Re: Evolution increases the computational ability of organisms.
    ... interviews Norman Packard and there is the following exchange: ... of the utility of increased computational complexity in evolution. ... considers information processing as a measure of complexity. ... conscious mind to perceive, much less appreciate, the pattern. ...
    (sci.bio.evolution)
  • Re: Evolution increases the computational ability of organisms.
    ... interviews Norman Packard and there is the following exchange: ... of the utility of increased computational complexity in evolution. ... considers information processing as a measure of complexity. ... conscious mind to perceive, much less appreciate, the pattern. ...
    (sci.bio.evolution)
  • Re: Pitmans Miller Time
    ... this evidence could equally be explained by common ... design and common descent. ... The real absence in the pattern is more than ... You have presented no metric of "level of functional complexity". ...
    (talk.origins)