[Comp-neuro] Kolmogorov complexity

[james bower]

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.