Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

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

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

}

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

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





Дата публикования: 2015-01-10; Прочитано: 924 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...