Сложность реализации почти всех булевых функций клеточными автоматами с локаторами

Аннотация

В работе исследуется возможность реализации произвольной булевой функции клеточными автоматами с локаторами. Доказано, что в двумерном клеточном автомате с локаторами любая булева функция от \(n\) переменных реализуется схемой площади \(2^n+O(n2^{n/2})\) с задержкой четыре такта и поступлением нового входного набора на каждом такте. Подсчёт конфигураций даёт нижнюю оценку \(\Omega (2^n)\) для почти всех функций. Функция Шеннона площади имеет порядок \(2^n\).

Ключевые слова: клеточные автоматы, локаторы, булевы функции, площадь схем, функция Шеннона.

BibTeX
@article{IS-Nadirov2026,
  author  = {Надиров, Чингиз},
  title   = {{Сложность реализации почти всех булевых функций клеточными автоматами с локаторами}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {224--227},
}
AMSBIB
\RBibitem{IS-Nadirov2026}
\by Ч.~Надиров
\paper Сложность реализации почти всех булевых функций клеточными автоматами с локаторами
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 224--227
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover