Target-Oriented Self-Structuring in Classifying Cellular Automata
Christopher Auer, Patrick Wuchner and Hermann De Meer
Some cellular automata are able to solve classification problems on their initial configuration by building globally visible structures. However, no formal measures exist yet for describing or detecting this behavior in general. The lack of such formal methods often leads to quite observer-dependent discussions of emergent computation. In this paper, we propose the measures of target orientation and self-structuring that allow to formally evaluate a cellular automaton’s ability to solve a classification problem by emergent computation. By the means of these measures, globally emerging patterns can be recognized and their contribution to the solution of the classification problem can be judged in an observer-independent way.
Keywords: One-dimensional cellular automata; Classification problem; Emergent computation; Formal measures