Real-Time Generation of Primes by a 1-Bit-Communication Cellular Automaton

Issue title: Cellular Automata

Article type: Research Article

Authors: Umeo, Hiroshi | Kamikawa, Naoki

Affiliations: Faculty of Information Science and Technology, Osaka Electro-Communication University, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan | Noritsu Koki Co., Ltd., Wakayama-shi, Umehara, 579-1, Wakayama, 640-8550, Japan

Abstract: It is shown that an infinite prime sequence can be generated in real-time by a cellular automaton having 1-bit inter-cell communications (CA_{1-bit}). The algorithm presented is based on the classical sieve of Eratosthenes, and its implementation will be made on a CA_{1-bit} using 34 internal states and 71 transition rules.

Keywords: cellular automaton, 1-bit inter-cell communication, real-time prime generation algorithm, sieve of Eratosthenes

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 421-435, 2003