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

UptoLike

ВУЗ: 

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

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

Рубрика: 

198 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ
ôÁËÏÊ ÓÐÏÓÏ ÏÐÒÅÄÅÌÅÎÉÑ ÆÕÎËÃÉÉ ÎÁÚÙ×ÁÀÔ ÏÇÒÁÎÉÞÅÎÎÙÍ ÏÐÅÒÁÔÏ-
ÒÏÍ ÍÉÎÉÍÉÚÁÃÉÉ ¡ × ÏÔÌÉÞÉÅ ÏÔ ÎÅÏÇÒÁÎÉÞÅÎÎÏÇÏ, ÇÄÅ ÎÅÔ ÚÁÒÁÎÅÅ ÉÚ×ÅÓÔ-
ÎÏÊ ÇÒÁÎÉÃÙ g(x). ëÁË ÍÙ Õ×ÉÄÉÍ, × ÎÅÏÇÒÁÎÉÞÅÎÎÏÍ ÓÌÕÞÁÅ ÐÏÌÕÞÁÀÝÁÑÓÑ
ÆÕÎËÃÉÑ ÎÅ ÏÂÑÚÁÎÁ ÂÙÔØ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ.
ïÇÒÁÎÉÞÅÎÎÙÊ ÏÐÅÒÁÔÏÒ ÍÉÎÉÍÉÚÁÃÉÉ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ, ÞÔÏÂÙ ÕÂÅ-
ÄÉÔØÓÑ, ÞÔÏ ÆÕÎËÃÉÑ x 7→ (ÍÉÎÉÍÁÌØÎÏÅ ÐÒÏÓÔÏÅ ÞÉÓÌÏ, ÂÏÌØÛÅÅ x) ÐÒÉÍÉ-
ÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ (ÒÁÓÓÕÖÄÅÎÉÅ å×ËÌÉÄÁ Ï ÂÅÓËÏÎÅÞÎÏÓÔÉ ÍÎÏÖÅÓÔ×Á ÐÒÏ-
ÓÔÙÈ ÞÉÓÅÌ ÕÓÔÁÎÁ×ÌÉ×ÁÅÔ, ÞÔÏ ÜÔÏ ÞÉÓÌÏ ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ x! + 1, Á ÆÁËÔÏÒÉ-
ÁÌ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÅÎ). ðÏÓÌÅ ÜÔÏÇÏ ÆÕÎËÃÉÑ n 7→ (n-Å ÐÒÏÓÔÏÅ ÞÉÓÌÏ)
ÌÅÇËÏ ÏÐÒÅÄÅÌÑÅÔÓÑ Ó ÐÏÍÏÝØÀ ÒÅËÕÒÓÉÉ.
§4. äÒÕÇÉÅ ×ÉÄÙ ÒÅËÕÒÓÉÉ
óÌÏ×Á ¥ÒÅËÕÒÓÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÆÕÎËÃÉÉ¥ ÍÏÖÎÏ ÐÏÎÉÍÁÔØ É × ÂÏÌÅÅ
ÛÉÒÏËÏÍ ÓÍÙÓÌÅ, ÎÅÖÅÌÉ ÍÙ ÜÔÏ ÄÅÌÁÌÉ (ÓÍ. ×ÙÛÅ ÏÐÒÅÄÅÌÅÎÉÅ ÒÅËÕÒÓÉÉ,
ÉÌÉ ÐÒÉÍÉÔÉ×ÎÏÊ ÒÅËÕÒÓÉÉ) ¡ ËÁË ÌÀÂÏÊ ÓÐÏÓÏ ÚÁÄÁÎÉÑ ÆÕÎËÃÉÉ, ËÏÔÏÒÙÊ
Ó×ÑÚÙ×ÁÅÔ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ × ÄÁÎÎÏÊ ÔÏÞËÅ Ó ÄÒÕÇÉÍÉ Å¾ ÚÎÁÞÅÎÉÑÍÉ. ëÁË
ÍÙ Õ×ÉÄÉÍ ÎÉÖÅ ÐÒÉ ÏÂÓÕÖÄÅÎÉÉ ÆÕÎËÃÉÉ áËËÅÒÍÁÎÁ, ÅÓÔØ ÔÁËÉÅ ÓÈÅÍÙ
ÒÅËÕÒÓÉ×ÎÙÈ ÏÐÒÅÄÅÌÅÎÉÊ, ËÏÔÏÒÙÅ ×Ù×ÏÄÑÔ ÉÚ ËÌÁÓÓÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒ-
ÓÉ×ÎÙÈ ÆÕÎËÃÉÊ. îÏ ÅÓÔØ É ÔÁËÉÅ, ËÏÔÏÒÙÅ ÍÏÖÎÏ Ó×ÅÓÔÉ Ë ÒÁÓÓÍÏÔÒÅÎÎÏÊ
ÎÁÍÉ ÓÈÅÍÅ.
íÙ ÐÒÉ×ÅÄ¾Í Ä×Á ÐÒÉÍÅÒÁ ÐÏÓÌÅÄÎÅÇÏ ÔÉÐÁ: ÓÏ×ÍÅÓÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÎÅ-
ÓËÏÌØËÉÈ ÆÕÎËÃÉÊ É ÉÓÐÏÌØÚÏ×ÁÎÉÅ ÐÒÏÉÚ×ÏÌØÎÙÈ ÍÅÎØÛÉÈ ÚÎÁÞÅÎÉÊ ÁÒÇÕ-
ÍÅÎÔÁ.
óÏ×ÍÅÓÔÎÁÑ ÒÅËÕÒÓÉÑ. ðÕÓÔØ Ä×Å ÏÄÎÏÍÅÓÔÎÙÅ ÆÕÎËÃÉÉ f É g ÚÁÄÁÎÙ ÓÏ-
ÏÔÎÏÛÅÎÉÑÍÉ:
f(0) = a, (1)
g(0) = b, (2)
f(n + 1) = F (n, f(n), g(n)), (3)
g(n + 1) = G(n, f (n), g(n)), (4)
ÇÄÅ a É b ¡ ÎÅËÏÔÏÒÙÅ ÞÉÓÌÁ, Á ÆÕÎËÃÉÉ F É G ¡ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ
ÆÕÎËÃÉÉ ÔÒ¾È ÁÒÇÕÍÅÎÔÏ×. ðÏËÁÖÅÍ, ÞÔÏ ÔÏÇÄÁ ÆÕÎËÃÉÉ f É g ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÙ.
þÔÏÂÙ ÄÏËÁÚÁÔØ ÜÔÏ, ÎÁÍ ÐÏÔÒÅÂÕÅÔÓÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁÑ ÎÕÍÅ-
ÒÁÃÉÑ ÐÁÒ ¡ ÔÁËÁÑ ÆÕÎËÃÉÑ hx, yi → [x, y] (ÎÏÍÅÒ ÐÁÒÙ ÍÙ ÏÂÏÚÎÁÞÁÅÍ
Ë×ÁÄÒÁÔÎÙÍÉ ÓËÏÂËÁÍÉ), ËÏÔÏÒÁÑ ÂÙÌÁ ÂÙ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ ×ÍÅÓÔÅ
Ó Ä×ÕÍÑ ÏÂÒÁÔÎÙÍÉ ÆÕÎËÃÉÑÍÉ (ÄÁÀÝÉÍÉ ÐÏ ÎÏÍÅÒÕ ÐÁÒ٠ž ÐÅÒ×ÙÊ É
×ÔÏÒÏÊ ÞÌÅÎÙ). ôÏÇÄÁ ÍÙ ÓÍÏÖÅÍ ÎÁÐÉÓÁÔØ ÒÅËÕÒÓÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÄÌÑ
198                                     çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

   ôÁËÏÊ ÓÐÏÓÏ ÏÐÒÅÄÅÌÅÎÉÑ ÆÕÎËÃÉÉ ÎÁÚÙ×ÁÀÔ ÏÇÒÁÎÉÞÅÎÎÙÍ ÏÐÅÒÁÔÏ-
ÒÏÍ ÍÉÎÉÍÉÚÁÃÉÉ ¡ × ÏÔÌÉÞÉÅ ÏÔ ÎÅÏÇÒÁÎÉÞÅÎÎÏÇÏ, ÇÄÅ ÎÅÔ ÚÁÒÁÎÅÅ ÉÚ×ÅÓÔ-
ÎÏÊ ÇÒÁÎÉÃÙ g(x). ëÁË ÍÙ Õ×ÉÄÉÍ, × ÎÅÏÇÒÁÎÉÞÅÎÎÏÍ ÓÌÕÞÁÅ ÐÏÌÕÞÁÀÝÁÑÓÑ
ÆÕÎËÃÉÑ ÎÅ ÏÂÑÚÁÎÁ ÂÙÔØ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ.
   ïÇÒÁÎÉÞÅÎÎÙÊ ÏÐÅÒÁÔÏÒ ÍÉÎÉÍÉÚÁÃÉÉ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ, ÞÔÏÂÙ ÕÂÅ-
ÄÉÔØÓÑ, ÞÔÏ ÆÕÎËÃÉÑ x 7→ (ÍÉÎÉÍÁÌØÎÏÅ ÐÒÏÓÔÏÅ ÞÉÓÌÏ, ÂÏÌØÛÅÅ x) ÐÒÉÍÉ-
ÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ (ÒÁÓÓÕÖÄÅÎÉÅ å×ËÌÉÄÁ Ï ÂÅÓËÏÎÅÞÎÏÓÔÉ ÍÎÏÖÅÓÔ×Á ÐÒÏ-
ÓÔÙÈ ÞÉÓÅÌ ÕÓÔÁÎÁ×ÌÉ×ÁÅÔ, ÞÔÏ ÜÔÏ ÞÉÓÌÏ ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ x! + 1, Á ÆÁËÔÏÒÉ-
ÁÌ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÅÎ). ðÏÓÌÅ ÜÔÏÇÏ ÆÕÎËÃÉÑ n 7→ (n-Å ÐÒÏÓÔÏÅ ÞÉÓÌÏ)
ÌÅÇËÏ ÏÐÒÅÄÅÌÑÅÔÓÑ Ó ÐÏÍÏÝØÀ ÒÅËÕÒÓÉÉ.

  §4. äÒÕÇÉÅ ×ÉÄÙ ÒÅËÕÒÓÉÉ
   óÌÏ×Á ¥ÒÅËÕÒÓÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÆÕÎËÃÉÉ¥ ÍÏÖÎÏ ÐÏÎÉÍÁÔØ É × ÂÏÌÅÅ
ÛÉÒÏËÏÍ ÓÍÙÓÌÅ, ÎÅÖÅÌÉ ÍÙ ÜÔÏ ÄÅÌÁÌÉ (ÓÍ. ×ÙÛÅ ÏÐÒÅÄÅÌÅÎÉÅ ÒÅËÕÒÓÉÉ,
ÉÌÉ ÐÒÉÍÉÔÉ×ÎÏÊ ÒÅËÕÒÓÉÉ) ¡ ËÁË ÌÀÂÏÊ ÓÐÏÓÏ ÚÁÄÁÎÉÑ ÆÕÎËÃÉÉ, ËÏÔÏÒÙÊ
Ó×ÑÚÙ×ÁÅÔ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ × ÄÁÎÎÏÊ ÔÏÞËÅ Ó ÄÒÕÇÉÍÉ Å¾ ÚÎÁÞÅÎÉÑÍÉ. ëÁË
ÍÙ Õ×ÉÄÉÍ ÎÉÖÅ ÐÒÉ ÏÂÓÕÖÄÅÎÉÉ ÆÕÎËÃÉÉ áËËÅÒÍÁÎÁ, ÅÓÔØ ÔÁËÉÅ ÓÈÅÍÙ
ÒÅËÕÒÓÉ×ÎÙÈ ÏÐÒÅÄÅÌÅÎÉÊ, ËÏÔÏÒÙÅ ×Ù×ÏÄÑÔ ÉÚ ËÌÁÓÓÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒ-
ÓÉ×ÎÙÈ ÆÕÎËÃÉÊ. îÏ ÅÓÔØ É ÔÁËÉÅ, ËÏÔÏÒÙÅ ÍÏÖÎÏ Ó×ÅÓÔÉ Ë ÒÁÓÓÍÏÔÒÅÎÎÏÊ
ÎÁÍÉ ÓÈÅÍÅ.
   íÙ ÐÒÉ×ÅÄ¾Í Ä×Á ÐÒÉÍÅÒÁ ÐÏÓÌÅÄÎÅÇÏ ÔÉÐÁ: ÓÏ×ÍÅÓÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÎÅ-
ÓËÏÌØËÉÈ ÆÕÎËÃÉÊ É ÉÓÐÏÌØÚÏ×ÁÎÉÅ ÐÒÏÉÚ×ÏÌØÎÙÈ ÍÅÎØÛÉÈ ÚÎÁÞÅÎÉÊ ÁÒÇÕ-
ÍÅÎÔÁ.
   óÏ×ÍÅÓÔÎÁÑ ÒÅËÕÒÓÉÑ. ðÕÓÔØ Ä×Å ÏÄÎÏÍÅÓÔÎÙÅ ÆÕÎËÃÉÉ f É g ÚÁÄÁÎÙ ÓÏ-
ÏÔÎÏÛÅÎÉÑÍÉ:
                            f (0) = a,                                (1)
                            g(0) = b,                                 (2)
                       f (n + 1) = F (n, f (n), g(n)),                (3)
                       g(n + 1) = G(n, f (n), g(n)),                  (4)
ÇÄÅ a É b ¡ ÎÅËÏÔÏÒÙÅ ÞÉÓÌÁ, Á ÆÕÎËÃÉÉ F É G ¡ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ
ÆÕÎËÃÉÉ ÔÒ¾È ÁÒÇÕÍÅÎÔÏ×. ðÏËÁÖÅÍ, ÞÔÏ ÔÏÇÄÁ ÆÕÎËÃÉÉ f É g ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÙ.
   þÔÏÂÙ ÄÏËÁÚÁÔØ ÜÔÏ, ÎÁÍ ÐÏÔÒÅÂÕÅÔÓÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁÑ ÎÕÍÅ-
ÒÁÃÉÑ ÐÁÒ ¡ ÔÁËÁÑ ÆÕÎËÃÉÑ hx, yi → [x, y] (ÎÏÍÅÒ ÐÁÒÙ ÍÙ ÏÂÏÚÎÁÞÁÅÍ
Ë×ÁÄÒÁÔÎÙÍÉ ÓËÏÂËÁÍÉ), ËÏÔÏÒÁÑ ÂÙÌÁ ÂÙ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ ×ÍÅÓÔÅ
Ó Ä×ÕÍÑ ÏÂÒÁÔÎÙÍÉ ÆÕÎËÃÉÑÍÉ (ÄÁÀÝÉÍÉ ÐÏ ÎÏÍÅÒÕ ÐÁÒ٠ž ÐÅÒ×ÙÊ É
×ÔÏÒÏÊ ÞÌÅÎÙ). ôÏÇÄÁ ÍÙ ÓÍÏÖÅÍ ÎÁÐÉÓÁÔØ ÒÅËÕÒÓÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÄÌÑ

Страницы