Машина Тьюринга

Дисциплина Математическая логика и теория алгоритмов

Заказчик	strenghellon1 ☆ 3 ✍ 10 ♥ 0
Вид работы	Контрольная
Срок	31.03.2017
Вариант	1
Бюджет	200 ₽

Задание 1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т слову Р. Предполагается, что q1 – начальное состояние, q0 – заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте.
Задание 2.  По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию (q0 – заключительное состояние).
Задание 3. А = {a,b,c}. Пусть Р – непустое слово. Удалить из слова второй символ, если такой существует. Составить машину Тьюринга, реализующую процесс.