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

Машину Тьюринга ? будем называть распознающей, если для некоторого алфавита ? и каждого входа 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 }.$

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