The Complexity of Implementing Almost All Boolean Functions Using Cellular Automata with Locators
Received: 26 Oct 2026 Revised: 30 Oct 2026 Accepted: 31 Oct 2026
Published: 2026, vol. 30, issue 4, pp. 224–227
Abstract
This paper investigates the possibility of implementing arbitrary Boolean functions using cellular automata with locators. It is proved that, in a two-dimensional cellular automaton with locators, any Boolean function of \(n\) variables can be implemented by a circuit of area \(2^n+O(n2^{n/2})\), with a delay of four time steps and a new input vector supplied at every time step. Configuration counting yields a lower bound of \(\Omega (2^n)\) for almost all Boolean functions. The Shannon function for circuit area is of order \(2^n\).
Keywords: cellular automata, locators, Boolean functions, circuit area, Shannon function.
BibTeX
@article{IS-Nadirov2026,
author = {Nadirov, Chingiz},
title = {{The Complexity of Implementing Almost All Boolean Functions Using Cellular Automata with Locators}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {224--227},
}
AMSBIB
\Bibitem{IS-Nadirov2026}
\by C.~Nadirov
\paper The Complexity of Implementing Almost All Boolean Functions Using Cellular Automata with Locators
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 224--227
\lang In Russian
RU