НИЖНЯЯ ОЦЕНКА НЕНАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ С ОПЕРАТОРОМ УСЛОВНОЙ ОСТАНОВКИ
Рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки. Предполагается, что функциональные операторы с вероятностью подвержены инверсным неисправностям на выходах, а операторы условной остановки абсолютно надежны. Доказано, что любую функцию f ∈ K (класс K найден явно) нельзя реализовать неприводимой неветвящейся программой с ненадежностью меньше ε(1 - ε)m, где m - число функциональных операторов в программе. Из этого и ранее полученного результата о верхней оценке ненадежности неветвящихся программ следует, что почти все функции можно реализовать асимптотически оптимальными по надежности неветвящимися программами, функционирующими с ненадежностью, асимтотически равной ε при ε→0.