[Comp-neuro] Kolmogorov complexity

Carson Chow ccchow at pitt.edu
Tue Aug 19 19:36:26 CEST 2008


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.

> 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