Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 150

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

76

 

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

 

[ГЛ. I

условие

 

заданы

как

нормальные

алгорифмы)

выте­

кает

из

следующей

теоремы

( М а р к о в

[2;

гл. 3,

§

5]).

Т е о р е м а

7.

Каковы

 

бы

ни были

нормальные

 

алго­

рифмы

21,

33

и

может быть построен

нормальный

 

ал­

горифм

33 над объединением

А их

алфавитов

такой, что

при любом

слове

Р в А

 

 

 

 

 

 

 

 

 

1)

если

& не

применим

к

Р, то и 3) не применим

 

к Р;

2)

если

g

применим

к Р, то

 

 

 

 

 

 

 

 

 

 

 

 

33 (Р) ~

21 (Р)

 

 

 

 

 

 

в том случае,

когда

 

 

 

 

 

 

 

 

 

 

и

 

 

 

 

 

6 ( Р ) = Л ,

 

 

 

 

 

 

 

 

 

 

 

3) (Р) ~

23 (Р)

 

 

 

 

 

 

е гол случае,

когда

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<£(/>)# Л .

 

 

 

 

 

 

Теорема

разветвления

легко

распространяется

на

случай, когда выбор работающего алгорифма зависит от

последовательной проверки

нескольких

условий.

 

 

 

Т е о р е м а

8 (ср. М а р к о в

[2; гл. 3,

§ 5]). Каковы

бы

ни были

нормальные

алгорифмы

%ь . . .,

2f„+ 1 , S b

. . . ,

Q>„

(и >

0),

можно

построить такой нормальный

алгорифм

2D

над

 

объединением

А их

алфавитов,

что

для

любого

слова

Р

в

А*)

 

 

 

 

 

 

 

35 (Р)

~

 

 

 

 

 

 

 

 

 

 

 

21, (Р),

если

е , ( Я ) =

Л ,

 

 

 

 

 

 

212 (Р),

если

( Е , ( Р ) # Л ,

< М Р ) = Л ,

 

 

 

^

213 (Р),

есл«

6 , ( Р ) # Л ,

М Р ) # Л , е 3 (^)=г=Л,

 

 

2t„(P),

если

(МР)=5бЛ,..., 6 Я - , ( Р ) # Л , 6Я (Р) =

Л ,

 

Я Я + 1 ( Р ) ,

есл«

S , ( P ) ^ A , <5а(Р)=£ Л,...,

 

ВД#Л.

 

*) Следует иметь в виду, что если два выражения связаны

знаком графического

неравенства ^ф, то они

осмыслены

и пред­

ставляют собой различные слова. Словесное предписание, соответ­ ствующее алгорифму £>, таково: применяем к Р алгорифм бг, если процесс применения Gi закончился, то смотрим, пуст или нет ре­

зультат;

в случае, когда

6 i (

^ > ) = r r A , применяем к Р алгорифм

Щи

в случае,

когда &i(P)=£

Л ,

применяем к Р алгорифм 6 2 и

т. д.

 

 

 

 

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

 

 

 

77

С л е д с т в и е

3.

Пусть

$Ф — разрешимое

 

свойство

слов

в алфавите

А,

21, 53,

К —- нормальные

 

алгорифмы

над А. Можно построить нормальный

алгорифм

55 над

А

так,

что для

любого

слова

Р в

А

 

 

 

 

 

 

 

 

21 (Р), если

слово

Р

обладает

свойством

S4-,

 

 

23 (Р), если

слово

Р не обладает

свойством S4-.

С л е д с т в и е

4.

Пусть

 

s4-u...,

Жп

—разрешимые

свойства

слов

в

алфавите

А,

210

 

,

21„ —

нормальные

алгорифмы

 

над

А.

 

Можно

построить

 

нормальный

алгорифм

3)

над А

так,

 

что при

любом

слове

Р в

А

выполняется

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

•

\{Р)<

если

Р

не

обладает

ни

одним

из

свойств

 

 

 

 

s4-i (1 <

i <

 

п),

 

 

 

 

 

 

 

 

21, (Р),

если

Р

обладает

свойством

s4-x,

 

 

 

212 (Р),

если

Р

не

 

обладает

свойством

six

и

 

 

 

обладает

свойством

М2,

 

 

 

 

 

21„(Р),

если

Р

не

обладает

свойствами

М[

 

 

 

(I г О ' ^ п

— 1) и обладает свойством

s£n.

4) Т е о р е м а п о в т о р е н и я . О п е р а т о р

н а и ­

м е н ь ш е г о ч и с л а . З а д а н и е н о р м а л ь н ы х а л ­ г о р и ф м о в р е к у р с и е й . Во многих случаях возни­ кает необходимость в итерации некоторого процесса до тех пор, пока получающийся результат не удовлетворит определенному условию. Например, таким повторяемым процессом может быть прибавление единицы к нату­ ральному числу, а проверяемым условием — свойство натурального числа быть большим, скажем, пяти. В слу­ чае, когда рассматриваемый процесс есть словарный алгорифм 2Т, а условие является алгорифмически про­ веряемым, можно сформулировать следующее алгорифмическое предписание (рис. 5): применить к исходному

слову

Р алгорифм 21, проверить, обладает

ли результат

21 (Р)

(если, конечно, 21 применим к Р)

нужным свой­

ством; при положительном исходе этой проверки обо­

рвать переработку

слова Р

и считать

21 (Р)

результатом,

при отрицательном

исходе

перейти к

слову

21 (Р) и по­

ступить с ним так

же, как

и с Р, и т. д.

 

78 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА [ГЛ. 1

Т е о р е м а 9 ( М а р к о в

[2;

гл. 3,

§

6]).

Каковы

бы

ни были

нормальные

алгорифмы

%

и

33,

может быть

построен

нормальный

алгорифм

S над

объединением

А

 

21

21 (Р)

ПроВврш

 

А Выполнено

 

 

 

услооая d

 

 

ВыхоВ

d не Выполнено

Рис . 5. Повторение нормального алгорифма.

их

алфавитов

такой,

что (5

перерабатывает

произволь­

ное

слово

Р е

А в слово

Q

тогда и

только

тогда, когда

существует

ряд

слов

Р0,

...,

Рп (п>

0) со

следующими

свойствами:

 

 

 

 

 

 

 

(51)

 

 

Р^Р,

 

 

 

 

(52)

 

 

Я, =

Я(Р,_,)

( 0 < / < л ) ,

 

(53)P„==Q,

(54)

ЯЭ(Р,)=5#Л

(0 < / < / * ) ,

(55)2 3 ( Р „ ) ^ Л .

Иногда, прежде чем применять к данному слову алгорифм 21, оказывается целесообразным проверить,

Р

Проверка

& не Выполнено

21

i/слоВия <А

 

 

 

 

J d Выполнено

Выход

Рис. 6. Видоизмененное повторение нормального алгорифма.

не обладает ли нужным свойством само исходное слово (так, в частности, обстоит дело с приведенным выше примером последовательного прибавления единицы). В подобных случаях полезен следующий вариант тео­ ремы повторения (рис. 6)

i I ]

 

 

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

 

 

79

 

 

 

 

 

 

Т е о р е м а

10 ( М а р к о в

[2; гл. 3, § 6]). Каковы

бы

ни

были

нормальные

алгорифмы

%

и 23,

можно

по­

строить нормальный

 

алгорифм

(5

над

объединением

А

их

алфавитов

такой,

что

6

перерабатывает

 

произволь­

ное

слово

Р е

А в

слово

Q

тогда и только

тогда,

когда

существует ряд слов Р0, ...,

Рп

(п ^

0),

удовлетворяю­

щий условиям

(51) — (53), (55)

и

условию

 

 

 

 

 

 

5 3 ( Л - ) # Л

 

(0 < / < п).

 

 

 

 

Про

алгорифм

(5, построенный

согласно

теореме 9

(теореме 10), будем говорить, что он является повто­

рением (видоизмененным

повторением)

алгорифма 51,

управляемым алгорифмом 23.

 

Теорема повторения

позволяет задавать нормальные

алгорифмы при помощи таких хорошо известных из

теории

рекурсивных

функций средств,

как

ц-оператор

и

примитивная рекурсия.

 

 

 

 

 

Пусть si—

некоторое свойство натуральных чисел*).

Обозначим

через

 

 

 

 

 

(56)

 

 

 

\ins4- (п)

 

 

 

наименьшее

натуральное число,

обладающее

свойством

si.

В случае,

когда

свойство

si

не выполняется ни для

какого

натурального

числа,

выражение

(56)

считается

лишенным

смысла.

 

 

 

 

 

 

С двухместным алгорифмически проверяемым отно­

шением

si

можно связать следующее

алгорифмическое

предписание: для данного исходного слова Р последо­

вательно проверять si(P,0),

si(P,l)

и т. д. до обнару­

жения

числа

k, при

котором первый

раз

выполнится

si(P,k);

это

число

считать

результатом.

Возможность

оформления такого предписания в виде нормального

алгорифма

(при

условии,

что

мы

имеем

нормальный

алгорифм,

проверяющий

отношение

si)

вытекает из

следующей

теоремы (в теоремах

11 —12 А — произволь­

ный

алфавит,

а — некоторая

не

принадлежащая

алфа­

виту А 0 {0|} буква).

 

 

 

 

 

 

 

Т е о р е м а

11

(ср. Ц е й т и н

[5;

стр. 304]).

По

вся­

кому

нормальному

алгорифму

51 над

алфавитом

 

А[){а}

*) Напомним, что под натуральными

числами

мы

понимаем

слова

в алфавите

{0|} вида 0, 0|,

0| |

и

т. д.

 

 

 

 

80

АЛГОРИФМЫ И

ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. 1

можно

построить

нормальный алгорифм

23 над

алфави­

том A U {0|} так, что для любого

слова

Р в алфавите А

выполняется: если

при

каждом

натуральном

i

(57)

 

 

151 (Poi),

 

 

 

то

 

 

 

 

 

 

(58)3 3 ( Р ) ~ ц я ( Я ( Р < т ) = = Л ) .

Д о к а з а т е л ь с т в о . Обозначим через 23i такой нормальный алгорифм, что для любого слова Q в ал­ фавите A U {а0|}

» . ( Q ) = 5 = QI

(см. пример 8) п. 4). По теореме 10 построим алго­ рифм 232, являющийся видоизмененным повторением ал­ горифма 33], управляемым алгорифмом 91. Тогда для любого Р е Л, удовлетворяющего условию (57), будет выполняться

 

932(РоО) са Рацп{%{Pan)

== Л) .

Легко построить алгорифм 933

так, что

 

2 3 3 ( Р ) ~ 932 (Ра0).

 

Искомый алгорифм 93 строим теперь как компози­

цию алгорифмов 933 и

«высекающего» алгорифма В2

(стр. 72)

. Очевидно, при

выполнении

(57)

93

(Р) ~ В2(233 (Р)) ~ В2(Pa[in

(21 (Pan) == Л)).

Следовательно,

 

 

 

 

93(Р)~цп(21 (Pan)

=

Л),

т.е. выполняется (58), что и требуется.

Те о р е м а 12 (определение нормального алгорифма при помощи примитивной рекурсии). Пусть 91 и 23 —

нормальные

алгорифмы

соответственно

над

алфавитами

А и Ai

=

А [) {0\а}.

Можно

построить

нормальный

ал­

горифм

(S

над

А\ так,

что при любом

слове

Р в

алфа­

вите А

и любом

натуральном

числе m

 

 

 

 

 

 

S(Pa0)~9t(P),

 

 

 

 

 

© (Pam

+

1) ~ 93 (PamaS (Paw)).

 

 

Смотрите также файлы