Операция ветвления (условный оператор).(с32-с33)

Пусть даны две машины Тьюринга Т₁ и Т_2, которые вычисляют соответствующие функции в одном и том же алфавите.

Тогда существует машина Тьюринга Т, которая вычисляет функцию определенную следующим образом

Т.е. нужно уметь вычислять предикат , а значит построить машину Тьюринга Т_p вычисляющую предикат. Вычислять можно двумя способами.

Первый вариант заменить на ленте на 0 или 1, но это очень часто сделать нельзя, т.к. необходимо сохранить входное слово . Поэтому существует второй вариант, так называемое вычисление с восстановлением, дающее в заключительной стандартной конфигурации q₀^p .

Тогда машина Тьюринга Т начальную конфигурацию

Существование машины Т вытекает из следующих конструкций.

Строится МТ Т_p вычисляющая предикат с восстановлением.

Строится промежуточная машина Т₃ с начальным состоянием и системой команд

}

где команды машины Т₁, а машины Т₂ соответственно.

Тогда Т() – это композиция двух машин Т₃(Т_p()).