Другие направления
В работе [BM] был построен псевдослучайный генератор, в котором центральным звеном является конструкция, которую можно рассматривать как самокорректирующуюся программу для решения задачи, эквивалентной проблеме дискретных логарифмов[BLR]. В работе [BLR] указывается, что Р. Рубинфилд ввел понятия программных чекеров для параллельных программ и использовал идею самотестирования для построения схемы константной глубины для проверки мажоритарных функций. В работе [BK] показаны методы построения программных чекеров для решения некоторых задач сортировки. В частности для двух массивов целых X и Y, представляющих некоторые мультимножества, чекер выдает «Сбой», если множество Y не упорядочено или если X¹Y. В противном случае, если данная программа выполняет корректную сортировку, чекер выдает «Норма».
