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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§4. íÎÏÖÅÓÔ×Á ÎÏÍÅÒÏ× 167
ôÅÐÅÒØ ÌÅÇËÏ ÕËÁÚÁÔØ ÐÒÉÍÅÒ ×ÙÞÉÓÌÉÍÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎËÃÉÉ, ÎÅ
Ñ×ÌÑÀÝÅÊÓÑ ÇÌÁ×ÎÏÊ. äÏÓÔÁÔÏÞÎÏ ÓÄÅÌÁÔØ ÔÁË, ÞÔÏÂÙ ÎÉÇÄÅ ÎÅ ÏÐÒÅÄÅ̾ÎÎÁÑ
ÆÕÎËÃÉÑ ÉÍÅÌÁ ÅÄÉÎÓÔ×ÅÎÎÙÊ ÎÏÍÅÒ. üÔÏ ÎÅÓÌÏÖÎÏ. ðÕÓÔØ U(n, x) ¡ ÐÒÏ-
ÉÚ×ÏÌØÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎËÃÉÑ. òÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï D
×ÓÅÈ U-ÎÏÍÅÒÏ× ×ÓÅÈ ÆÕÎËÃÉÊ Ó ÎÅÐÕÓÔÏÊ ÏÂÌÁÓÔØÀ ÏÐÒÅÄÅÌÅÎÉÑ. ëÁË ÍÙ
ÕÖÅ ÇÏ×ÏÒÉÌÉ, ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÐÅÒÅÞÉÓÌÉÍÏ. òÁÓÓÍÏÔÒÉÍ ×ÓÀÄÕ ÏÐÒÅÄÅ̾Î-
ÎÕÀ ×ÙÞÉÓÌÉÍÕÀ ÆÕÎËÃÉÀ d, ÅÇÏ ÐÅÒÅÞÉÓÌÑÀÝÕÀ: D = {d(0), d(1), . . .}.
ôÅÐÅÒØ ÒÁÓÓÍÏÔÒÉÍ ÆÕÎËÃÉÀ V (i, x), ÄÌÑ ËÏÔÏÒÏÊ V (0, x) ÎÅ ÏÐÒÅÄÅÌÅÎÏ ÎÉ
ÐÒÉ ËÁËÏÍ x, Á V (i+1, x) = U(d(i), x). äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÆÕÎËÃÉÑ V
0
ÎÉÇÄÅ ÎÅ
ÏÐÒÅÄÅÌÅÎÁ, Á ÆÕÎËÃÉÑ V
i+1
ÓÏ×ÐÁÄÁÅÔ Ó U
d(i)
. ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÆÕÎËÃÉÑ V
×ÙÞÉÓÌÉÍÁ; ÏÎÁ ÕÎÉ×ÅÒÓÁÌØÎÁ ÐÏ ÐÏÓÔÒÏÅÎÉÀ, É ÅÄÉÎÓÔ×ÅÎÎÙÍ V -ÎÏÍÅÒÏÍ
ÎÉÇÄÅ ÎÅ ÏÐÒÅÄÅ̾ÎÎÏÊ ÆÕÎËÃÉÉ Ñ×ÌÑÅÔÓÑ ÞÉÓÌÏ 0.
îÁ ÓÁÍÏÍ ÄÅÌÅ ÓÕÝÅÓÔ×ÕÀÔ É ÂÏÌÅÅ ÜËÚÏÔÉÞÅÓËÉÅ ÎÕÍÅÒÁÃÉÉ: ËÁË ÐÏËÁ-
ÚÁÌ æÒÉÄÂÅÒÇ, ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÕÎÉ×ÅÒÓÁÌØÎÕÀ ×ÙÞÉÓÌÉÍÕÀ ÆÕÎËÃÉÀ, ÄÌÑ
ËÏÔÏÒÏÊ ËÁÖÄÁÑ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ ÂÕÄÅÔ ÉÍÅÔØ ÒÏ×ÎÏ ÏÄÉÎ ÎÏÍÅÒ. óÏ-
ÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÎÕÍÅÒÁÃÉÉ ÎÁÚÙ×ÁÀÔ ÏÄÎÏÚÎÁÞÎÙÍÉ; ÏÞÅ×ÉÄÎÏ, ÏÎÉ ÎÅ ÍÏ-
ÇÕÔ ÂÙÔØ ÇÌÁ×ÎÙÍÉ. úÁÂÁ×ÎÁÑ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁ: ÍÏÖÎÏ ÒÁÚÒÁÂÏÔÁÔØ ÔÁËÏÊ
ÑÚÙË ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ, × ËÏÔÏÒÏÍ ËÁÖÄÕÀ ÐÒÏÇÒÁÍÍÉÓÔÓËÕÀ ÚÁÄÁÞÕ ÍÏÖ-
ÎÏ ÒÅÛÉÔØ ÅÄÉÎÓÔ×ÅÎÎÙÍ ÏÂÒÁÚÏÍ. (äÏËÁÚÁÔÅÌØÓÔ×Ï ÜÔÏÊ ÔÅÏÒÅÍÙ ÔÒÕÄÎÏ É
ÎÅ ÐÒÉ×ÏÄÉÔÓÑ, ÎÁ ÒÕÓÓËÏÍ ÑÚÙËÅ ÏÎÏ ÅÓÔØ × ËÎÉÖËÅ á. é. íÁÌØÃÅ×Á ¥áÌÇÏ-
ÒÉÔÍÙ É ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ.)
áÎÁÌÏÇÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ×ÅÒÎÏ É ÄÌÑ ÎÕÍÅÒÁÃÉÊ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏ-
ÖÅÓÔ×.
§4. íÎÏÖÅÓÔ×Á ÎÏÍÅÒÏ×                                                   167

   ôÅÐÅÒØ ÌÅÇËÏ ÕËÁÚÁÔØ ÐÒÉÍÅÒ ×ÙÞÉÓÌÉÍÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎËÃÉÉ, ÎÅ
Ñ×ÌÑÀÝÅÊÓÑ ÇÌÁ×ÎÏÊ. äÏÓÔÁÔÏÞÎÏ ÓÄÅÌÁÔØ ÔÁË, ÞÔÏÂÙ ÎÉÇÄÅ ÎÅ ÏÐÒÅÄÅ̾ÎÎÁÑ
ÆÕÎËÃÉÑ ÉÍÅÌÁ ÅÄÉÎÓÔ×ÅÎÎÙÊ ÎÏÍÅÒ. üÔÏ ÎÅÓÌÏÖÎÏ. ðÕÓÔØ U(n, x) ¡ ÐÒÏ-
ÉÚ×ÏÌØÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎËÃÉÑ. òÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï D
×ÓÅÈ U-ÎÏÍÅÒÏ× ×ÓÅÈ ÆÕÎËÃÉÊ Ó ÎÅÐÕÓÔÏÊ ÏÂÌÁÓÔØÀ ÏÐÒÅÄÅÌÅÎÉÑ. ëÁË ÍÙ
ÕÖÅ ÇÏ×ÏÒÉÌÉ, ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÐÅÒÅÞÉÓÌÉÍÏ. òÁÓÓÍÏÔÒÉÍ ×ÓÀÄÕ ÏÐÒÅÄÅ̾Î-
ÎÕÀ ×ÙÞÉÓÌÉÍÕÀ ÆÕÎËÃÉÀ d, ÅÇÏ ÐÅÒÅÞÉÓÌÑÀÝÕÀ: D = {d(0), d(1), . . . }.
ôÅÐÅÒØ ÒÁÓÓÍÏÔÒÉÍ ÆÕÎËÃÉÀ V (i, x), ÄÌÑ ËÏÔÏÒÏÊ V (0, x) ÎÅ ÏÐÒÅÄÅÌÅÎÏ ÎÉ
ÐÒÉ ËÁËÏÍ x, Á V (i+1, x) = U(d(i), x). äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÆÕÎËÃÉÑ V0 ÎÉÇÄÅ ÎÅ
ÏÐÒÅÄÅÌÅÎÁ, Á ÆÕÎËÃÉÑ Vi+1 ÓÏ×ÐÁÄÁÅÔ Ó Ud(i) . ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÆÕÎËÃÉÑ V
×ÙÞÉÓÌÉÍÁ; ÏÎÁ ÕÎÉ×ÅÒÓÁÌØÎÁ ÐÏ ÐÏÓÔÒÏÅÎÉÀ, É ÅÄÉÎÓÔ×ÅÎÎÙÍ V -ÎÏÍÅÒÏÍ
ÎÉÇÄÅ ÎÅ ÏÐÒÅÄÅ̾ÎÎÏÊ ÆÕÎËÃÉÉ Ñ×ÌÑÅÔÓÑ ÞÉÓÌÏ 0.
   îÁ ÓÁÍÏÍ ÄÅÌÅ ÓÕÝÅÓÔ×ÕÀÔ É ÂÏÌÅÅ ÜËÚÏÔÉÞÅÓËÉÅ ÎÕÍÅÒÁÃÉÉ: ËÁË ÐÏËÁ-
ÚÁÌ æÒÉÄÂÅÒÇ, ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÕÎÉ×ÅÒÓÁÌØÎÕÀ ×ÙÞÉÓÌÉÍÕÀ ÆÕÎËÃÉÀ, ÄÌÑ
ËÏÔÏÒÏÊ ËÁÖÄÁÑ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ ÂÕÄÅÔ ÉÍÅÔØ ÒÏ×ÎÏ ÏÄÉÎ ÎÏÍÅÒ. óÏ-
ÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÎÕÍÅÒÁÃÉÉ ÎÁÚÙ×ÁÀÔ ÏÄÎÏÚÎÁÞÎÙÍÉ; ÏÞÅ×ÉÄÎÏ, ÏÎÉ ÎÅ ÍÏ-
ÇÕÔ ÂÙÔØ ÇÌÁ×ÎÙÍÉ. úÁÂÁ×ÎÁÑ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁ: ÍÏÖÎÏ ÒÁÚÒÁÂÏÔÁÔØ ÔÁËÏÊ
ÑÚÙË ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ, × ËÏÔÏÒÏÍ ËÁÖÄÕÀ ÐÒÏÇÒÁÍÍÉÓÔÓËÕÀ ÚÁÄÁÞÕ ÍÏÖ-
ÎÏ ÒÅÛÉÔØ ÅÄÉÎÓÔ×ÅÎÎÙÍ ÏÂÒÁÚÏÍ. (äÏËÁÚÁÔÅÌØÓÔ×Ï ÜÔÏÊ ÔÅÏÒÅÍÙ ÔÒÕÄÎÏ É
ÎÅ ÐÒÉ×ÏÄÉÔÓÑ, ÎÁ ÒÕÓÓËÏÍ ÑÚÙËÅ ÏÎÏ ÅÓÔØ × ËÎÉÖËÅ á. é. íÁÌØÃÅ×Á ¥áÌÇÏ-
ÒÉÔÍÙ É ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ.)
   áÎÁÌÏÇÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ×ÅÒÎÏ É ÄÌÑ ÎÕÍÅÒÁÃÉÊ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏ-
ÖÅÓÔ×.

Страницы