The Representation Role for Basic Operations Embodied in Cellular Automata: A Suitability Example for Addition of Natural Numbers in Redundant vs Conventional Numeral Systems
Salvatore Di Gregorio
Cellular Automata (CA) can embody different numeral representation and perform related basic arithmetical operations. However conventional numeral representations are thought as intrinsically sequential, while some redundant numeral representations exalt the CA parallelism in a space/time trade-off. Usually the emigration toward an advantageous redundant numeric representation is costless, but the inverse one implies a cost that annuls the benefits in terms of computation time. The problem then arises when the result of an operation must be utilized in the conventional representation. This paper explores the properties of the conventional representation embodied in a CA together with the addition of natural numbers and the corresponding ones of a redundant representation, the rules and time cost for the passage from conventional numeral system to redundant one and vice versa. The results permit to individuate the CA computation context (longest sequence of additions or operations based on addition), when redundancy could be exploited advantageously.
Keywords: Cellular automata, parallel computation, computational complexity, redundant numeral binary systems, natural numbers, parallel addition