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

         

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


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

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

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

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

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

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

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

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



Содержание раздела