Выяснить, применима ли машина Тьюринга, заданная программой Р, к слову S

Что-то очень подозрительное с Машиной Тьюринга

Здравствуйте! Нужно решить задачу, но не могу вообще понять, как это сделать. Поиск решений в гугле ничего не дал. Впервые сталкиваюсь с машиной тьюринга. Помогите, пожалуйста, решить, по шагам для самых неосведомлённых...

Во вложении какая-то схема, которая была вместе с этим заданием.

"Выяснить, применима ли машина Тьюринга, заданная программой Р к слову S и, если применима, то указать результат применения машины Тьюринга к заданному слову. При решении задачи следует учесть, что в начальный момент времени головка машины обозревает самую левую ячейку на ленте и устройство управления (УУ) находится в начальном состоянии q1"