[Comp-neuro] Kolmogorov complexity
james bower
bower at uthscsa.edu
Wed Aug 20 18:29:41 CEST 2008
Actually, I think the right way to say this is that Jim assumes that
it is really really big, and Bard assumes (and hopes) that it is not
so big. Neither of us know. Further, Jim would like to believe Bard
and wishes him well -- he is just skeptical.
The question here is not the truth, but the assumptions one makes in
formulating ones approach to figuring it out.
As you also point out, this is a process.
Is there any evidence we can take now to estimate the convergence
point -- Jim is still building more and more realistic models, and
abstract modelers who are willing to keep educating themselves about
biology are, generally speaking, playing with more and more complex
models --
I will leave it to the mathematicians to figure out the likely
convergence point.
:-)
Jim
On Aug 19, 2008, at 12:36 PM, Carson Chow wrote:
> 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.
>>
>>
>
> _______________________________________________
> Comp-neuro mailing list
> Comp-neuro at neuroinf.org
> http://www.neuroinf.org/mailman/listinfo/comp-neuro
==================================
Dr. James M. Bower Ph.D.
Professor of Computational Neuroscience
Research Imaging Center
University of Texas Health Science Center -
- San Antonio
8403 Floyd Curl Drive
San Antonio Texas 78284-6240
Main Number: 210- 567-8100
Fax: 210 567-8152
Mobile: 210-382-0553
CONFIDENTIAL NOTICE:
The contents of this email and any attachments to it may be privileged
or
contain privileged and confidential information. This information is
only
for the viewing or use of the intended recipient. If you have received
this
e-mail in error or are not the intended recipient, you are hereby
notified
that any disclosure, copying, distribution or use of, or the taking of
any
action in reliance upon, any of the information contained in this e-
mail, or
any of the attachments to this e-mail, is strictly prohibited and that
this
e-mail and all of the attachments to this e-mail, if any, must be
immediately returned to the sender or destroyed and, in either case,
this
e-mail and all attachments to this e-mail must be immediately deleted
from
your computer without making any copies hereof and any and all hard
copies
made must be destroyed. If you have received this e-mail in error,
please
notify the sender by e-mail immediately.
More information about the Comp-neuro
mailing list