Выяснить, применима ли машина Тьюринга, задаваемая программой П, к слову Р. достигнут конец программы, значит, последняя конфигурация является заключительной. Следовательно, машина T к

1) Применяя машину T к слову P, получаем последовательность конфигураций:

Вид второй конфигурации обусловлен тем, что символ 0 считается пустым символом и может не записываться.

Поскольку команда вида в программе отсутствует, то последняя конфигурация является заключительной. Следовательно, машина T к слову P применима,