Computing Modulo-n by Composing Cellular Automata Rules

• Autorzy: Martins C. L. M. , de Oliveira P. P. B.

Identyfikatory

DOI

10.3233/FI-2016-1344

• Języki publikacji: EN

Abstrakty

EN

The understanding of how predefined computations can be attained by means of individual cellular automata rules, their spatial arrangements or their temporal sequences, is a key conceptual underpinning in the general notion of emergent computation. In this context, here we construct a solution to the MODn problem, which is the determination of whether the number of 1-bits in a cyclic binary string is perfectly divisible by the integer n > 1. Our solution is given for any lattice size N that is co-prime to n, and relies upon a set of one-dimensional rules, with maximum radius of n - 1, organised in a temporal sequence. Although the simpler cases of the problem for n = 2 and n = 3 have been addressed in the literature, this is the first account on the general case, for arbitrary n.

Słowa kluczowe

EN

cellular automata; emergent computation; rule composition; modulo-n problem; MODn; active state transitions; parity; classification; decision problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 1
• Strony: 1--17
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Martins C. L. M.

• Pós-Graduação em Engenharia Elétrica e Computação, Universidade Presbiteriana Mackenzie, São Paulo, SP - Brazil

autor

de Oliveira P. P. B.

• Pós-Graduação em Engenharia Elétrica e Computação, Universidade Presbiteriana Mackenzie, São Paulo, SP - Brazil

Bibliografia

• [1] Wolfram S. A New Kind of Science. Wolfram Media, Champaign; 2002.
• [2] Xu H, Lee KM, Chau HF. Modulo three problem with a cellular automaton solution. International Journal of Modern Physics C. 2003;14(03):249–256. doi:10.1142/S0129183103004450.
• [3] Lee KM, Xu H, Chau HF. Parity problem with a cellular automaton solution. Physical Review E. 2001;64(2):026702. doi:10.1103/PhysRevE.64.026702.
• [4] Martins CLM, de Oliveira PPB. Improvement of a result on sequencing elementary cellular automata rules for solving the parity problem. Electronic Notes in Theoretical Computer Science. 2009;252:103–119. doi:10.1016/j.entcs.2009.09.017.
• [5] Betel H, de Oliveira PPB, Flocchini P. Solving the parity problem in one-dimensional cellular automata. Natural Computing. 2013;12(3):323–337. doi:10.1007/s11047-013-9374-9.
• [6] Martins CLM, de Oliveira PPB. Evolving sequential combinations of elementary cellular automata rules. Lecture Notes in Computer Science. 2005;3630:461–470. doi:10.1007/11553090 47.
• [7] Martins CLM, de Oliveira PPB. Merging cellular automata rules to optimise a solution to the Modulo-n problem. Lecture Notes in Computer Science. 2015;9099:196–209. doi:10.1007/978-3-662-47221-7 15