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

UptoLike

ВУЗ: 

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

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

Рубрика: 

как можно реализовать на этих машинах основные программные
структуры:
• cуперпозицию программ;
• композицию программ;
• ветвление и циклические структуры.
Суперпозиция программ. Предположим, что машины M
и M
1 2
вычисляют соответственно функции f
(X) и f
1 2
(X) в одном и том же
алфавите A. Построим машину M=M
°M
1 2
для вычисления
суперпозиции f
2
(f
1
(X))
(рис.4.2). Обозначения
состояний машин M
1
и M
2
должны различаться за
исключением того, что заключительное состояние M
f
1
f
2
f
2
(
f
1
(
X
))
X
Рис.4.2.
1
имеет то же
обозначение, что и начальное состояние M
2
. В таком случае
программа машины M получается простым объединением программ
M
и M . Работу машины M=M °M можно представить схемой
1 2 1 2
(
)
(
)
(
)
XffXfX
MM
121
21
→→
.
Композиция программ. Пусть машины M
и M
1 2
вычисляют
функции f
(X) и f (X) соответственно. Построим машину M= M *M
1 2 1 2
для вычисления композиции f
(X)*f
1 2
(X), где * - символ, не
встречающийся в алфавитах M
и M
1 2
. Машина M использует
“двухэтажную” ленту, на которую записываются пары символов вида
. Слово X записывается нижними элементами пары вида , где
Λ - пустой символ. После запуска M оно переписывается в верхний
этаж и оказывается записанным символами вида . Далее M
работает на нижнем этаже как M
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
a
b
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
Λ
a
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
a
a
и вычисляет f
1 1
(X), затем M
работает на верхнем этаже как M
и вычисляет f (X). В завершение M
2 2
149

Страницы