1. Главная
  2. Библиотека
  3. Логика
  4. Выяснить, применима ли машина Тьюринга, задаваемая прог...
Решение задачи на тему

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

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

Условие:

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

Решение:

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

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

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

Выбери предмет