[Comp-neuro] Kolmogorov complexity
Carson Chow
ccchow at pitt.edu
Tue Aug 19 19:36:26 CEST 2008
Hi,
I just wanted to point out that Kolmogorov complexity (KC) is defined as
the minimal length of a program that can generate a string and halt on a
Turing machine. In this context, it would correspond to the minimal
string length that could describe the brain, where the brain is coded
into a bit string. So if the brain were Kolmogorov complexity complete
(KCC) then the only description of the brain is the brain itself. The
simplest example of something KCC is a completely random string of
bits. Also, the type of "computer program" used to express the minimal
description doesn't matter since the difference in the minimal program
length only differs by a constant when you switch Turing machines. The
final point about KC is that is undecidable, meaning that there is no
general computation that can determine the KC. So we can never know for
sure if the brain is KCC or not.
Let me rephrase Jim's question below to: given a function that maps a
set of inputs to a set of outputs, is there a simpler function that can
do the same thing? The answer is that there is a function that is the
simplest, meaning that it has the smallest length program to do the job
but we can never know what it is with any certainty. The best we can do
is to keep coming up with guesses and comparing them to the current
champion. Phrased this way, the question of whether the brain is KCC is
somewhat of a tautology. It depends on what we mean by a description of
the brain. If we mean it to be a characterization of what it does then
by definition it is KCC because we can always characterize what it does
by the minimal description. So I would suggest that what we are trying
to do is to find the minimal description of the brain and Jim thinks
that it is really really big like while Bard thinks it is not so big.
best,
Carson
>
>
> Which brings us to a specific aspect of Kolmogorov complexity which is
> directly relevant to neuroscience, and that is the relationship
> between the complexity of the solution to a problem and the intrinsic
> complexity of the problem itself. In his book "Vision", Marr proposed
> (in what he referred to actually as a 'bottom up' approach to
> understanding the nervous system), that one must first understand the
> nature of the computational problem being solved, and then consider
> the set of algorythms that could solve the problem and then and only
> then, look at the particular instance of that set implemented in the
> brain (under the assumption that the brain was not KCC). Complexity
> theory provides a formal framework (oh that again) for considering the
> relationship between the inherent complexity of a particular problem,
> and the complexity of the solution to that problem -- I believe (and
> someone will surely correct me if I am wrong), there is a fundamental
> principle that the complexity of the problem sets a kind of floor for
> the complexity of the solutions to the problem. That is, you can
> find more complex solutions to a problem -- but you can't find a
> solution with less complexity than the problem itself, if you did,
> then you could recast the original problem in a less complex form.
> Accordingly, if the brain is KCC, then, by definition, solutions to
> real brain problems involving 4 input 'neurons', 10 in the hidden
> layer, and 3 output 'neurons' must be underestimating the real nature
> of the problem the brain solves. Or in other words, if the solution
> to the problem is less complex than the brain, then one has
> misunderstood the problem.
>
>
More information about the Comp-neuro
mailing list