Пусть начальной является конфигурация 1q11111

Пример

• Пусть начальной является конфигурация 1q11111.
• Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11q111.
• Такт 2 – аналогичным образом осуществляется переход к конфигурации 111q11.
• Такт 3 – переход к конфигурации 1111q1.
• Такт 4 –переход к конфигурации 11111q
• Такт 5 Обозревается , в ЛУ состояние q. Выходная команда z1S – вместо в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация 111111z.
• Задача решена.

Отличия читающего автомата с выходом и МТ

Тезис Тьюринга

• Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
• Машина Тьюринга - это модель компьютера

жүктеу 1,59 Mb.

Достарыңызбен бөлісу: