Теорема Шеннона — Лупанова

Теорема Шеннона — Лупанова определяет число элементов, необходимых для реализации автомата в заданном автоматном базисе^{[неизвестный термин]}.

Формулировка

1. Для любого базиса ${\displaystyle \Sigma }$: ${\displaystyle L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}}$, где ${\displaystyle C_{\Sigma }}$ — константа, зависящая от базиса.

2. Для любого ${\displaystyle \epsilon >0}$ доля функций ${\displaystyle f}$, для которых ${\displaystyle L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}}$ стремится к нулю с ростом ${\displaystyle n}$.

Пояснения

Здесь ${\displaystyle L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)}$, где максимум берется по всем функциям от ${\displaystyle n}$ переменных^{[прояснить]}. Знак ${\displaystyle \sim }$ обозначает асимптотическое равенство: ${\displaystyle a(n)\sim b(n)}$, если ${\displaystyle \lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1}$. Смысл второго утверждения теоремы в том, что с ростом ${\displaystyle n}$ почти все функции реализуются со сложностью, близкой к верхней границе ${\displaystyle L(n)}$.

Доказательство

Доказательство есть в статье^[1].