ВУЗ:
Составители:
возвращается обратно. Описанный процесс может быть реализован с
помощью ДТ, приведенной на рис. 2.5.
Рис. 2.5
Ясно, что после того, как все палочки в
4
х
будут стерты, машина остановится
(в этом случае элементарная МТ r встретит не палочку, а пробел).
Предположим теперь, что
4
х >
3
х . В этом случае найдется цикл, в
котором все палочки
3
х будут стерты, а
4
х еще нет. При выполнении этого
цикла на ленте будет записано:
{
BBBBBBB
x
x
43421
4
3
..|...||...
↑
Поэтому из двух
элементарных МТ L срабатывает только первая, а вторая будет вечно искать
несуществующий на ленте массив палочек. Таким образом, функция
),(
43
хxf
не определена для случая
4
х >
3
х и для нее не существует МТ. Другими
словами, функция
),(
43
хxf является частично вычислимой.
В данном случае частично вычислимую функцию
4343
),( хxхxf
−
=
можно продолжить до вычислимой функции двумя способами. Во-первых, до
вычислимой функции
||),(
4343
хxхxf
−
=
′
, а во-вторых, до вычислимой
функции
⎪
⎩
⎪
⎨
⎧
〈
≥−
=
.0
,
),(
43
4343
43
ххпри
ххприxx
xxf
Функции
),(
43
хxf
′
и ),(
43
хxf
′
′
реализуются ДТ, приведенными
соответственно на рис. 2.6.
Рис. 2.6.
lBL
2
r
B
|
BR
2
s
В
l
|
В
L
2
r
|
В
R
2
В
s
s
В
l
|
В
L
2
r
|
В
R
2
В
s
s
а)
В
В
s
l
б)
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
