Создание самокрректирующихся программ для решения прикладных задач
3
Пусть
означает некоторую вычислительную задачу и/или неко-
торую задачу поиска решения. Для
x
, рассматриваемого в качестве
входа задачи, пусть
(
x
) обозначает результат решения задачи
.
Пусть
Р
— программа, предназначенная для решения задачи
. Будем
говорить, что
Р
имеет дефект, если для некоторого входа
x
задачи
имеет место
P
(
x
)
(
x
). Определим
программный чекер C
для зада-
чи
следующим образом. Чекер
( , )
Р
С x k
является вероятностной
программой, удовлетворяющей следующим условиям.
Для любой программы
P
(предположительно решающей задачу
),
выполняемой на всех входах задачи
, для любого входа
x
и для любого
положительного
k
(параметра безопасности) имеет место:
если программа
P
не имеет дефектов, т. е.
P
(
x
) =
(
x
) для всех
входов
x
задачи
, то
( , )
Р
С x k
выдаст на выходе ответ «Норма» с ве-
роятностью не менее 1 – 1/2
k
;
если программа
P
имеет дефекты, т. е.
P
(
x
)
(
x
) для всех входов
x
задачи
, тогда
( , )
Р
С x k
выдаст на выходе ответ «Сбой» с вероятно-
стью не менее 1 – 1/2
k
.
Самокорректирующаяся программа —
это вероятностная про-
грамма
C
f
, которая помогает программе
P
скорректировать саму себя,
если только
P
выдает корректный результат с малой вероятностью
ошибки, т. е. для любого
x
,
C
f
вызывает программу
P
для корректного
вычисления
f
(
x
), в то время как сама
P
обладает малой вероятностью
ошибки.
Самотестирующейся/самокорректирующейся программной па-
рой
называется пара программ вида (
T
f
,
C
f
). Предположим, пользова-
тель применяет программу
P
, которая вычисляет
f
и тестирует саму
себя при помощи программы
T
f
. Если
P
не проходит такие тесты, то-
гда по любому
x
, пользователь может вызвать программу
C
f
, которая
в свою очередь вызывает
P
для корректного вычисления
f
(
x
). Даже
если программа
P
вычисляет значение функции
f
некорректно для
отдельной небольшой доли входных значений, ее все равно можно
уверенно использовать для корректного вычисления
f
(
x
) для любо-
го
x
. Кроме того, если в будущем удастся написать программу P
для
вычисления той же функции
f
, то пара (
T
f
,
C
f
) может использоваться
для самотестирования и самокоррекции P
без какой-либо модифика-
ции этой пары.
Вероятностная программа M является
оракульной программой
,
если она может вызывать другую программу во время выполне-
ния M.
Пусть
x
I
n
и пусть
c
> 1 — целое число. Свойство
рандомизиро-
ванной самосводимости
заключается в том, что существует алгоритм
A
1
, работающий за время пропорциональное
nO
(1), посредством ко-
