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

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

?*, на котором ? останавливается, ее результат {?}(x)

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

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

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

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

вычисляющая функцию

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

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

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

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

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