Рассматриваются программы над полным базисом, вычисляющие двоичные всюду определенные функции. Доказывается, что если функция, вычисляемая программой, обладают энтропией H, то имеется, по меньшей мере, одно вычисление программы длины 2dH для некоторой положительной константы d.
Язык публикации: русский, страниц:32
Направление исследований:
Математическое моделирование в актуальных проблемах науки и техники
