О НАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ В БАЗИСЕ,
СОДЕРЖАЩЕМ ФУНКЦИЮ ВИДА x1a1 x2a2 1
Аннотация. <...> Рассматривается реализация булевых функций неветвящимися
программами с оператором условной остановки в полном конечном базисе B,
содержащем некоторую функцию вида x1a1 x2a2 , a1, a2 {0, 1} . <...> Предполагается,
что функциональные операторы с вероятностью ( (0, 1/ 2)) подвержены
инверсным неисправностям на выходах, а операторы условной остановки абсолютно надежны. <...> Программы с оператором условной остановки характеризуются наличием
управляющей команды – команды условной остановки, дающей возможность
досрочного прекращения работы при выполнении определенного условия. <...> Переменные из
множества Y назовем внутренними, переменные из множества Z – выходными переменными. <...> Вычислительной командой p назовем выражение p : a h b1, , bd . <...> Переменную a назовем выходом вычислительной команды, переменные b1, ..., bd –
входами этой команды. <...> Командой остановки p назовем выражение
p : stop a . <...> Переменную a назовем входом команды остановки p. <...> Последовательность Pr p1 pi pL , состоящая из вычислительных
команд и команд остановки, называется неветвящейся программой с условной
остановкой, если при любом j 1, 2, , L каждый вход команды p j есть
либо независимая переменная, либо выход некоторой вычислительной команды pi , где i j . <...> Неветвящаяся программа работает в дискретные моменты времени
t 0, 1, 2, ..., не изменяет значения независимых переменных и изменяет значения внутренних и выходных переменных. <...> Значением команды pt программы Pr на наборе x ( x1, , xn ) независимых переменных x1, x2 , ..., xn назовем значение ее выхода в момент времени t и обозначим pt ( x ) . <...> Тогда через s j будем обозначать j-ю команду остановки программы Pr, т.е. s j pt j . <...> Вычислительную команду pi (переменную xl ) назовем аргументом
команды остановки s j , n( s j ) r , и обозначим через q j , если <...> (i) выход команды pi (переменная xl ) является входом команды s j ;
(ii) среди команд pt , i t r , нет <...>