Математическая логика и теория алгоритмов. Самохин А.В. - 206 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

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

Рубрика: 

206 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ
äÌÑ ÂÁÚÉÓÎÙÈ ÆÕÎËÃÉÊ ÕÔ×ÅÒÖÄÅÎÉÅ ÏÞÅ×ÉÄÎÏ. ðÏÓÍÏÔÒÉÍ ÎÁ ÐÏÄÓÔÁÎÏ×-
ËÕ. ðÕÓÔØ
f(x) = g(h
1
(x), . . . , h
k
(x))
(ÄÌÑ ËÒÁÔËÏÓÔÉ ÍÙ ÐÉÛÅÍ ÏÄÎÕ ÂÕË×Õ x, ÉÍÅÑ × ×ÉÄÕ ×ÅËÔÏÒ ÐÅÒÅÍÅÎ-
ÎÙÈ). ðÕÓÔØ α
N
ÏÃÅÎÉ×ÁÅÔ ×ÓÅ ÆÕÎËÃÉÉ h
1
, . . . , h
k
É ÆÕÎËÃÉÀ g Ó×ÅÒÈÕ,
ÔÏ ÅÓÔØ h
i
(x) 6 α
N
(max(x)) ÐÒÉ ×ÓÅÈ i É x, Á ÔÁËÖÅ g(y) 6 α
N
(max(y))
(ÚÄÅÓØ max(u) ÏÚÎÁÞÁÅÔ ÍÁËÓÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ × ÎÁÂÏÒÅ u). ôÏÇÄÁ f(x) ÎÅ
ÐÒÅ×ÏÓÈÏÄÉÔ
α
N
(max(h
1
(x), . . . , h
k
(x))) 6 α
N
(α
N
(x)) 6 α
N +1
(x)
(ÍÙ ÐÏÌØÚÕÅÍÓÑ ÕËÁÚÁÎÎÙÍÉ ×ÙÛÅ Ó×ÏÊÓÔ×ÁÍÉ ÆÕÎËÃÉÊ α
i
).
ðÏÈÏÖÅ (ÎÏ ÎÅÍÎÏÇÏ ÓÌÏÖÎÅÅ) ÄÅÌÏ ÏÂÓÔÏÉÔ Ó ÒÅËÕÒÓÉÅÊ. ðÕÓÔØ ÆÕÎËÃÉÑ f
ÏÐÒÅÄÅÌÑÅÔÓÑ ÒÅËÕÒÓÉ×ÎÏ:
f(x, 0) = g(x); (1)
f(x, n + 1) = h(x, n, f(x, n)). (2)
(úÄÅÓØ x ÔÁËÖÅ ÏÂÏÚÎÁÞÁÅÔ ÎÁÂÏÒ ÎÅÓËÏÌØËÉÈ ÐÅÒÅÍÅÎÎÙÈ.) ðÕÓÔØ ÆÕÎËÃÉÉ g
É h ÏÃÅÎÉ×ÁÀÔÓÑ Ó×ÅÒÈÕ ÆÕÎËÃÉÅÊ α
N
. ôÏÇÄÁ
f(x, 1) = h(x, 0, f (x, 0)) 6 α
N
(max(x, 0, f(x, 0))) 6
6 α
N
(max(x, 0, α
N
(max(x)))) 6 α
N
(α
N
(max(x))) (3)
(× ÐÏÓÌÅÄÎÅÍ ÐÅÒÅÈÏÄÅ ÍÙ ÐÏÌØÚÕÅÍÓÑ ÔÅÍ, ÞÔÏ α
N
(t) > t). áÎÁÌÏÇÉÞÎÏ
f(x, 2) 6 α
N
(α
N
(α
N
(max(x)))) É ×ÏÏÂÝÅ
f(x, i) 6 α
[i+1]
N
(max(x)) 6 α
N +1
(max(i, max(x))),
ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ ÄÏËÁÚÁÔØ.
úÁÍÅÔÉÍ, ÞÔÏ ËÁÖÄÙÊ ÏÐÅÒÁÔÏÒ ÐÏÄÓÔÁÎÏ×ËÉ ÉÌÉ ÒÅËÕÒÓÉÉ Õ×ÅÌÉÞÉ×ÁÅÔ
ÎÏÍÅÒ ×ÅÒÈÎÅÊ ÏÃÅÎËÉ ÎÁ 1, ÔÁË ÞÔÏ ÆÕÎËÃÉÑ, × ÏÐÒÅÄÅÌÅÎÉÉ ËÏÔÏÒÏÊ ÎÅ
ÂÏÌÅÅ 100 ÏÐÅÒÁÔÏÒÏ×, ÒÁÓÔ¾Ô ÎÅ ÂÙÓÔÒÅÅ α
101
.
ïÞÅ×ÉÄÎÙÍ ÓÌÅÄÓÔ×ÉÅÍ ÐÏÌÕÞÅÎÎÏÊ ÏÃÅÎËÉ Ñ×ÌÑÅÔÓÑ ÔÁËÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ:
ôÅÏÒÅÍÁ 82. æÕÎËÃÉÑ A(n) = α
n
(n) ÒÁÓÔ¾Ô ÂÙÓÔÒÅÅ ÌÀÂÏÊ ÐÒÉÍÉÔÉ×-
ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ ÆÕÎËÃÉÉ.
ïÔÍÅÔÉÍ, ÞÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÆÕÎËÃÉÉ áËËÅÒÍÁÎÁ (ÔÏÞÎÅÅ, ÆÕÎËÃÉÉ
hn, xi 7→ α
n
(x)) ×ÐÏÌÎÅ ÍÏÖÎÏ ÎÁÚ×ÁÔØ ÒÅËÕÒÓÉ×ÎÙÍ ¡ ÏÄÎÏ ÚÎÁÞÅÎÉÅ ÜÔÏÊ
ÆÕÎËÃÉÉ ÏÐÒÅÄÅÌÑÅÔÓÑ ÞÅÒÅÚ ÄÒÕÇÉÅ, Ó ÍÅÎØÛÉÍ ÐÅÒ×ÙÍ ÁÒÇÕÍÅÎÔÏÍ. ïÎÏ
Ñ×ÌÑÅÔÓÑ ÐÒÉÍÅÒÏÍ ÒÅËÕÒÓÉ×ÎÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ, ÎÅ Ó×ÏÄÑÝÅÇÏÓÑ Ë ÐÒÉÍÉÔÉ×-
ÎÏÊ ÒÅËÕÒÓÉÉ.
206                                         çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

   äÌÑ ÂÁÚÉÓÎÙÈ ÆÕÎËÃÉÊ ÕÔ×ÅÒÖÄÅÎÉÅ ÏÞÅ×ÉÄÎÏ. ðÏÓÍÏÔÒÉÍ ÎÁ ÐÏÄÓÔÁÎÏ×-
ËÕ. ðÕÓÔØ
                       f (x) = g(h1(x), . . . , hk (x))
(ÄÌÑ ËÒÁÔËÏÓÔÉ ÍÙ ÐÉÛÅÍ ÏÄÎÕ ÂÕË×Õ x, ÉÍÅÑ × ×ÉÄÕ ×ÅËÔÏÒ ÐÅÒÅÍÅÎ-
ÎÙÈ). ðÕÓÔØ αN ÏÃÅÎÉ×ÁÅÔ ×ÓÅ ÆÕÎËÃÉÉ h1 , . . . , hk É ÆÕÎËÃÉÀ g Ó×ÅÒÈÕ,
ÔÏ ÅÓÔØ hi (x) 6 αN (max(x)) ÐÒÉ ×ÓÅÈ i É x, Á ÔÁËÖÅ g(y) 6 αN (max(y))
(ÚÄÅÓØ max(u) ÏÚÎÁÞÁÅÔ ÍÁËÓÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ × ÎÁÂÏÒÅ u). ôÏÇÄÁ f (x) ÎÅ
ÐÒÅ×ÏÓÈÏÄÉÔ
             αN (max(h1 (x), . . . , hk (x))) 6 αN (αN (x)) 6 αN +1 (x)
(ÍÙ ÐÏÌØÚÕÅÍÓÑ ÕËÁÚÁÎÎÙÍÉ ×ÙÛÅ Ó×ÏÊÓÔ×ÁÍÉ ÆÕÎËÃÉÊ αi ).
  ðÏÈÏÖÅ (ÎÏ ÎÅÍÎÏÇÏ ÓÌÏÖÎÅÅ) ÄÅÌÏ ÏÂÓÔÏÉÔ Ó ÒÅËÕÒÓÉÅÊ. ðÕÓÔØ ÆÕÎËÃÉÑ f
ÏÐÒÅÄÅÌÑÅÔÓÑ ÒÅËÕÒÓÉ×ÎÏ:
                              f (x, 0) = g(x);                              (1)
                         f (x, n + 1) = h(x, n, f (x, n)).                  (2)
(úÄÅÓØ x ÔÁËÖÅ ÏÂÏÚÎÁÞÁÅÔ ÎÁÂÏÒ ÎÅÓËÏÌØËÉÈ ÐÅÒÅÍÅÎÎÙÈ.) ðÕÓÔØ ÆÕÎËÃÉÉ g
É h ÏÃÅÎÉ×ÁÀÔÓÑ Ó×ÅÒÈÕ ÆÕÎËÃÉÅÊ αN . ôÏÇÄÁ

 f (x, 1) = h(x, 0, f (x, 0)) 6 αN (max(x, 0, f (x, 0))) 6
                            6 αN (max(x, 0, αN (max(x)))) 6 αN (αN (max(x))) (3)
(× ÐÏÓÌÅÄÎÅÍ ÐÅÒÅÈÏÄÅ ÍÙ ÐÏÌØÚÕÅÍÓÑ ÔÅÍ, ÞÔÏ αN (t) > t). áÎÁÌÏÇÉÞÎÏ
f (x, 2) 6 αN (αN (αN (max(x)))) É ×ÏÏÂÝÅ
                          [i+1]
              f (x, i) 6 αN (max(x)) 6 αN +1(max(i, max(x))),
ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ ÄÏËÁÚÁÔØ.
   úÁÍÅÔÉÍ, ÞÔÏ ËÁÖÄÙÊ ÏÐÅÒÁÔÏÒ ÐÏÄÓÔÁÎÏ×ËÉ ÉÌÉ ÒÅËÕÒÓÉÉ Õ×ÅÌÉÞÉ×ÁÅÔ
ÎÏÍÅÒ ×ÅÒÈÎÅÊ ÏÃÅÎËÉ ÎÁ 1, ÔÁË ÞÔÏ ÆÕÎËÃÉÑ, × ÏÐÒÅÄÅÌÅÎÉÉ ËÏÔÏÒÏÊ ÎÅ
ÂÏÌÅÅ 100 ÏÐÅÒÁÔÏÒÏ×, ÒÁÓÔ¾Ô ÎÅ ÂÙÓÔÒÅÅ α101.
   ïÞÅ×ÉÄÎÙÍ ÓÌÅÄÓÔ×ÉÅÍ ÐÏÌÕÞÅÎÎÏÊ ÏÃÅÎËÉ Ñ×ÌÑÅÔÓÑ ÔÁËÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ:
   ôÅÏÒÅÍÁ 82. æÕÎËÃÉÑ A(n) = αn (n) ÒÁÓÔ¾Ô ÂÙÓÔÒÅÅ ÌÀÂÏÊ ÐÒÉÍÉÔÉ×-
ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ ÆÕÎËÃÉÉ.
   ïÔÍÅÔÉÍ, ÞÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÆÕÎËÃÉÉ áËËÅÒÍÁÎÁ (ÔÏÞÎÅÅ, ÆÕÎËÃÉÉ
hn, xi 7→ αn (x)) ×ÐÏÌÎÅ ÍÏÖÎÏ ÎÁÚ×ÁÔØ ÒÅËÕÒÓÉ×ÎÙÍ ¡ ÏÄÎÏ ÚÎÁÞÅÎÉÅ ÜÔÏÊ
ÆÕÎËÃÉÉ ÏÐÒÅÄÅÌÑÅÔÓÑ ÞÅÒÅÚ ÄÒÕÇÉÅ, Ó ÍÅÎØÛÉÍ ÐÅÒ×ÙÍ ÁÒÇÕÍÅÎÔÏÍ. ïÎÏ
Ñ×ÌÑÅÔÓÑ ÐÒÉÍÅÒÏÍ ÒÅËÕÒÓÉ×ÎÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ, ÎÅ Ó×ÏÄÑÝÅÇÏÓÑ Ë ÐÒÉÍÉÔÉ×-
ÎÏÊ ÒÅËÕÒÓÉÉ.

Страницы