Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

The Complexity of Implementing Almost All Boolean Functions Using Cellular Automata with Locators

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover