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