\input style
\chapter{3 їрЁръЄхЁшёЄшър ёхьрэЄшъш}

эАС ИНТЕРЕСУЮТ ПРЕИМУЩЕСТВЕННО ТАКИЕ СИСТЕМЫ,
КОТОРЫЕ, ПРИСТУПИВ К РАБОТЕ В НЕКОЕМ "НАЧАЛЬНОМ
СОСТОЯНИИ", ЗАВЕРШАТ ЕЕ В КАКОМ-ТО "КОНЕЧНОМ
СОСТОЯНИИ", КОТОРОЕ, КАК ПРАВИЛО, ЗАВИСИТ ОТ
ВЫБОРА НАЧАЛЬНОГО СОСТОЯНИЯ. ¤ТОТ ПОДХОД НЕСКОЛЬКО
ОТЛИЧАЕТСЯ ОТ КОНЦЕПЦИИ АВТОМАТА С КОНЕЧНЫМ ЧИСЛОМ
СОСТОЯНИЙ, КОТОРЫЙ, С ОДНОЙ СТОРОНЫ, ВОСПРИНИМАЕТ
ПОТОК ВХОДНЫХ СИМВОЛОВ, А С ДРУГОЙ СТОРОНЫ,
ПОРОЖДАЕТ ПОТОК ВЫХОДНЫХ СИМВОЛОВ. ўТОБЫ ПЕРЕВЕСТИ
ЭТО В НАШУ СХЕМУ, МЫ ДОЛЖНЫ  ПРЕДПОЛОЖИТЬ, ЧТО
ЗНАЧЕНИЕ ВХОДА (Т. Е. АРГУМЕНТ) oТРАЖАЕТСЯ В
ВЫБОРЕ НАЧАЛЬНОГО СОСТОЯНИЯ И ЧТО ЗНАЧЕНИЕ ВЫХОДА
(Т. Е. ОТВЕТ) ОТРАЖАЕТСЯ В ВЫБОРЕ КОНЕЧНОГО
СОСТОЯНИЯ. эАШ ПОДХОД ИЗБАВЛЯЕТ НАС ОТ
ВСЕВОЗМОЖНЫХ НЕПРИНЦИПИАЛЬНЫХ СЛОЖНОСТЕЙ.

яЕРВАЯ ЧАСТЬ ЭТОЙ ГЛАВЫ ПОСВЯЩЕНА ПОЧТИ ИСКЛЮЧИТЕЛЬНО
ТАК НАЗЫВАЕМЫМ "ДЕТЕРМИНИРОВАННЫМ МАШИНАМ", ТОГДА
КАК ВО ВТОРОЙ ЧАСТИ (КОТОРУЮ МОЖНО ПРОПУСТИТЬ ПРИ
ПЕРВОМ ЧТЕНИИ) РЕЧЬ ИДЕТ О ТАК НАЗЫВАЕМЫХ
"НЕДЕТЕРМИНИРОВАННЫХ МАШИНАХ". ЁАЗЛИЧИЕ МЕЖДУ
ЭТИМИ ДВУМЯ ПОНЯТИЯМИ СОСТОИТ  В ТОМ, ЧТО ДЛЯ
ДЕТЕРМИНИРОВАННОЙ МАШИНЫ СОБЫТИЕ, КОТОРОЕ
ПРОИЗОЙДЕТ ПОСЛЕ ЗАПУСКА КОНСТРУКЦИИ, ПОЛНОСТЬЮ
ОПРЕДЕЛЯЕТСЯ ЕЕ НАЧАЛЬНЫМ СОСТОЯНИЕМ. хСЛИ ОНА
ЗАПУСКАЕТСЯ ДВАЖДЫ В ОДИНАКОВЫХ НАЧАЛЬНЫХ
СОСТОЯНИЯХ, ТО ПРОИЗОЙДУТ ОДИНАКОВЫЕ СОБЫТИЯ:
ПОВЕДЕНИЕ ДЕТЕРМИНИРОВАННОЙ МАШИНЫ ПОЛНОСТЬЮ
ВОСПРОИЗВОДИМО. фЛЯ НЕДЕТЕРМИНИРОВАННОЙ МАШИНЫ,
НАПРОТИВ, ЗАПУСК В ЗАДАННОМ НАЧАЛЬНОМ СОСТОЯНИИ
ПРИВЕДЕТ К КАКОМУ-ТО ОДНОМУ СОБЫТИЮ ИЗ КЛАССА
ВОЗМОЖНЫХ СОБЫТИЙ; НАЧАЛЬНОЕ СОСТОЯНИЕ ТОЛЬКО
ФИКСИРУЕТ ЭТОТ КЛАСС В ЦЕЛОМ.

ЄЕПЕРЬ Я ПРЕДПОЛАГАЮ, ЧТО ПРОЕКТИРОВАНИЕ ТАКОЙ СИСТЕМЫ
ЯВЛЯЕТСЯ ЦЕЛЕНАПРАВЛЕННОЙ ДЕЯТЕЛЬНОСТЬЮ, Т. Е. МЫ
ЖЕЛАЕМ ДОСТИЧЬ ЧЕГО-ТО С ПОМОЩЬЮ ЭТОЙ СИСТЕМЫ.
эАПРИМЕР, ЕСЛИ МЫ ХОТИМ СОЗДАТЬ МАШИНУ, СПОСОБНУЮ
ВЫЧИСЛЯТЬ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ, ТО МОЖЕМ
ПОТРЕБОВАТЬ, ЧТОБЫ КОНЕЧНОЕ СОСТОЯНИЕ
УДОВЛЕТВОРЯЛО УСЛОВИЮ
$$
x=\эюф(X, Y) \eqno(1)
$$
т РАССМОТРЕННОЙ РАНЕЕ МАШИНЕ МЫ БУДЕМ ИМЕТЬ ТАКЖЕ
$y=\эюф(X, Y)$, ПОТОМУ ЧТО ИГРА ЗАКАНЧИВАЕТСЯ ПРИ
$x=y$, НО ЭТО ОТНЮДЬ НЕ ЧАСТЬ НАШИХ ТРЕБОВАНИЙ,
КОГДА МЫ РЕШАЕМ ПРИНЯТЬ КОНЕЧНОЕ ЗНАЧЕНИЕ $x$ В
КАЧЕСТВЕ ОТВЕТА.

ьЫ НАЗЫВАЕМ УСЛОВИЕ (1) (ЖЕЛАЕМЫМ) "ПОСТУСЛОВИЕМ" --- "ПОСТ", ПОТОМУ ЧТО 
ОНО НАЛАГАЕТСЯ НА ТО СОСТОЯНИЕ, В КОТОРОМ СИСТЕМА ДОЛЖНА ОКАЗАТЬСЯ
\emph{ПОСЛЕ} СВОЕЙ РАБОТЫ. чАМЕТИМ, ЧТО
ПОСТУСЛОВИЕ МОЖЕТ УДОВЛЕТВОРЯТЬСЯ МНОГИМИ
ВОЗМОЖНЫМИ СОСТОЯНИЯМИ. т ТАКОМ СЛУЧАЕ МЫ
ЕСТЕСТВЕННО СЧИТАЕМ КАЖДОЕ ИЗ НИХ ОДИНАКОВО
УДОВЛЕТВОРИТЕЛЬНЫМ, ТАК ЧТО НЕТ ОСНОВАНИЙ
ТРЕБОВАТЬ, ЧТОБЫ КОНЕЧНОЕ СОСТОЯНИЕ БЫЛО
ОДНОЗНАЧНОЙ ФУНКЦИЕЙ ОТ НАЧАЛЬНОГО СОСТОЯНИЯ.
(ўИТАТЕЛЬ УВИДИТ ИЗ ДАЛЬНЕЙШЕГО, ЧТО ИМЕННО ЗДЕСЬ
ПРОЯВЛЯЕТСЯ ПОТЕНЦИАЛЬНАЯ ПОЛЕЗНОСТЬ
НЕДЕТЕРМИНИРОВАННОГО УСТРОЙСТВА.)

фЛЯ ТОГО ЧТОБЫ ИСПОЛЬЗОВАТЬ ЭТУ МАШИНУ, КОГДА МЫ
ХОТИМ ПОЛУЧИТЬ ОТ НЕЕ ОТВЕТ (НАПРИМЕР, ХОТИМ
"ЧТОБЫ ОНА ДОСТИГЛА КОНЕЧНОГО СОСТОЯНИЯ,
УДОВЛЕТВОРЯЮЩЕГО ПОСТУСЛОВИЮ (1) ДЛЯ ЗАДАННОГО
НАБОРА ЗНАЧЕНИЙ $X$ И $Y$"), НАМ ЖЕЛАТЕЛЬНО ЗНАТЬ
МНОЖЕСТВО СООТВЕТСТВУЮЩИХ НАЧАЛЬНЫХ СОСТОЯНИЙ, А
БОЛЕЕ ТОЧНО, МНОЖЕСТВО ТАКИХ НАЧАЛЬНЫХ СОСТОЯНИЙ,
ПРИ КОТОРЫХ ЗАПУСК ОБЯЗАТЕЛЬНО ПРИВЕДЕТ К СОБЫТИЮ
ПРАВИЛЬНОГО ЗАВЕРШЕНИЯ ПРИЧЕМ СИСТЕМА ОСТАНЕТСЯ В
КОНЕЧНОМ СОСТОЯНИИ, УДОВЛЕТВОРЯЮЩЕМ ПОСТУСЛОВИЮ.
хСЛИ МЫ МОЖЕМ ПРИВЕСТИ СИСТЕМУ БЕЗ ВЫЧИСЛИТЕЛЬНЫХ
УСИЛИЙ В ОДНО ИЗ ТАКИХ СОСТОЯНИЙ, ТО МЫ УЖЕ ЗНАЕМ,
КАК ИСПОЛЬЗОВАТЬ ЭТУ СИСТЕМУ ДЛЯ ПОЛУЧЕНИЯ
ЖЕЛАЕМОГО ОТВЕТА. яРИВЕДЕМ ПРИМЕР ДЛЯ ЕВКЛИДОВОЙ
ИГРЫ НА КАРТОНЕ: МЫ МОЖЕМ ГАРАНТИРОВАТЬ КОНЕЧНОЕ
СОСТОЯНИЕ, УДОВЛЕТВОРЯЮЩЕЕ ПОСТУСЛОВИЮ (1) ДЛЯ
ЛЮБОГО НАЧАЛЬНОГО СОСТОЯНИЯ, УДОВЛЕТВОРЯЮЩЕГО
УСЛОВИЮ
$$
\эюф(x,y)=\эюф(ї,Y) \and 0<x\le500 \and 0<y\le 500
\eqno(2)
$$
(тЕРХНИЕ ГРАНИЦЫ ДОБАВЛЕНЫ, ЧТОБЫ УЧЕСТЬ
ОГРАНИЧЕННЫЙ РАЗМЕР ЛИСТА КАРТОНА. хСЛИ МЫ
НАЧИНАЕМ С ПАРОЙ $(X,Y)$, ТАКОЙ, ЧТО
$\эюф(X,Y)=713$, ТО НЕ СУЩЕСТВУЕТ ПАРЫ $(x,y)$,
УДОВЛЕТВОРЯЮЩЕЙ УСЛОВИЮ (2), Т. Е. ДЛЯ ТАКИХ
ЗНАЧЕНИЙ $X$ И $Y$ УСЛОВИЕ (2) СВОДИТСЯ К
ПРЕДИКАТУ $F$, А ЭТО ОЗНАЧАЕТ, ЧТО РАССМАТРИВАЕМАЯ
МАШИНА НЕ МОЖЕТ БЫТЬ ИСПОЛЬЗОВАНА ДЛЯ ВЫЧИСЛЕНИЯ
$\эюф(X,Y)$ ПРИМЕНИТЕЛЬНО К ЭТОЙ ПАРЕ ЗНАЧЕНИЙ $X$
И $Y$).

яРИ МНОГИХ КОМБИНАЦИЯХ $(X, Y)$ МНОГИЕ СОСТОЯНИЯ
УДОВЛЕТВОРЯЮТ УСЛОВИЮ (2). т СЛУЧАЕ $0<X\le 500$ И
$0<Y\le500$ \emph{ТРИВИАЛЬНЫМ} ВЫБОРОМ ЯВЛЯЕТСЯ
$x=X$ И $y=Y$. ¤ТОТ ВЫБОР МОЖЕТ БЫТЬ ПРОИЗВЕДЕН
БЕЗ КАКОГО-ЛИБО ВЫЧИСЛЕНИЯ ФУНКЦИИ эюф И ДАЖЕ БЕЗ
УЧЕТА ТОГО ФАКТА, ЧТО ЭТО СИММЕТРИЧНАЯ ФУНКЦИЯ ОТ
СВОИХ АРГУМЕНТОВ.

єСЛОВИЕ, ХАРАКТЕРИЗУЮЩЕЕ МНОЖЕСТВО ВСЕХ НАЧАЛЬНЫХ
СОСТОЯНИЙ, ПРИ КОТОРЫХ ЗАПУСК ОБЯЗАТЕЛЬНО ПРИВЕДЕТ
К СОБЫТИЮ
ПРАВИЛЬНОГО ЗАВЕРШЕНИЯ, ПРИЧЕМ СИСТЕМА ОСТАНЕТСЯ В КОНЕЧНОМ 
СОСТОЯНИИ, УДОВЛЕТВОРЯЮЩЕМ ЗАДАННОМУ ПОСТУСЛОВИЮ,  
НАЗЫВАЕТСЯ "СЛАБЕЙШИМ ПРЕДУСЛОВИЕМ, СООТВЕТСТВУЮЩИМ ЭТОМУ  
ПОСТУСЛОВИЮ". (ьЫ НАЗЫВАЕМ ЕГО "СЛАБЕЙШИМ", ПОСКОЛЬКУ, ЧЕМ 
СЛАБЕЕ УСЛОВИЕ, ТЕМ БОЛЬШЕ СОСТОЯНИЙ УДОВЛЕТВОРЯЮТ ЕМy, А МЫ 
СТРЕМИМСЯ ЗДЕСЬ ОХАРАКТЕРИЗОВАТЬ ВСЕ ВОЗМОЖНЫЕ НАЧАЛЬНЫЕ 
СОСТОЯНИЯ, КОТОРЫЕ НЕИЗБЕЖНО ПРИВЕДУТ К ЖЕЛАЕМОМУ КОНЕЧНОМУ 
СОСТОЯНИЮ.)

хСЛИ СИСТЕМА (МАШИНА, КОНСТРУКЦИЯ) ОБОЗНАЧАЕТСЯ ЧЕРЕЗ S, А 
ЖЕЛАЕМОЕ ПОСТУСЛОВИЕ --- ЧЕРЕЗ R, ТО СООТВЕТСТВУЮЩЕЕ 
СЛАБЕЙШЕЕ ПРЕДУСЛОВИЕ МЫ ОБОЗНАЧИМ%
\note{яО НАЧАЛЬНЫМ БУКВАМ 
АНГЛИЙСКИХ СЛОВ weakest РrЕ-condition.--- яРИМ. ПЕРЕВ.}
$$
\wp (S,R)
$$

хСЛИ НАЧАЛЬНОЕ СОСТОЯНИЕ УДОВЛЕТВОРЯЕТ $\wp(S, R)$, ТО 
КОНСТРУКЦИЯ ОБЯЗАТЕЛЬНО ОБЕСПЕЧИТ В КОНЦЕ КОНЦОВ ИСТИННОСТЬ 
$R$. яОСКОЛЬКУ $\wp(S, R)$ --- ЭТО СЛАБЕЙШЕЕ ПРЕДУСЛОВИЕ, МЫ 
ЗНАЕМ ТАКЖЕ, ЧТО ЕСЛИ НАЧАЛЬНОЕ СОСТОЯНИЕ НЕ УДОВЛЕТВОРЯЕТ 
$\wp(S, R)$, ТО ТАКОЙ ГАРАНТИИ ДАТЬ НЕЛЬЗЯ, Т. Е. ХОД 
СОБЫТИЙ МОЖЕТ ПРИВЕСТИ К ЗАВЕРШЕНИЮ РАБОТЫ В КОНЕЧНОМ 
СОСТОЯНИИ, Нe УДОВЛЕТВОРЯЮЩЕМ $R$, А МОЖЕТ ДАЖЕ И ВООБЩЕ 
ПОМЕШАТЬ ДОСТИЖЕНИЮ КАКОГО БЫ ТО НИ БЫЛО КОНЕЧНОГО СОСТОЯНИЯ 
(КАК МЫ УВИДИМ ДАЛЕЕ, ЛИБО ПОТОМУ, ЧТО СИСТЕМА ОКАЗЫВАЕТСЯ 
ВОВЛЕЧЕННОЙ В ВЫПОЛНЕНИЕ НЕЗАВЕРШИМОГО ЗАДАНИЯ, ЛИБО ПОТОМУ, 
ЧТО СИСТЕМА ПОПАДАЕТ В ТУПИК).

ьЫ СЧИТАЕМ, ЧТО НАМ ДОСТАТОЧНО ХОРОШО ИЗВЕСТНО, КАК РАБОТАЕТ 
КОНСТРУКЦИЯ $S$, ЕСЛИ МОЖЕМ ВЫВЕСТИ ДЛЯ ЛЮБОГО ПОСТУСЛОВИЯ 
$R$ СООТВЕТСТВУЮЩЕЕ СЛАБЕЙШЕЕ ПРЕДУСЛОВИЕ $\wp (S,R)$, 
ПОСКОЛЬКУ ТЕМ САМЫМ МЫ УЛОВИЛИ, ЧТ\'О ЭТА КОНСТРУКЦИЯ 
СПОСОБНА СДЕЛАТЬ ДЛЯ НАС; ЭТО НАЗЫВАЕТСЯ "ЕЕ СЕМАНТИКОЙ".

чДЕСЬ УМЕСТНЫ ДВА ЗАМЕЧАНИЯ. тО-ПЕРВЫХ, МНОЖЕСТВО ВОЗМОЖНЫХ 
ПОСТУСЛОВИЙ, ВООБЩЕ ГОВОРЯ, СТОЛЬ ОГРОМНО, ЧТО ЭТА 
ИНФОРМАЦИЯ В ТАБЛИЧНОЙ ФОРМЕ (Т. Е. В ВИДЕ ТАБЛИЦЫ, ГДЕ 
КАЖДОМУ ПОСТУСЛОВИЮ $R$ СООТВЕТСТВУЕТ ЗАПИСЬ, В КОТОРОЙ 
СОДЕРЖИТСЯ СООТВЕТСТВУЮЩЕЕ ПРЕДУСЛОВИЕ $\wp(S, R))$, 
ОКАЗАЛАСЬ БЫ СОВЕРШЕННО НЕОБОЗРИМОЙ, А СЛЕДОВАТЕЛЬНО, 
БЕСПОЛЕЗНОЙ. яОЭТОМУ ОПРЕДЕЛЕНИЕ СЕМАНТИКИ ТОЙ ИЛИ ИНОЙ 
КОНСТРУКЦИИ ВСЕГДА ДАЕТСЯ ДРУГИМ СПОСОБОМ --- В ВИДЕ 
ПРАВИЛА, ОПИСЫВАЮЩЕГО, КАК ДЛЯ ЛЮБОГО ЗАДАННОГО ПОСТУСЛОВИЯ 
$R$ МОЖНО ВЫВЕСТИ СООТВЕТСТВУЮЩЕЕ СЛАБЕЙШЕЕ ПРЕДУСЛОВИЕ 
$\wp(S, R))$. фЛЯ ФИКСИРОВАННОЙ КОНСТРУКЦИИ $S$ ТАКОЕ 
ПРАВИЛО, КОТОРОЕ ПО ЗАДАННОМУ ПРЕДИКАТУ $R$, ОЗНАЧАЮЩЕМУ 
ПОСТУСЛОВИЕ, ВЫРАБАТЫВАЕТ ПРЕДИКАТ $\wp(S, R)$, ОЗНАЧАЮЩИЙ 
СООТВЕТСТВУЮЩЕЕ СЛАБЕЙШЕЕ ПРЕДУСЛОВИЕ, НАЗЫВАЕТСЯ 
"ПРЕОБРАЗОВАТЕЛЕМ ПРЕДИКАТОВ". ъОГДА МЫ ПРОСИМ, ЧТОБЫ НАМ 
СООБЩИЛИ ОПИСАНИЕ СЕМАНТИКИ КОНСТРУКЦИИ S, ТО В СУЩНОСТИ 
РЕЧЬ ИДЕТ О СООТВЕТСТВУЮЩЕМ ЭТОЙ КОНСТРУКЦИИ ПРЕОБРАЗОВАТЕЛЕ 
ПРЕДИКАТОВ.

 тО-ВТОРЫХ,--- И Я ЧУВСТВУЮ ИСКУШЕНИЕ ДОБАВИТЬ "БЛАГОДАРЯ 
СУДЬБЕ" --- ЧАСТО НАС НЕ ИНТЕРЕСУЕТ ПОЛНАЯ СЕМАНТИКА 
КОНСТРУКЦИИ. ¤ТО ОБоЯСНЯЕТСЯ ТЕМ, ЧТО МЫ СТРЕМИМСЯ 
ИСПОЛЬЗОВАТЬ КОНСТРУКЦИЮ $S$ ТОЛЬКО ДЛЯ КОНКРЕТНОЙ 
НАДОБНОСТИ, А ТОЧНЕЕ, ДЛЯ ТОГО, ЧТОБЫ ОБЕСПЕЧИТЬ ИСТИННОСТЬ 
ВЕСЬМА КОНКРЕТНОГО ПОСТУСЛОВИЯ $R$, РАДИ КОТОРОГО 
ПРОИЗВОДИЛАСЬ РАЗРАБОТКА КОНСТРУКЦИИ. ш ДАЖЕ ПРИМЕНИТЕЛЬНО К 
ЭТОМУ КОНКРЕТНОМУ ПОСТУСЛОВИЮ $R$ НАС ЧАСТО НЕ ИНТЕРЕСУЕТ 
ТОЧНЫЙ ВИД $\wp(S,R)$; ЗАЧАСТУЮ МЫ УДОВЛЕТВОРЯЕМСЯ БОЛЕЕ 
СИЛЬНЫМ УСЛОВИЕМ $P$, Т. Е. ТАКИМ УСЛОВИЕМ, ДЛЯ КОТОРОГО 
МОЖНО ПОКАЗАТЬ, ЧТО УТВЕРЖДЕНИЕ
$$
P \Rightarrow  \wp(S, R)\qquad\hbox{ ДЛЯ ВСЕХ СОСТОЯНИЙ}\eqno{(3)}
$$
СПРАВЕДЛИВО. (яРЕДИКАТ "$P\Rightarrow Q$" (ЧИТАЕТСЯ "ИЗ $Ё$ СЛЕДУЕТ 
$Q$") ЛОЖЕН ТОЛЬКО В ТЕХ ТОЧКАХ ПРОСТРАНСТВА СОСТОЯНИЙ, ГДЕ 
УСЛОВИЕ $P$ СПРАВЕДЛИВО, a $Q$ НЕ СПРАВЕДЛИВО; ВО ВСЕХ 
ОСТАЛЬНЫХ ТОЧКАХ ОН ИСТИНЕН. ЄРЕБУЯ, ЧТОБЫ УТВЕРЖДЕНИЕ 
"$P \Rightarrow \wp(S,R)$" БЫЛО СПРАВЕДЛИВО ДЛЯ ВСЕХ СОСТОЯНИЙ, МЫ 
ТЕМ САМЫМ ТРЕБУЕМ, ЧТОБЫ ВСЯКИЙ РАЗ КОГДА $P$ --- ИСТИНА, 
УСЛОВИЕ $\wp(S, R)$ ТОЖЕ БЫЛО ИСТИНОЙ; ТОГДА $Ё$ --- 
ДОСТАТОЧНОЕ ПРЕДУСЛОВИЕ. т ТЕОРЕТИКО-МНОЖЕСТВЕННОЙ 
ТЕРМИНОЛОГИИ ЭТО ОЗНАЧАЕТ, ЧТО МНОЖЕСТВО СОСТОЯНИЙ, 
ХАРАКТЕРИЗУЕМОЕ УСЛОВИЕМ $P$, ЯВЛЯЕТСЯ ПОДМНОЖЕСТВОМ ТОГО 
МНОЖЕСТВА СОСТОЯНИЙ, КОТОРОЕ ХАРАКТЕРИЗУЕТСЯ УСЛОВИЕМ 
$\wp(S, R)$.) хСЛИ ДЛЯ ЗАДАННЫХ $Ё$, $S$ И $R$ ОТНОШЕНИЕ (3) 
ВЫПОЛНЯЕТСЯ, ЭТО ЧАСТО МОЖНО ДОКАЗАТЬ, НЕ ПРИБЕГАЯ К ТОЧНОЙ 
ФОРМУЛИРОВКЕ,--- ИЛИ, ЕСЛИ ВАМ ТАК БОЛЬШЕ НРАВИТСЯ, 
"ВЫЧИСЛЕНИЮ" ИЛИ "ВЫВОДУ" --- ПРЕДИКАТА $\wp(S,R)$. ш ЭТО 
ОТРАДНОЕ ОБСТОЯТЕЛЬСТВО, ПОСКОЛЬКУ, ЗА ИСКЛЮЧЕНИЕМ 
ТРИВИАЛЬНЫХ СЛУЧАЕВ, СЛЕДУЕТ ОЖИДАТЬ, ЧТО ЯВНАЯ ФОРМУЛИРОВКА 
УСЛОВИЯ $\wp(S,R)$ ПРЕВЫСИТ ПО КРАЙНЕЙ МЕРЕ РЕЗЕРВ НАШЕЙ 
ПИСЧЕЙ БУМАГИ, НАШЕГО ТЕРПЕНИЯ ИЛИ НАШЕЙ (АНАЛИТИЧЕСКОЙ) 
ИЗОБРЕТАТЕЛЬНОСТИ (ИЛИ КАКУЮ-ТО КОМБИНАЦИЮ ЭТИХ РЕЗЕРВОВ).

ёМЫСЛ $\wp(S, R)$, Т. Е. "СЛАБЕЙШЕГО ПРЕДУСЛОВИЯ ДЛЯ 
НАЧАЛЬНОГО СОСТОЯНИЯ, ПРИ КОТОРОМ ЗАПУСК ОБЯЗАТЕЛЬНО 
ПРИВЕДЕТ К СОБЫТИЮ ПРАВИЛЬНОГО ЗАВЕРШЕНИЯ, ПРИЧЕМ СИСТЕМА 
$S$ ОСТАНЕТСЯ В КОНЕЧНОМ СОСТОЯНИИ, УДОВЛЕТВОРЯЮЩЕМ 
ПОСТУСЛОВИЮ $R$" ПОЗВОЛЯЕТ НАМ УСТАНОВИТЬ, ЧТО 
ПРЕОБРАЗОВАТЕЛЬ ПРЕДИКАТОВ, РАССМАТРИВАЕМЫЙ КАК ФУНКЦИЯ ОТ 
ПОСТУСЛОВИЯ $R$, ОБЛАДАЕТ РЯДОМ ОПРЕДЕЛЕННЫХ СВОЙСТВ.

{\sl ёВОЙСТВО 1.} фЛЯ ЛЮБОЙ КОНСТРУКЦИИ $S$ МЫ ИМЕЕМ
$$
\wp(S,F)=F \eqno{(4)}
$$

яРЕДПОЛОЖИМ, ЧТО ОКАЗАЛОСЬ НЕ ТАК; ПРИ ЭТОМ НАШЛОСЬ ХОТЬ ОДНО СОСТОЯНИЕ, 
УДОВЛЕТВОРЯЮЩЕЕ УСЛОВИЮ $\wp(S,F)$. тОЗЬМЕМ ТАКОЕ СОСТОЯНИЕ В КАЧЕСТВЕ 
НАЧАЛЬНОГО СОСТОЯНИЯ ДЛЯ КОНСТРУКЦИИ $S$. ЄОГДА, СОГЛАСНО НАШЕМУ 
ОПРЕДЕЛЕНИЮ, ЗАПУСК ПРИВЕЛ БЫ К СОБЫТИЮ ПРАВИЛЬНОГО ЗАВЕРШЕНИЯ, ПРИЧЕМ 
СИСТЕМА ОСТАЛАСЬ БЫ В КОНЕЧНОМ СОСТОЯНИИ, УДОВЛЕТВОРЯЮЩЕМ ПРЕДИКАТУ $F$. 
эО ЗДЕСЬ ВОЗНИКАЕТ ПРОТИВОРЕЧИЕ, ТАК КАК ПО ОПРЕДЕЛЕНИЮ ПРЕДИКАТА $F$ НЕ 
СУЩЕСТВУЕТ СОСТОЯНИЙ, УДОВЛЕТВОРЯЮЩИХ $F$; ТЕМ САМЫМ ДОКАЗАНО ОТНОШЕНИЕ 
(4). ёВОЙСТВО 1 ИЗВЕСТНО ТАКЖЕ ПОД НАЗВАНИЕМ "ЗАКОН ИСКЛЮЧЕННОГО ЧУДА".

{\sl ёВОЙСТВО 2.} фЛЯ ЛЮБОЙ КОНСТРУКЦИИ $S$ И ЛЮБЫХ ПОСТУСЛОВИЙ $Q$ И 
$R$, ТАКИХ, ЧТО
$$
Q \Rightarrow R\qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$
СПРАВЕДЛИВО ТАКЖЕ ОТНОШЕНИЕ
$$
\wp(S,Q) \Rightarrow\wp(S, R)\qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}\eqno{(6)}
$$
т САМОМ ДЕЛЕ, ПРИ ЛЮБОМ НАЧАЛЬНОМ СОСТОЯНИИ, УДОВЛЕТВОРЯЮЩЕМ $\wp(S,Q)$, 
СОГЛАСНО ОПРЕДЕЛЕНИЮ, ПО ОКОНЧАНИИ РАБОТЫ СИСТЕМЫ БУДЕТ ОБЕСПЕЧЕНА 
ИСТИННОСТЬ $Q$. ё УЧЕТОМ ОТНОШЕНИЯ (5) ТЕМ САМЫМ БУДЕТ ОБЕСПЕЧЕНА И 
ИСТИННОСТЬ $R$. ёЛЕДОВАТЕЛЬНО, ДАННОЕ НАЧАЛЬНОЕ СОСТОЯНИЕ БУДЕТ 
ОДНОВРЕМЕННО УДОВЛЕТВОРЯТЬ И УСЛОВИЮ $\wp(S,R)$, КАК ЗАПИСАНО В (6). 
ёВОЙСТВО 2 --- ЭТО СВОЙСТВО МОНОТОННОСТИ.

{\sl ёВОЙСТВО 3.} фЛЯ ЛЮБОЙ КОНСТРУКЦИИ $S$ И ДЛЯ ЛЮБЫХ ПОСТУСЛОВИЙ $Q$ 
И $R$ СПРАВЕДЛИВО
$$
(\wp(S, Q) \and \wp(S,R))=\wp(S,Q\and R) \eqno{(7)}
$$

т ЛЮБОЙ ТОЧКЕ ПРОСТРАНСТВА СОСТОЯНИЙ ИЗ ЛЕВОЙ ЧАСТИ ОТНОШЕНИЯ (7)  
ЛОГИЧЕСКИ СЛЕДУЕТ ЕГО ПРАВАЯ ЧАСТЬ ПОТОМУ, ЧТО ДЛЯ ЛЮБОГО НАЧАЛЬНОГО 
СОСТОЯНИЯ, УДОВЛЕТВОРЯЮЩЕГО $\wp(S,Q)$, И $\wp(S,R)$, МЫ ЗНАЕМ В 
СОВОКУПНОСТИ, ЧТО УСТАНОВИТСЯ КОНЕЧНОЕ СОСТОЯНИЕ, УДОВЛЕТВОРЯЮЩЕЕ И $Q$, 
И $R$. фАЛЕЕ, ПОСКОЛЬКУ, В СИЛУ ОПРЕДЕЛЕНИЯ,
$$
(Q \and R) \Rightarrow Q \qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$
СВОЙСТВО 2 ПОЗВОЛЯЕТ НАМ ЗАКЛЮЧИТЬ, ЧТО
$$
\wp(S, Q \and R)\Rightarrow\wp(S, Q)\qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$
И АНАЛОГИЧНО 
$$
\wp(S, Q \and R) \Rightarrow \wp(S, R)\qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$

юДНАКО ИЗ $A\Rightarrow B$ И $A\Rightarrow C$, СОГЛАСНО ИСЧИСЛЕНИЮ ПРЕДИКАТОВ, 
МОЖНО ВЫВЕСТИ, ЧТО $A\Rightarrow(B\and C)$. яОЭТОМУ ПРАВАЯ ЧАСТЬ ОТНОШЕНИЯ (7) 
ЛОГИЧЕСКИ СЛЕДУЕТ ИЗ ЕГО ЛЕВОЙ ЧАСТИ В ЛЮБОЙ ТОЧКЕ ПРОСТРАНСТВА 
СОСТОЯНИЙ. яОСКОЛЬКУ ОБЕ ЧАСТИ ВСЮДУ СЛЕДУЮТ ДРУГ ИЗ ДРУГА, ОНИ ДОЛЖНЫ 
БЫТЬ РАВНЫ, А ТЕМ САМЫМ ДОКАЗАНО СВОЙСТВО 3.

{\sl ёВОЙСТВО 4.} фЛЯ ЛЮБОЙ КОНСТРУКЦИИ $S$ И ЛЮБЫХ ПОСТУСЛОВИЙ $Q$ И 
$R$ СПРАВЕДЛИВО
$$
(\wp(S,Q)\or \wp(S, R))\Rightarrow \wp(S,Q \or R) \qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
\eqno{(8)}
$$

яОСКОЛЬКУ, В СИЛУ ОПРЕДЕЛЕНИЯ, 
$$
Q \Rightarrow(Q \or R)\qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$
СВОЙСТВО 2 ПОЗВОЛЯЕТ НАМ ПРИЙТИ К ЗАКЛЮЧЕНИЮ, ЧТО 
$$
 \wp(S,Q) \Rightarrow \wp(S, Q \or R)\qquad\hbox{ ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$
И АНАЛОГИЧНО 
$$
\wp(S,R) \Rightarrow\wp(S, Q \or R)\qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
$$

эО, СОГЛАСНО ИСЧИСЛЕНИЮ ВЫСКАЗЫВАНИЙ, ИЗ $A \Rightarrow C$ 
И~$B\Rightarrow C$ МОЖНО 
ЗАКЛЮЧИТЬ, ЧТО $(A\or B)\Rightarrow C$, И ЭТИМ ДОКАЗАНА СПРАВЕДЛИВОСТЬ 
СООТНОШЕНИЯ (8). тООБЩЕ ГОВОРЯ, СЛЕДОВАНИЕ В ОБРАТНОМ НАПРАВЛЕНИИ НЕ 
ИМЕЕТ МЕСТА. ЄАК ПРО ЖЕНЩИНУ, КОТОРАЯ ЖДЕТ РЕБЕНКА, НЕВЕРНО УТВЕРЖДЕНИЕ, 
ЧТО ОНА РОДИТ ОБЯЗАТЕЛЬНО СЫНА И НЕВЕРНО УТВЕРЖДЕНИЕ, ЧТО ОНА РОДИТ 
ОБЯЗАТЕЛЬНО ДОЧЬ; ОДНАКО С АБСОЛЮТНОЙ УВЕРЕННОСТЬЮ МОЖНО УТВЕРЖДАТЬ, ЧТО 
ОНА РОДИТ СЫНА ИЛИ ДОЧЬ. тПРОЧЕМ, ДЛЯ ДЕТЕРМИНИРОВАННЫХ КОНСТРУКЦИЙ 
СПРАВЕДЛИВО СЛЕДУЮЩЕЕ, БОЛЕЕ СИЛЬНОЕ СВОЙСТВО.

{\sl ёВОЙСТВО 4'.}  фЛЯ ЛЮБОЙ ДЕТЕРМИНИРОВАННОЙ КОНСТРУКЦИИ $S$ И ЛЮБЫХ 
ПОСТУСЛОВИЙ $Q$ И $R$ СПРАВЕДЛИВО
$$
(\wp(S, Q) \or \wp(S, R)) \Rightarrow \wp (S, Q \or R)
$$

эАМ НУЖНО ПОКАЗАТЬ, ЧТО СЛЕДОВАНИЕ ВЫПОЛНЯЕТСЯ И В ЛЕВУЮ  СТОРОНУ. 
ЁАССМОТРИМ КАКОЕ-ТО НАЧАЛЬНОЕ СОСТОЯНИЕ, УДОВЛЕТВОРЯЮЩЕЕ 
$\wp(S, Q \or R)$, ЭТОМУ НАЧАЛЬНОМУ СОСТОЯНИЮ СООТВЕТСТВУЕТ 
\emph{ЕДИНСТВЕННОЕ} КОНЕЧНОЕ СОСТОЯНИЕ, УДОВЛЕТВОРЯЮЩЕЕ ЛИБО $Q$, ЛИБО 
$R$, ЛИБО ОБОИМ УСЛОВИЯМ; СЛЕДОВАТЕЛЬНО, ДАННОЕ НАЧАЛЬНОЕ СОСТОЯНИЕ 
ДОЛЖНО УДОВЛЕТВОРЯТЬ ЛИБО $\wp(S, Q)$, ЛИБО $\wp(S, R)$, ЛИБО ОБОИМ 
УСЛОВИЯМ СООТВЕТСТВЕННО, Т. Е. ОН ДОЛЖНО УДОВЛЕТВОРЯТЬ 
$(\wp(S,Q) \or \wp(S,R))$. ш ЭТИМ ДОКАЗАНО СВОЙСТВО 4'.

т ЭТОЙ КНИГЕ Я БУДУ --- И ЭТО МОЖЕТ ОКАЗАТЬСЯ ОДНОЙ ИЗ ЕЕ ОТЛИЧИТЕЛЬНЫХ 
ОСОБЕННОСТЕЙ --- РАССМАТРИВАТЬ НЕДЕТЕРМИНИРОВАННОСТЬ КАК ПРАВИЛО, А 
ДЕТЕРМИНИРОВАННОСТЬ КАК ИСКЛЮЧЕНИЕ: ДЕТЕРМИНИРОВАННАЯ МАШИНА БУДЕТ 
РАССМАТРИВАТЬСЯ КАК ЧАСТНЫЙ СЛУЧАЙ НЕДЕТЕРМИНИРОВАННОЙ, КАК КОНСТРУКЦИЯ, 
ДЛЯ КОТОРОЙ СПРАВЕДЛИВО СВОЙСТВО 4' А НЕ ТОЛЬКО БОЛЕЕ СЛАБОЕ СВОЙСТВО 4. 
ЄАКОЕ РЕШЕНИЕ ОТРАЖАЕТ КОРЕННОЕ ИЗМЕНЕНИЕ В МОЕМ МИРОВОЗЗРЕНИИ. т 
1958~Г. Я БЫЛ ОДНИМ ИЗ ПЕРВЫХ, КТО РАЗРАБАТЫВАЛ БАЗОВОЕ ПРОГРАММНОЕ 
ОБЕСПЕЧЕНИЕ ДЛЯ МАШИНЫ С ПРЕРЫВАНИЯМИ ВВОДА-ВЫВОДА, И 
НЕВОСПРОИЗВОДИМОСТЬ ПОВЕДЕНИЯ ТАКОЙ ВО ВСЕХ ОТНОШЕНИЯХ 
НЕДЕТЕРМИНИРОВАННОЙ МАШИНЫ ЯВИЛАСЬ ГОРЕСТНЫМ ОБСТОЯТЕЛЬСТВОМ. ъОГДА 
ВПЕРВЫЕ БЫЛА ПРЕДЛОЖЕНА ИДЕЯ ПРЕРЫВАНИЙ ВВОДА-ВЫВОДА, МЕНЯ НАСТОЛЬКО 
ПУГАЛА САМА МЫСЛЬ О НЕОБХОДИМОСТИ РАЗРАБАТЫВАТЬ НАДЕЖНОЕ ПРОГРАММНОЕ 
ОБЕСПЕЧЕНИЕ ДЛЯ ТАКОГО НЕУКРОТИМОГО ЗВЕРЯ, ЧТО Я ОТТЯГИВАЛ ПРИНЯТИЕ 
РЕШЕНИЯ О ДОПУЩЕНИИ ТАКИХ ПРЕРЫВАНИЙ ПО КРАЙНЕЙ МЕРЕ В ТЕЧЕНИЕ ТРЕХ 
МЕСЯЦЕВ. ш ДАЖЕ ПОСЛЕ ТОГО, КАК Я СДАЛСЯ (МОЕ СОПРОТИВЛЕНИЕ СЛОМИЛИ 
ЛЕСТЬЮ), ЧУВСТВОВАЛ Я СЕБЯ ВЕСЬМА НЕУЮТНО: ВЕДЬ ОШИБКА В ПРОГРАММЕ 
СПОСОБНА ВЫЗВАТЬ НЕСУРАЗНОЕ ПОВЕДЕНИЕ СИСТЕМЫ, СТОЛЬ СХОДНОЕ С 
НЕВОСПРОИЗВОДИМЫМ МАШИННЫМ СБОЕМ. ъРОМЕ ТОГО,--- И ЭТО В ТО ВРЕМЯ, КОГДА 
ДЛЯ ДЕТЕРМИНИРОВАННЫХ МАШИН МЫ ВСЕ ЕЩЕ ПОЛАГАЛИСЬ НА "ОТЛАДКУ",--- С 
САМОГО НАЧАЛА БЫЛО СОВЕРШЕННО ОЧЕВИДНО, ЧТО ТЕСТИРОВАНИЕ ПРОГРАММ 
ОКАЗЫВАЛОСЬ ТЕПЕРЬ СОВСЕМ НЕПРИГОДНЫМ СРЕДСТВОМ ДЛЯ ДОСТИЖЕНИЯ ДОЛЖНОГО 
УРОВНЯ НАДЕЖНОСТИ.

т ТЕЧЕНИЕ МНОГИХ ЛЕТ ВПОСЛЕДСТВИИ Я ОТНОСИЛСЯ К НЕВОСПРОИЗВОДИМОСТИ 
ПОВЕДЕНИЯ НЕДЕТЕРМИНИРОВАННОЙ МАШИНЫ КАК К ДОБАВОЧНОМУ ОСЛОЖНЕНИЮ, 
КОТОРОГО СЛЕДУЕТ ИЗБЕГАТЬ ЛЮБЫМИ СПОСОБАМИ. яРЕРЫВАНИЯ БЫЛИ ДЛЯ МЕНЯ НЕ 
ЧЕМ ИНЫМ, КАК ЗЛЫМИ КОЗНЯМИ ИНЖЕНЕРОВ ПО АППАРАТУРЕ ПРОТИВ БЕДНЫХ 
РАЗРАБОТЧИКОВ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ. шЗ ЭТОГО МОЕГО СТРАХА РОДИЛАСЬ 
ДИСЦИПЛИНА "ГАРМОНИЧЕСКИ ВЗАИМОДЕЙСТВУЮЩИХ ПОСЛЕДОВАТЕЛЬНЫХ ПРОЦЕССОВ". 
эЕСМОТРЯ НА ЕЕ УСПЕХ, МОИ ОПАСЕНИЯ СОХРАНЯЛИСЬ, ПОСКОЛЬКУ НАШИ РЕШЕНИЯ
--- ХОТЬ БЫ И С ДОКАЗАННОЙ ПРАВИЛЬНОСТЬЮ --- ПРЕДСТАВЛЯЛИСЬ ЧАСТНЫМИ 
РЕШЕНИЯМИ ПРОБЛЕМЫ "УКРОЩЕНИЯ" (ИМЕННО ТАК  МЫ  ЭТО ВОСПРИНИМАЛИ!) 
КОНКРЕТНЫХ ВИДОВ НЕДЕТЕРМИНИРОВАННОСТИ. юСНОВАНИЕМ ДЛЯ МОЕГО СТРАХА БЫЛО 
ОТСУТСТВИЕ ОБЩЕЙ МЕТОДОЛОГИИ.

ё ТЕХ ПОР ДВА ОБСТОЯТЕЛЬСТВА ИЗМЕНИЛИ КАРТИНУ. яЕРВОЕ ВОЗНИКЛО С 
ПОНИМАНИЕМ ТОГО, ЧТО ДАЖЕ В СЛУЧАЕ ПОЛНОСТЬЮ ДЕТЕРМИНИРОВАННЫХ МАШИН 
ПОЛЕЗНОСТЬ ТЕСТИРОВАНИЯ ПРОГРАММ ОКАЗЫВАЕТСЯ СОМНИТЕЛЬНОЙ. ъАК Я УЖЕ 
МНОГО paЗ ГОВОРИЛ И ВО МНОГИХ МЕСТАХ ПИСАЛ, ТЕСТИРОВАНИЕ ПРОГРАММЫ МОЖЕТ 
ВПОЛНЕ ЭФФЕКТИВНО СЛУЖИТЬ ДЛЯ ДЕМОНСТРАЦИИ НАЛИЧИЯ В НЕЙ ОШИБОК, НО, К 
СОЖАЛЕНИЮ, НЕПРИГОДНО ДЛЯ ДОКАЗАТЕЛЬСТВА ИХ ОТСУТСТВИЯ. фРУГИМ 
ПРОЯСНИВШИМСЯ ТЕМ ВРЕМЕНЕМ ОБСТОЯТЕЛЬСТВОМ ЯВИЛОСЬ ОБНАРУЖЕНИЕ 
НЕОБХОДИМОСТИ ТОГО, ЧТОБЫ ВСЯКАЯ ДИСЦИПЛИНА ПРОЕКТИРОВАНИЯ ДОЛЖНЫМ 
ОБРАЗОМ УЧИТЫВАЛА ТОТ ФАКТ, ЧТО САМО ПРОЕКТИРОВАНИЕ КОНСТРУКЦИИ, 
ПРЕДНАЗНАЧЕННОЙ ДЛЯ КАКОЙ-ТО ЦЕЛИ, ТОЖЕ ДОЛЖНО БЫТЬ ЦЕЛЕНАПРАВЛЕННОЙ 
ДЕЯТЕЛЬНОСТЬЮ. т НАШЕМ КОНКРЕТНОМ СЛУЧАЕ ЭТО ОЗНАЧАЕТ ЕСТЕСТВЕННОСТЬ 
ПРЕДПОЛОЖЕНИЯ, ЧТО ОТПРАВНОЙ ТОЧКОЙ ДЛЯ ПРОЕКТНЫХ РАССМОТРЕНИЙ БУДЕТ 
СЛУЖИТЬ ЗАДАННОЕ ПОСТУСЛОВИЕ. т КАКОМ-ТО СМЫСЛЕ МЫ БУДЕМ "РАБОТАТЬ 
ВСПЯТЬ". фЕЙСТВУЯ ТАК, МЫ ОБНАРУЖИМ, ЧТО ВЕСЬМА СУЩЕСТВЕННЫМ ОКАЗЫВАЕТСЯ 
СЛЕДОВАНИЕ ИЗ СВОЙСТВА 4, ТОГДА КАК ОТ РАВЕНСТВА ИЗ СВОЙСТВА 4' МЫ 
ПОЛУЧИМ ОЧЕНЬ МАЛО ПОЛЬЗЫ.

ъАК ТОЛЬКО МЫ РАЗРАБОТАЛИ МАТЕМАТИЧЕСКИЙ АППАРАТ, ПОЗВОЛЯЮЩИЙ 
ПРОЕКТИРОВАТЬ НЕДЕТЕРМИНИРОВАННЫЕ КОНСТРУКЦИИ, ДОСТИГАЮЩИЕ ЦЕЛИ, 
НЕДЕТЕРМИНИРОВАННАЯ МАШИНА ПЕРЕСТАЕТ НАС ПУГАТЬ. эАПРОТИВ! ьЫ НАУЧИМСЯ 
ДАЖЕ ЦЕНИТЬ ЕЕ КАК ВАЖНУЮ СТЕПЕНЬ НА ПУТИ РАЗРАБОТКИ ПРОЕКТА В КОНЕЧНОМ 
ИТОГЕ ПОЛНОСТЬЮ ДЕТЕРМИНИРОВАННОЙ КОНСТРУКЦИИ.

(яОСЛЕДУЮЩАЯ ЧАСТЬ ЭТОЙ ГЛАВЫ МОЖЕТ БЫТЬ ПРОПУЩЕНА ПРИ ПЕРВОМ ЧТЕНИИ.) 
ЁАНЕЕ МЫ ДОГОВОРИЛИСЬ, ЧТО ПРЕДСТАВЛЯЕМ ФУНКЦИОНИРОВАНИЕ КОНСТРУКЦИИ $S$ 
ДОСТАТОЧНО ХОРОШО, ЕСЛИ ТОЛЬКО ЗНАЕМ, КАК СООТВЕТСТВУЮЩИЙ ЕЙ 
ПРЕОБРАЗОВАТЕЛЬ ПРЕДИКАТОВ $\wp(S,R)$ ДЕЙСТВУЕТ НАД ЛЮБЫМ ПОСТУСЛОВИЕМ 
$R$. хСЛИ НАМ ИЗВЕСТНО ТАКЖЕ, ЧТО ДАННАЯ КОНСТРУКЦИЯ ДЕТЕРМИНИРОВАНА, ТО 
ЗНАНИЕ ЭТОГО ПРЕОБРАЗОВАТЕЛЯ ПРЕДИКАТОВ ПОЛНОСТЬЮ ОПРЕДЕЛЯЕТ ВОЗМОЖНОЕ 
ПОВЕДЕНИЕ КОНСТРУКЦИИ. фЛЯ ДЕТЕРМИНИРОВАННОЙ КОНСТРУКЦИИ $S$ И 
НЕКОТОРОГО ПОСТУСЛОВИЯ $R$ ВСЯКОЕ НАЧАЛЬНОЕ СОСТОЯНИЕ ПОПАДАЕТ В ОДНО ИЗ 
ТРЕХ НЕПЕРЕСЕКАЮЩИХСЯ МНОЖЕСТВ В СООТВЕТСТВИИ СО СЛЕДУЮЩИМИ ВЗАИМНО 
ИСКЛЮЧАЮЩИМИ ВОЗМОЖНОСТЯМИ:

(А) чАПУСК КОНСТРУКЦИИ $S$ ПРИВЕДЕТ К КОНЕЧНОМУ СОСТОЯНИЮ, 
УДОВЛЕТВОРЯЮЩЕМУ $R$.

(Б) чАПУСК КОНСТРУКЦИИ $S$ ПРИВЕДЕТ К КОНЕЧНОМУ СОСТОЯНИЮ, 
УДОВЛЕТВОРЯЮЩЕМУ $\non R$.

(В) чАПУСК КОНСТРУКЦИИ $S$ НЕ ПРИВЕДЕТ К КАКОМУ БЫ ТО НИ БЫЛО КОНЕЧНОМУ 
СОСТОЯНИЮ, Т. Е. РАБОТА НЕ СМОЖЕТ ЗАВЕРШИТЬСЯ ПРАВИЛЬНЫМ ОБРАЗОМ.

яЕРВОЕ МНОЖЕСТВО ХАРАКТЕРИЗУЕТСЯ ВЫРАЖЕНИЕМ $\wp(S, R)$, ВТОРОЕ 
МНОЖЕСТВО --- ВЫРАЖЕНИЕМ $\wp(S, \non R)$, ИХ ОБоЕДИНЕНИЕ --- 
ВЫРАЖЕНИЕМ $(\wp(S,R)\or\wp(S,\non R))=\wp(S,R\or\non R)=\wp(S,T)$
А СЛЕДОВАТЕЛЬНО, ТРЕТЬЕ МНОЖЕСТВО ХАРАКТЕРИЗУЕТСЯ ВЫРАЖЕНИЕМ 
$\non\wp(S,T)$.

ЄРУДНЕЕ ДАТЬ ПОЛНУЮ СЕМАНТИЧЕСКУЮ ХАРАКТЕРИСТИКУ НЕДЕТЕРМИНИРОВАННОЙ 
СИСТЕМЫ. яО ОТНОШЕНИЮ К ЛЮБОМУ ЗАДАННОМУ ПОСТУСЛОВНЮ $R$ МЫ СНОВА ИМЕЕМ 
ТРИ ВОЗМОЖНЫХ ТИПА СОБЫТИЙ, КАК ПЕРЕЧИСЛЕНО ВЫШЕ В ПУНКТАХ (А), (Б) И 
(В). юДНАКО В СЛУЧАe НЕДЕТЕРМИНИРОВАННОЙ СИСТЕМЫ ОДНО И ТО ЖЕ НАЧАЛЬНОЕ 
СОСТОЯНИЕ НЕ ОБЯЗАТЕЛЬНО ПРИВОДИТ К ЕДИНСТВЕННОМУ СОБЫТИЮ, КОТОРОЕ ПО 
ОПРЕДЕЛЕНИЮ ОТНОСИЛОСЬ БЫ К ОДНОМУ ИЗ ТРЕХ ВЗАИМНО ИСКЛЮЧАЮЩИХ ТИПОВ; 
ДЛЯ ЛЮБОГО НАЧАЛЬНОГО СОСТОЯНИЯ ВОЗМОЖНЫЕ СОБЫТИЯ МОГУТ ТЕПЕРЬ 
ОТНОСИТЬСЯ К ОДНОМУ, ДВУМ ИЛИ ДАЖЕ КО ВСЕМ ТРЕМ ТИПАМ.

ўТОБЫ ОПИСЫВАТЬ ТАКИЕ СИТУАЦИИ, МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ ПОНЯТИЕ 
"СВОБОДНОГО ПРЕДУСЛОВИЯ". ЁАНЕЕ МЫ РАССМОТРИВАЛИ ТАКИЕ ПРЕДУСЛОВИЯ, ПРИ 
КОТОРЫХ ГАРАНТИРОВАЛАСЬ ДОСТИЖИМОСТЬ "ПРАВИЛЬНОГО РЕЗУЛЬТАТА", Т. Е. 
КОНЕЧНОГО СОСТОЯНИЯ, УДОВЛЕТВОРЯЮЩЕГО $R$. ёВОБОДНОЕ ПРЕДУСЛОВИЕ 
ЯВЛЯЕТСЯ БОЛЕЕ СЛАБЫМ: ОНО ГАРАНТИРУЕТ ТОЛЬКО, ЧТО СИСТЕМА НЕ ВЫДАСТ 
НЕПРАВИЛЬНОГО РЕЗУЛЬТАТА, Т. Е. НЕ ДОСТИГНЕТ ТАКОГО КОНЕЧНОГО СОСТОЯННЯ, 
КОТОРОЕ НЕ УДОВЛЕТВОРЯЛО БЫ $R$, ОДНАКО НЕ ИСКЛЮЧАЕТСЯ ВОЗМОЖНОСТЬ 
НЕЗАВЕРШЕНИЯ РАБОТЫ СИСТЕМЫ. рНАЛОГИЧНО И ДЛЯ СВОБОДНЫХ ПРЕДУСЛОВИЙ МЫ 
МОЖЕМ ВВЕСТИ ПОНЯТИЕ "СЛАБЕЙШЕГО СВОБОДНОГО ПРЕДУСЛОВИЯ"; ОБОЗНАЧИМ ЕГО 
ЧЕРЕЗ $\wlp(S,R)$, яРИ ЭТОМ ПРОСТРАНСТВО НАЧАЛЬНЫХ СОСТОЯНИЙ 
ПОДРАЗДЕЛЯЕТСЯ В ПРИНЦИПЕ НА СЕМЬ ВЗАИМНО НЕПЕРЕСЕКАЮЩИХСЯ ОБЛАСТЕЙ, НИ 
ОДНА ИЗ КОТОРЫХ НЕ ОБЯЗАНА БЫТЬ ПУСТОЙ. (шХ СЕМЬ, ПОТОМУ ЧТО ИЗ ТРЕХ 
ОБоЕКТОВ МОЖНО СДЕЛАТЬ СЕМЬ НЕПУСТЫХ ВЫБОРОК.) тСЕ ОНИ ЛЕГКО 
ХАРАКТЕРИЗУЮТСЯ ТРЕМЯ ПРЕДИКАТАМИ: $\wlp(S,R)$, $\wlp(S,\non R)$ И 
$\wp(S,T)$.
$$
\wp(S, R) = (\wlp (S, R) \and \wp(S, T) )\leqno{(А)}
$$
чАПУСК ОБЕСПЕЧИТ ИСТИННОСТЬ R.
$$
 \wp(S, \non R) = (\wlp (S, \non R) \and \wp(S, T)) \leqno{(Б)}
$$
чАПУСК ОБЕСПЕЧИТ ИСТИННОСТЬ $\non R$.
$$
 \wlp (S, F) = (\wlp (S, R) \and \wlp (S, \non R)) \leqno{(В)}
$$
чАПУСК НЕ СМОЖЕТ ПРИВЕСТИ К ПРАВИЛЬНО ЗАВЕРШАЕМОЙ РАБОТЕ 
$$
 \wp(S, T) \and \non \wlp(S, R) \and \non \wlp(S, \non R)\leqno{(АБ)}
$$
чАПУСК ПРИВЕДЕТ К ЗАВЕРШАЕМОЙ РАБОТЕ, НО ПО НАЧАЛЬНОМУ СТОЯНИЮ НЕЛЬЗЯ 
ОПРЕДЕЛИТЬ, БУДЕТ ЛИ КОНЕЧНОЕ СОСТОЯНИЕ УДОВЛЕТВОРЯТЬ УСЛОВИЮ $R$ ИЛИ 
НЕТ.
$$
 \wlp (S,R) \and \non \wp(S, Є)\leqno{(АВ)}
$$
хСЛИ ЗАПУСК ПРИВОДИТ К КАКОМУ-ТО КОНЕЧНОМУ СОСТОЯНИЮ, ТАКОЕ КОНЕЧНОЕ 
СОСТОЯНИЕ БУДЕТ УДОВЛЕТВОРЯТЬ $R$, НО ПО НАЧАЛЬНОМУ СОСТОЯНИЮ НЕЛЬЗЯ 
ОПРЕДЕЛИТЬ, ЗАВЕРШИТСЯ ЛИ РАБОТА СИСТЕМЫ.
$$
 \wlp (S, \non R) \and \non \wp (S, T)\leqno{(БВ)}
$$
хСЛИ ЗАПУСК ПРИВОДИТ К КАКОМУ-ТО КОНЕЧНОМУ СОСТОЯНИЮ, ТАКОЕ КОНЕЧНОЕ 
СОСТОЯНИЕ НЕ БУДЕТ УДОВЛЕТВОРЯТЬ $R$, НО ПО НАЧАЛЬНОМУ СОСТОЯНИЮ НЕЛЬЗЯ 
ОПРЕДЕЛИТЬ, ЗАВЕРШИТСЯ ЛИ РАБОТА СИСТЕМЫ. 
$$
 \non (\wlp(S, R) \or \wlp(S, \non R) \or \wp(S, T)\leqno{(АБВ)}
$$
яО НАЧАЛЬНОМУ СОСТОЯНИЮ НЕЛЬЗЯ ОПРЕДЕЛИТЬ, ПРИВЕДЕТ ЛИ ЗАПУСК К 
ЗАВЕРШАЕМОЙ РАБОТЕ, А В СЛУЧАЕ ЗАВЕРШАЕМОСТИ НЕЛЬЗЯ ОПРЕДЕЛИТЬ, БУДЕТ ЛИ 
УДОВЛЕТВОРЯТЬСЯ УСЛОВИЕ $R$.

яОСЛЕДНИЕ ЧЕТЫРЕ ВОЗМОЖНОСТИ СУЩЕСТВУЮТ ТОЛЬКО ДЛЯ НЕДЕТЕРМИРОВАННЫХ 
МАШИН.

шЗ ОПРЕДЕЛЕНИЯ $wlp(S, R)$ СЛЕДУЕТ, ЧТО
$$
\wlp(S, T)=T 
$$
▀СНО ТАКЖЕ, ЧТО
$$
 (\wlp(S,F) \and \wp(S,T))=F
$$

хСЛИ БЫ БЫЛО НЕ ТАК, ТО СУЩЕСТВОВАЛО БЫ НАЧАЛЬНОЕ СОСТОЯНИЕ, ДЛЯ 
КОТОРОГО МОЖНО БЫЛО БЫ ГАРАНТИРОВАТЬ И ЗАВЕРШИМОСТЬ, И НЕЗАВЕРШИМОСТЬ 
РАБОТЫ. эА РИС. 3.1 ДАНО ГРАФИЧЕСКОЕ
$$
//РИС.31
$$
ПРЕДСТАВЛЕНИЕ ПРОСТРАНСТВА  СОСТОЯНИЙ,ПРИЧЕМ ВНУТРЕННИЕ ЧАСТИ  
ПРЯМОУГОЛЬНИКОВ УДОВЛЕТВОРЯЮТ $\wlp (S, R)$, $\wlp(S, \non R)$ И 
$\wp(S, T)$  СООТВЕТСТВЕННО.  

¤ТОТ АНАЛИЗ ПРИВЕДЕН ДЛЯ ПОЛНОТЫ, А ТАКЖЕ ПОТОМУ, ЧТО НА ПРАКТИКЕ 
ПОНЯТИЕ СВОБОДНОГО ПРЕДУСЛОВИЯ ОКАЗЫВАЕТСЯ ВЕСЬМА ПОЛЕЗНЫМ. хСЛИ, 
НАПРИМЕР, КТО-ТО РЕАЛИЗУЕТ ЯЗЫК ПРОГРАММИРОВАНИЯ, ТО ОН НЕ СТАНЕТ 
ДОКАЗЫВАТЬ, ЧТО ПРИ ЭТОЙ РЕАЛИЗАЦИИ ЛЮБАЯ ПРАВИЛЬНАЯ ПРОГРАММА 
ВЫПОЛНЯЕТСЯ ПРАВИЛЬНО. юН БЫЛ БЫ УДОВЛЕТВОРЕН И СЧАСТЛИВ, ЕСЛИ БЫ ТВЕРДО 
ЗНАЛ, ЧТО НИКАКАЯ ПРАВИЛЬНАЯ ПРОГРАММА НЕ БУДЕТ ВЫПОЛНЕНА ПРАВИЛЬНО БЕЗ 
СООТВЕТСТВУЮЩЕГО ПРЕДУПРЕЖДЕНИЯ,--- РАЗУМЕЕТСЯ, ПРИ УСЛОВИИ, ЧТО КЛАСС 
ПРОГРАММ, КОТОРЫЕ НА САМОМ ДЕЛЕ БУДУТ ВЫПОЛНЯТЬСЯ ПРАВИЛЬНО, ДОСТАТОЧНО 
ВЕЛИК ДЛЯ ТОГО, ЧТОБЫ ЭТА РЕАЛИЗАЦИЯ ПРЕДСТАВЛЯЛА КАКОЙ-ТО ИНТЕРЕС.

юДНАКО ПОКА МЫ НЕ БУДЕМ РАССМАТРИВАТЬ ПОНЯТИЕ СВОБОДНОГО ПРЕДУСЛОВИЯ, А 
СОСРЕДОТОЧИМ СВОЕ ВНИМАНИЕ НА СПОСОБЕ ХАРАКТЕРИСТИКИ ТЕХ НАЧАЛЬНЫХ 
СОСТОЯНИЙ, КОТОРЫЕ ГАРАНТИРУЮТ ПОЛУЧЕНИЕ ПРАВИЛЬНОГО РЕЗУЛЬТАТА. ъОГДА 
ТАКОЙ СПОСОБ БУДЕТ РАЗРАБОТАН, МЫ ПОСМОТРИМ, КАК МОЖНО ЕГО ВИДОИЗМЕНИТЬ 
ТАКИМ ОБРАЗОМ, ЧТОБЫ ЭТО ПОЗВОЛИЛО НАМ РАССУЖДАТЬ О СВОБОДНЫХ 
ПРЕДУСЛОВИЯХ В ТОЙ МЕРЕ, В КОТОРОЙ ОНИ НАС ИНТЕРЕСУЮТ.

\bye