ВУЗ:
Составители:
следующим образом: |0 = , ||1 = , |||2 = , …,
321
1
*****
=
=
n
n (черта сверху означает
кодированное число).
Построим простейшую МТ, вычисляющую сумму
y
x
+ любых двух
целых неотрицательных чисел. На ленту занесем сначала первое число х, а
затем через пробел (В) - второе число y. Вычисление начнем с крайней левой
позиции, предположив, что машина находится в начальной ситуации q
0
В.
Будем считать, что результат получен, если на ленте осталось столько
палочек, записанных не обязательно подряд, чему равно истинное значение
суммы. Это значение таково:
2
−
+
=
+
yxyx .
Для построения МТ используем следующую процедуру. Сначала
выделяем первую палочку кода
x
и стираем ее. Затем выделяем первую
палочку кода
y
и также стираем ее. В результате на ленте остается столько
палочек, сколько их должно быть в числе
y
x
+
. Заметим, что тот же
результат может быть получен другими способами, например, выделяя и
вычеркивая первую палочку кода
x
и последнюю в коде
y
, две первые в коде
x
и тому подобное. Исходя из этой идеи, можно синтезировать множество
команд, определяющих требуемую МТ. Действительно, по команде q
0
Вlq
1
МТ перейдет из начальной ситуации q
0
В в рабочее состояние q
1
, а в рабочей
ячейке будет находиться первая палочка кода
x
. Далее машина должна
стереть эту палочку. Это выполняется командой q
1
|Вq
1
. Теперь машина
находится в ситуации q
1
В. Сдвиг ленты на одну ячейку влево приведет к
ситуации q
2
|. Это выполняется командой q
1
Вlq
2
. После выполнения команды
q
2
|lq
2
в рабочей ячейке скажется пробел В, предшествующий коду
y
. Сдвиг
ленты влево на дну ячейку по команде q
2
Вlq
3
приведет к ситуации q
3
|.
Команда q
3
|Вq
3
сотрет первую палочку кода
y
. В итоге мы построили
следующую таблица Тьюринга:
1) q
0
Вlq
1
; 4) q
2
|lq
2
;
2) q
1
|Вq
1
; 5) q
2
Вlq
3
;
3) q
1
Вlq
2
; 6) q
3
|Вq
3
,
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
