Введение в схемы, автоматы и алгоритмы



             

Ветвление (условный оператор)


Машину Тьюринга ? будем называть распознающей, если для некоторого алфавита ? и каждого входа x

?*, на котором ? останавливается, ее результат {?}(x)
{0, 1}, т.е. ? вычисляет некоторую двузначную функцию (возможно частичную) на словах из ?.

Лемма 9.5. Пусть ? - распознающая м.Т., м.Т.

{\cal M}_1
вычисляет функцию f(x), а м.Т.
{\cal M}_2
- функцию g(x). Тогда существует м.Т.
\cal M,\
вычисляющая функцию

h(x) =\left\{ \begin{array}{lcl} f(x) & \mbox { при } & \Phi(x)=0 \\ g(x) & \mbox { при } & \Phi(x)=1 \end{array} \right.

Доказательство. Требуемая м.Т.

\cal M\

вначале копирует вход x и получает на ленте слово x*x, затем вычисляет параллельную композицию функций ?(x) и тождественной функции e(x)=x и переходит в конфигурацию p{?}(x)*x. Выбор между f и g происходит по следующим командам:

\ p 0 \rightarrow p_0 \wedge \textit{ П }; \ \ p1 \rightarrow p_1 \wedge \textit{ П}; \ \ p_0* \rightarrow q_0^1 \wedge \textit{ П}; \ \ p_1* \rightarrow q_0^2 \wedge \textit{ П}

Кроме того, обеспечим переход в новое заключительное состояние:

\ q_f^1 a \rightarrow q_f a \textit{ Н }; \ \ \ q_f^2 a \rightarrow q_f a \textit{ Н}\ \ (a \in \Sigma ).

Таким образом, мы реализовали в терминах машин Тьюринга обычный в языках программирования оператор ветвления:

 \mbox {\bf if }\ \Phi(x)=0\ \mbox {\bf then }\ f(x) \ \mbox {\bf else }\ g(x)\ \mbox {\bf endif }.




Содержание  Назад  Вперед