Составители:
Рубрика:
q
q q q q q
1 2 3 4 5 6
Λ ⎯ ⎯
1Нq
ΛЛq ΛПq ΛПq
2 4 0 0
1
ΛЛq 1Лq ΛПq 1Лq ΛПq
1Пq
1 3 3 1 5 6
− ⎯ ⎯
1Лq −Лq ΛПq
−Пq
1 5 3 6
Например, вычитание 1111¬111 (три минус два) начинается тремя
циклами, в результате каждого из которых стираются крайние единицы
содержимого ленты. Начальное состояние q
1
поддерживает перемещение
головки вправо до разделителя Λ:
…Λq
1111−111Λ…⇒ . . . …Λ1111−111q Λ… .
1 1
стирается самая правая единица и в состоянии q
Затем в состоянии q
2 3
происходит перемещение головки влево до разделителя Λ:
…Λ1111−111q
Λ…⇒ …Λ1111−11q Λ…⇒ …Λ1111−1q 1Λ…⇒
1 2 3
11Λ…⇒ . . . …Λq
…Λ1111−q
Λ1111−11Λ… .
3 3
Затем в состоянии q
4
стирается самая левая единица и начинается второй цикл:
в состоянии q
1
повторяется перемещение головки вправо до разделителя Λ и
т.д.:
…q
Λ1111−11Λ…⇒…Λq 1111−11Λ…⇒ …Λq 111−11Λ…⇒ … .
3 4 1
Четвертый и последний цикл отличается тем, что, обозревая символ “−” в
состоянии q
, головка заменяет его на “1” и переходит в состояние q
2 5
,
обеспечивающее корректное завершение программы:
…Λq
1−Λ…⇒ …Λ1q −Λ…⇒ …Λ1−q Λ…⇒ …Λ1q −Λ…⇒
1 1 1 2
11Λ…⇒ …q Λ11Λ…⇒…q
…Λ q
11Λ… .
5 5 0
Состояние q
6
предусмотрено для случая, когда вычитаемое больше
уменьшаемого. В этом состоянии головка очищает ленту: перемещается вправо
и стирает все единицы. Встретив разделитель Λ в состоянии q
6
, головка
заменяет его единицей, остается на месте и переходит в заключительное
состояние q
.
0
Приемы программирования машины Тьюринга
Цель настоящего раздела – продемонстрировать универсальные
вычислительные возможности машин Тьюринга. Для этого покажем,
148
Страницы
- « первая
- ‹ предыдущая
- …
- 62
- 63
- 64
- 65
- 66
- …
- следующая ›
- последняя »
