ВУЗ:
Составители:
{ {
↑
BBВ
xx
21
|...|||...||
и положение головки указано стрелкой. МТ должна сначала перейти от кода
1
х
к числу х
1
и от кода
2
х
к числу х
2
. Это выполняется следующей ДТ: lBrBR
2
.
В результате будет стерта первая палочка в
1
х
и последняя - в
2
х
. Затем
машина копирует число х
2
столько раз, сколько имеется палочек в х
1
. Для
этого используется цикл ,
при котором после стирания очередной палочки в х
1
копируется слово х
2
. Это
выполняет ДТ в прямоугольнике, имеющая вид:
22
KR
B
L . В результате после
того, как будет стерта последняя палочка в х
1
, а ленте будет записана
последовательность
{
{{
BBBBBB
xxx
x
212
1
|...|||...||...
×
↑
. Теперь необходимо стереть число х
2
.
Это выполняет ДТ .
Для перевода головки в крайнее правое положение используем ДТ: L.
Объединяя все приведенные диаграммы в одну, получим ДТ, показанную на
рис. 2.4.
Рис. 2.4
Таким образом, на ленте будет записано число
{
BB
xx
21
|...||
×
. Полученное
построение доказывает вычислимость функции
2121
),( хxхxf ×
=
.
Пример 2.3. Покажем, что функция
4343
),( хxхxf
−
=
, где Nхх
∈
43
, , а
пары
2
43
),( Nxx ∈ , является частично вычислимой.
Предположим, что
43
xx ≥ . Построим МТ, выполняющую вычитание
при указанном условии. Пусть на ленте расположены коды
3
х и
4
х ,
разделенные пробелом и головка обозревает пробел перед
3
х . Организуем
работу машины таким образом, чтобы она выполняла последовательные
циклы. В каждом цикле машина просматривает записи на ленте слева
направо и стирает самую левую палочку в
3
х и саму правую в
4
х , а затем
l
|
l
|
В
|
rBR
2
lBl
BL
2
K
R
3
В
В
В
l
|
L
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
