On the effectiveness of cellular automata to add real numbers

Abstract

This paper investigates the effectiveness of cellular automata to compute arithmetic functions over the set of real numbers. Since cellular automata (CA) have parallel computational ability in conjunction with the capacity to accept an infinite length input, the CA should be able to effectively compute real number arithmetic. This paper shows that typical representations of real numbers do not lend themselves to effective computation by a CA and that a nonstandard representation must be employed in order to accomplish this.

Keywords:

• Cellular automata
• Computability theory
• Parallel processing
• Arithmetic