Cellular automata (CAs) are discrete dynamical systems that have **been studied theoretically for years due to their architectural simplicity and the wide**
spectrum of behaviors they are capable of [1,2]. CAs are capable of universal computation and their time evolution can be complex. But many CAs show simpler dynamical behaviors such as fixed points and cyclic attractors. Here we study CAs that can be said to perform a simple "computational" task. One such tasks 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 the apparent simplicity of the task, it is difficult for a local system as a CA as it requires a coordination among the cells. 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 [3]. However, several efficient CAs for the density task have been found either by hand or by using heuristic methods, especially evolutionary computation [4,5,6,7,8,9]. **For a**
recent review of the work done on the problem in the last ten years see [10]. All previous investigations have empirically shown that finding good CAs for the majority task is very hard. In other words, the space of automata that are feasible solutions to the task is a difficult one to search. 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 try to statistically quantify in various ways the degree of difficulty of searching the majority CA landscape. Our investigation is a study of the fitness landscape as such, and thus it is ideally independent from the actual heuristics used to search the space provided that they use independent bit mutation as a search **operator.** However, a second goal of this study is to understand the features a good search technique for this particular problem space should possess.

The present study follows in the line of previous work by Hordijk [11] for another interesting collective CA problem: the synchronization task [12].

The paper proceeds as follows. The next section summarizes definitions and facts about CAs and the density task, including previous results obtained in building CAs for the task. A description of fitness landscapes and their statistical analysis follows. This is followed by a detailed analysis of the majority problem fitness landscape. 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.