You will be presented with the full text of a science research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
cellular automata ( cas ) are discrete dynamical systems that have been studied for years due to their architectural simplicity and the wide spectrum of behaviors they are capable of @xcite . here
we study cas that can be said to perform a simple `` computational '' task .
one such task is the so - called _ majority _ or _ density _
task in which a two - state ca is to decide whether the initial state contains more zeros than ones or vice versa . in spite of its apparent simplicity ,
it is a difficult problem for a ca as it requires a coordination among the automata . as such
, it is a perfect paradigm of the phenomenon of _ emergence _ in complex systems .
that is , the task solution is an emergent global property of a system of locally interacting agents .
indeed , it has been proved that no ca can perform the task perfectly i.e. , for any possible initial binary configuration of states @xcite .
however , several efficient cas for the density task have been found either by hand or by using heuristic methods , especially evolutionary computation @xcite .
for a recent review see @xcite .
all previous investigations have empirically shown that finding good cas for the majority task is very hard .
however , there have been no investigations , to our knowledge , of the reasons that make this particular fitness landscape a difficult one . in this paper
we statistically quantify in various ways the degree of difficulty of searching the majority ca landscape .
the paper proceeds as follows .
the next section summarizes some known facts about cas for the density task .
a description of its fitness landscape follows , focusing on the hardness and neutrality aspects .
next we identify and analyze a particular subspace of the problem search space called the olympus .
finally , we present our conclusions and hints to further works and open questions .
the density task is a prototypical distributed computational problem for cas . for a finite ca of size
@xmath0 it is defined as follows .
let @xmath1 be the fraction of 1s in the _ initial configuration _
( ic ) @xmath2 .
the task is to determine whether @xmath1 is greater than or less than @xmath3 . in this version ,
the problem is also known as the _ majority _ problem .
if @xmath4 then the ca must relax to a fixed - point configuration of all 1 s that we indicate as @xmath5 ; otherwise it must relax to a fixed - point configuration of all 0 s , noted @xmath6 , after a number of time steps of the order of the grid size @xmath0 . here
@xmath0 is set to 149 , the value that has been customarily used in research on the density task ( if @xmath0 is odd one avoids the case @xmath7 for which the problem is undefined ) .
this computation is trivial for a computer having a central control .
indeed , just scanning the array and adding up the number of , say , 1 bits will provide the answer in @xmath8 time .
however , it is nontrivial for a small radius one - dimensional ca since such a ca can only transfer information at finite speed relying on local information exclusively , while density is a global property of the configuration of states .
it has been shown that the density task can not be solved perfectly by a uniform , two - state ca with finite radius @xcite .
the lack of a perfect solution does not prevent one from searching for imperfect solutions of as good a quality as possible . in general , given a desired global behavior for a ca ( e.g. , the density task ) , it is extremely difficult to infer the local ca rule that will give rise to the emergence of the computation sought .
this is because of the possible nonlinearities and large - scale collective effects that can not in general be predicted from the sole local ca updating rule , even if it is deterministic . since exhaustive evaluation of all possible rules is out of the question except for elementary ( @xmath9 ) and perhaps radius - two automata , one possible solution consists in using evolutionary algorithms , as first proposed by packard in @xcite and further developed by mitchell et al .
+ the _ standard performance _ of the best rules ( with @xmath10 ) found at the end of the evolution is defined as the fraction of correct classifications over @xmath11 randomly chosen ics .
the ics are sampled according to a binomial distribution ( i.e. , each bit is independently drawn with probability @xmath3 of being 0 ) .
+ mitchell and coworkers performed a number of studies on the emergence of synchronous ca strategies for the density task ( with @xmath12 ) during evolution @xcite .
their results are significant since they represent one of the few instances where the dynamics of emergent computation in complex , spatially extended systems can be understood . as for the evolved cas , it was noted that , in most runs , the ga found unsophisticated strategies that consisted in expanding sufficiently large blocks of adjacent 1s or 0s .
this `` block - expanding '' strategy is unsophisticated in that it mainly uses local information to reach a conclusion . as a consequence ,
only those ic that have low or high density are classified correctly since they are more likely to have extended blocks of 1s or 0s .
these cas have a performance around @xmath13 .
a few runs yielded more sophisticated cas with performance ( around @xmath14 ) on a wide distribution of ics .
however , high - performance automata have evolved only nine times out of @xmath15 runs of the genetic algorithm .
this clearly shows that the search space is a very difficult one , even there exists some recent works on coevolutionary algorithm @xcite which able to find a number of `` block expanding '' strategies .
these sophisticated strategies rely on traveling signals ( `` particles '' ) that transfer spatial and temporal information about the density in local regions through the lattice , and have been quantitatively described with a framework known as `` computational mechanics '' @xcite .
the gkl rule @xcite is hand - coded but its behavior is similar to that of the best solutions found by evolution .
das and davis solutions are two other good solutions that have been found by hand @xcite .
other researchers have been able to artificially evolve a better ca ( @xmath16 ) by using genetic programming@xcite .
finally , juill _ et al _ @xcite obtained still better cas ( @xmath17 and @xmath18 ) by using a coevolutionary algorithm .
their coevolved ca has performance about 0.86 , which is the best result known to date .
we call the six best local optima known , with a standard performance over @xmath19 , the _ blok _ ( tab .
[ tab - opt6 ] ) .    in the next section we present a study of the overall fitness landscape ,
while section [ olympus ] concentrates on the structure of the landscape around the _
blok_.    .description in hexadecimal and standard performance of the 6 previously known best rules ( _ blok _ ) computed on sample size of @xmath20.[tab - opt6 ] [ cols="^,^ " , ]     [ [ neutral - degree . ] ] neutral degree .
+ + + + + + + + + + + + + + +    the figure [ fig - neutr]-b gives the neutral degree of solutions from olympus as a function of their performance .
the solutions below performance @xmath21 are randomly chosen in olympus .
the solutions over performance @xmath21 are sampled with 2 runs of a ga during @xmath22 generations .
this ga is based on ga defined by mitchell @xcite where the operators are restricted to olympus subspace and the selection is a tournament selection of size 2 taking into account the neutrality .
this ga allows to discover a lot of solutions between @xmath23 and @xmath24 and justified the useful of olympus runs , average performances are @xmath25 with standard deviation @xmath26 which is higher than @xmath27 of coevolutionary algorithm of pagie @xcite ] .
two important @xmath28 are located around fitnesses @xmath29 and @xmath21 where the neutral degree is over @xmath30 . for solutions over @xmath21 ,
the average of neutral degree is 37.6 which is a high neutral degree .
the landscape has a considerable number of points with performance @xmath29 or @xmath21 which means that investigations based on sampling techniques on the whole landscape are unlikely to give good results .
the neutrality of the landscape is high , and the neutral network topology is not completely random . exploiting similarities between the six best rules and symmetries in the landscape , we have defined the _ olympus _ landscape as a subspace of the majority problem landscape .
this subspace have less solutions with performance @xmath29 and it is easy to find solutions over @xmath23 with a simple ga . we have shown that the neutrality of landscape is high even for solution over @xmath21 .
andre , d. , bennett iii , f.h . ,
koza , j.r . :
discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem . in koza , j.r . ,
goldberg , d.e . ,
fogel , d.b .
, riolo , r.l .
, eds . : genetic programming 1996 : proceedings of the first annual conference , cambridge , ma , the mit press ( 1996 ) 311    juill , h. , pollack , j.b .
: coevolutionary learning : a case study . in : icml
98 proceedings of the fifteenth international conference on machine learning , san francisco , ca , morgan kaufmann ( 1998 ) 251259    crutchfield , j.p .
, mitchell , m. , das , r. : evolutionary design of collective computation in cellular automata . in crutchfield , j.p . , schuster , p. , eds . :
evolutionary dynamics : exploring the interplay of selection , accident , neutrality , and function .
oxford university press , oxford , uk ( 2003 ) 361411      pagie , l. , mitchell , m. : a comparison of evolutionary and coevolutionary search . in belew , r.k . ,
juill , h. , eds .
: coevolution : turning adaptive algorithms upon themselves , san francisco , california , usa ( 2001 ) 2025    das , r. , mitchell , m. , crutchfield , j.p . :
a genetic algorithm discovers particle - based computation in cellular automata . in davidor , y. , schwefel , h.p .
, mnner , r. , eds . : ppsn iii .
volume 866 of lncs .
, springer - verlag ( 1994 ) 344353                    barnett , l. : netcrawling - optimal evolutionary search with neutral networks . in : proceedings of the 2001 congress on evolutionary computation cec2001 , coex , world trade center , 159 samseong - dong , gangnam - gu , seoul , korea , ieee press ( 2001 ) 3037
we study in detail the fitness landscape of a difficult cellular automata computational task : the majority problem . 
 our results show why this problem landscape is so hard to search , and we quantify the large degree of neutrality found in various ways . 
 we show that a particular subspace of the solution space , called the `` olympus '' , is where good solutions concentrate , and give measures to quantitatively characterize this subspace .