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

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

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

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

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

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

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

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

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

}

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

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