Математическая логика и теория алгоритмов. Анкудинов Г.И - 67 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

Циклическая программа. Рассмотрим циклическую
программу на рис.4.5. Если значение
предиката P(X) истина (и), то программа
выдает значение f
1
(X). Если же значение
предиката P(X) (л), то программа
вычисляет значение X
(1)
=f
2
(X) и, если
P(X
(1)
)=и, то программа выдает значение
f
1
(X
(1)
), в противном случае вычисляет
значение X
(2)
=f
2
(X
(1)
) и т.д.
Приведем схему машины
Тьюринга, реализующей циклическую программу (рис.4.6). На этой
схеме машина M
f
1
(
X
)
f
1
X
f
2
f
2
(
X
)
и
л
P
(X)
Рис. 4.5.
M
P
*M
0
X
σ*X
M
1
∨M
2
σ=и
σ=л
f
1
(X)
f
2
(X)
Рис. 4.6.
вычисляет значение σ предиката P(X), машина M
P 0
передает X без изменения, поэтому композиция M
*M
P 0
формирует
σ*X. Машины M
и M вычисляют f (X) и f
1 2 1 2
(X) соответственно.
Машина M
1
∨M обеспечивает ветвление.
2
4.3. Элементы теории рекурсивных функций
Рекурсия - способ определения функций, являющийся одним из
основных объектом изучения в теории алгоритмов. Смысл рекурсии
151

Страницы