О надежности неветвящихся программ в базисе, содержащем обобщенную конъюнкцию, при произвольных неисправностях вычислительных операторов

Актуальность и цели. Понятие неветвящейся программы тесно связано с понятием схемы из функциональных элементов. Схемы из функциональных элементов являются моделями электронных схем, а неветвящиеся программы (как с условной остановкой, так и без нее) моделируют работу вычислительных устройств. Несмотря на эти различия, результаты о надежности и сложности, полученные для схем из функциональных элементов, переносятся на неветвящиеся программы без стоп-операторов и наоборот. До появления работ автора проблема построения надежных (а также и асимптотически оптимальных по надежности) неветвящихся программ с оператором условной остановки не рассматривалась. Впервые эта задача исследовалась при инверсных неисправностях на выходах вычислительных операторов, а затем при однотипных константных неисправностях на выходах вычислительных операторов. Вопрос о надежности неветвящихся программ при неисправностях произвольного типа до сих пор остается открытым. В работе рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки в полном конечном базисе, содержащем обобщенную конъюнкцию, в предположении, что вычислительные операторы независимо друг от друга подвержены неисправностям произвольного типа, а операторы условной остановки абсолютно надежны. Материалы и методы. Для повышения надежности исходных схем (программ) используется итерационный подход, т.е. многократное дублирование исходных схем (программ). Кроме того, разработан новый метод построения неветвящихся программ с оператором условной остановки. Результаты. Найдена верхняя оценка ненадежности неветвящихся программ с оператором условной остановки в полном конечном базисе B , содержащем обобщенную конъюнкцию. Выводы. Если полный конечный базис содержит обобщенную конъюнкцию, то любую булеву функцию можно реализовать неветвящейся программой с оператором условной остановки сколь угодно высокой наперед заданной надежности.