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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§2. ÷ÙÞÉÓÌÉÍÙÅ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÆÕÎËÃÉÊ 161
úÁÄÁÞÁ 189. ðÕÓÔØ U ¡ Ä×ÕÍÅÓÔÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎË-
ÃÉÑ ÄÌÑ ËÌÁÓÓÁ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. åÓÌÉ ÓÕÝÅÓÔ×Õ-
ÅÔ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÁÑ ÆÕÎËÃÉÑ, ËÏÔÏÒÁÑ ÐÏ ÎÏÍÅÒÁÍ p É q Ä×ÕÈ ÆÕÎËÃÉÊ
ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ÄÁ¾Ô ËÁËÏÊ-ÌÉÂÏ ÎÏÍÅÒ ÉÈ ËÏÍÐÏÚÉÃÉÉ, ÔÏ ÆÕÎËÃÉÑ U
Ñ×ÌÑÅÔÓÑ ÇÌÁ×ÎÏÊ. (õËÁÚÁÎÉÅ: ÐÏËÁÖÉÔÅ, ÞÔÏ ÐÏ k ÍÏÖÎÏ ÁÌÇÏÒÉÔÍÉÞÅ-
ÓËÉ ÐÏÌÕÞÁÔØ U-ÎÏÍÅÒ ÆÕÎËÃÉÉ x 7→ [k, x].)
åÓÔÅÓÔ×ÅÎÎÙÊ ×ÏÐÒÏÓ: ÓÕÝÅÓÔ×ÕÀÔ ÌÉ ×ÙÞÉÓÌÉÍÙÅ ÕÎÉ×ÅÒÓÁÌØÎÙÅ ÆÕÎË-
ÃÉÉ, ÎÅ Ñ×ÌÑÀÝÉÅÓÑ ÇÌÁ×ÎÙÍÉ? íÙ Õ×ÉÄÉÍ ÄÁÌØÛÅ, ÞÔÏ ÓÕÝÅÓÔ×ÕÀÔ.
úÁÄÁÞÁ 190. éÚÍÅÎÉÍ ÏÐÒÅÄÅÌÅÎÉÅ ÇÌÁ×ÎÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎËÃÉÉ É
ÂÕÄÅÍ ÔÒÅÂÏ×ÁÔØ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ¥ÔÒÁÎÓÌÑÔÏÒÁ¥ s ÌÉÛØ ÄÌÑ ÕÎÉ×ÅÒÓÁÌØ-
ÎÙÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ V (Á ÎÅ ÄÌÑ ÌÀÂÙÈ, ËÁË ÒÁÎØÛÅ). ðÏËÁÖÉÔÅ,
ÞÔÏ ÎÏ×ÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÜË×É×ÁÌÅÎÔÎÏ ÓÔÁÒÏÍÕ. (õËÁÚÁÎÉÅ: ÌÀÂÕÀ ÆÕÎË-
ÃÉÀ ÍÏÖÎÏ ÉÓËÕÓÓÔ×ÅÎÎÏ ÐÅÒÅÄÅÌÁÔØ × ÕÎÉ×ÅÒÓÁÌØÎÕÀ, ¥ÒÁÓÔ×ÏÒÉ×¥ × ÎÅÊ
ÌÀÂÕÀ ÄÒÕÇÕÀ ÕÎÉ×ÅÒÓÁÌØÎÕÀ ÆÕÎËÃÉÀ.)
úÁÄÁÞÁ 191. ðÕÓÔØ U ¡ ÇÌÁ×ÎÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎËÃÉÑ. äÏËÁÖÉÔÅ,
ÞÔÏ ÄÌÑ ÌÀÂÏÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ V (m, n, x) ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÁÑ ×ÓÀÄÕ
ÏÐÒÅÄÅ̾ÎÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ s(m, n), ÞÔÏ V (m, n, x) = U(s(m, n), x)
ÐÒÉ ×ÓÅÈ m, n É x. (õËÁÚÁÎÉÅ: ÏÂßÅÄÉÎÉÔØ m É n × ÐÁÒÕ.)
§2. ÷ÙÞÉÓÌÉÍÙÅ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ
×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
ðÕÓÔØ ÄÁÎÁ ÎÅËÏÔÏÒÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ f
0
, f
1
, . . . ×ÙÞÉÓÌÉÍÙÈ ÆÕÎË-
ÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. íÙ ÈÏÔÉÍ ÐÒÉÄÁÔØ ÓÍÙÓÌ ×ÙÒÁÖÅÎÉÀ ¥ÐÏÓÌÅÄÏ×Á-
ÔÅÌØÎÏÓÔØ i 7→ f
i
×ÙÞÉÓÌÉÍÁ¥. üÔÏ ÍÏÖÎÏ ÓÄÅÌÁÔØ Ä×ÕÍÑ ÓÐÏÓÏÂÁÍÉ:
• ÍÏÖÎÏ ÎÁÚÙ×ÁÔØ ÜÔÕ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ×ÙÞÉÓÌÉÍÏÊ, ÅÓÌÉ ÆÕÎËÃÉÑ F
Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×, ÚÁÄÁÎÎÁÑ ÆÏÒÍÕÌÏÊ F (i, n) = f
i
(n), Ñ×ÌÑÅÔÓÑ ×ÙÞÉ-
ÓÌÉÍÏÊ.
• ÍÏÖÎÏ ÎÁÚÙ×ÁÔØ ÜÔÕ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ×ÙÞÉÓÌÉÍÏÊ, ÅÓÌÉ ÓÕÝÅ-
ÓÔ×ÕÅÔ ×ÙÞÉÓÌÉÍÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÞÉÓÅÌ c
0
, c
1
, . . . , ÄÌÑ ËÏÔÏÒÏÊ
c
i
Ñ×ÌÑÅÔÓÑ ÏÄÎÉÍ ÉÚ ÎÏÍÅÒÏ× ÆÕÎËÃÉÉ f
i
.
÷ÔÏÒÏÅ ÏÐÒÅÄÅÌÅÎÉÅ (× ÏÔÌÉÞÉÅ ÏÔ ÐÅÒ×ÏÇÏ) ÚÁ×ÉÓÉÔ ÏÔ ×ÙÂÏÒÁ ÎÕÍÅÒÁ-
ÃÉÉ.
ôÅÏÒÅÍÁ 60. åÓÌÉ ÎÕÍÅÒÁÃÉÑ Ñ×ÌÑÅÔÓÑ ×ÙÞÉÓÌÉÍÏÊ (ÔÏ ÅÓÔØ ÓÏÏÔ-
×ÅÔÓÔ×ÕÀÝÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎËÃÉÑ ×ÙÞÉÓÌÉÍÁ), ÔÏ ÉÚ ×ÔÏÒÏÇÏ ÏÐÒÅ-
ÄÅÌÅÎÉÑ ÓÌÅÄÕÅÔ ÐÅÒ×ÏÅ. åÓÌÉ ÎÕÍÅÒÁÃÉÑ Ñ×ÌÑÅÔÓÑ Ë ÔÏÍÕ ÖÅ ÇÌÁ×ÎÏÊ, ÔÏ
ÉÚ ÐÅÒ×ÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ ÓÌÅÄÕÅÔ ×ÔÏÒÏÅ.
§2. ÷ÙÞÉÓÌÉÍÙÅ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÆÕÎËÃÉÊ                                161

   úÁÄÁÞÁ 189. ðÕÓÔØ U ¡ Ä×ÕÍÅÓÔÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎË-
ÃÉÑ ÄÌÑ ËÌÁÓÓÁ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. åÓÌÉ ÓÕÝÅÓÔ×Õ-
ÅÔ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÁÑ ÆÕÎËÃÉÑ, ËÏÔÏÒÁÑ ÐÏ ÎÏÍÅÒÁÍ p É q Ä×ÕÈ ÆÕÎËÃÉÊ
ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ÄÁ¾Ô ËÁËÏÊ-ÌÉÂÏ ÎÏÍÅÒ ÉÈ ËÏÍÐÏÚÉÃÉÉ, ÔÏ ÆÕÎËÃÉÑ U
Ñ×ÌÑÅÔÓÑ ÇÌÁ×ÎÏÊ. (õËÁÚÁÎÉÅ: ÐÏËÁÖÉÔÅ, ÞÔÏ ÐÏ k ÍÏÖÎÏ ÁÌÇÏÒÉÔÍÉÞÅ-
ÓËÉ ÐÏÌÕÞÁÔØ U-ÎÏÍÅÒ ÆÕÎËÃÉÉ x 7→ [k, x].)
  åÓÔÅÓÔ×ÅÎÎÙÊ ×ÏÐÒÏÓ: ÓÕÝÅÓÔ×ÕÀÔ ÌÉ ×ÙÞÉÓÌÉÍÙÅ ÕÎÉ×ÅÒÓÁÌØÎÙÅ ÆÕÎË-
ÃÉÉ, ÎÅ Ñ×ÌÑÀÝÉÅÓÑ ÇÌÁ×ÎÙÍÉ? íÙ Õ×ÉÄÉÍ ÄÁÌØÛÅ, ÞÔÏ ÓÕÝÅÓÔ×ÕÀÔ.
   úÁÄÁÞÁ 190. éÚÍÅÎÉÍ ÏÐÒÅÄÅÌÅÎÉÅ ÇÌÁ×ÎÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎËÃÉÉ É
ÂÕÄÅÍ ÔÒÅÂÏ×ÁÔØ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ¥ÔÒÁÎÓÌÑÔÏÒÁ¥ s ÌÉÛØ ÄÌÑ ÕÎÉ×ÅÒÓÁÌØ-
ÎÙÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ V (Á ÎÅ ÄÌÑ ÌÀÂÙÈ, ËÁË ÒÁÎØÛÅ). ðÏËÁÖÉÔÅ,
ÞÔÏ ÎÏ×ÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÜË×É×ÁÌÅÎÔÎÏ ÓÔÁÒÏÍÕ. (õËÁÚÁÎÉÅ: ÌÀÂÕÀ ÆÕÎË-
ÃÉÀ ÍÏÖÎÏ ÉÓËÕÓÓÔ×ÅÎÎÏ ÐÅÒÅÄÅÌÁÔØ × ÕÎÉ×ÅÒÓÁÌØÎÕÀ, ¥ÒÁÓÔ×ÏÒÉ×¥ × ÎÅÊ
ÌÀÂÕÀ ÄÒÕÇÕÀ ÕÎÉ×ÅÒÓÁÌØÎÕÀ ÆÕÎËÃÉÀ.)
  úÁÄÁÞÁ 191. ðÕÓÔØ U ¡ ÇÌÁ×ÎÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎËÃÉÑ. äÏËÁÖÉÔÅ,
ÞÔÏ ÄÌÑ ÌÀÂÏÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ V (m, n, x) ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÁÑ ×ÓÀÄÕ
ÏÐÒÅÄÅ̾ÎÎÁÑ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ s(m, n), ÞÔÏ V (m, n, x) = U(s(m, n), x)
ÐÒÉ ×ÓÅÈ m, n É x. (õËÁÚÁÎÉÅ: ÏÂßÅÄÉÎÉÔØ m É n × ÐÁÒÕ.)

  §2. ÷ÙÞÉÓÌÉÍÙÅ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ
   ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
   ðÕÓÔØ ÄÁÎÁ ÎÅËÏÔÏÒÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ f0, f1, . . . ×ÙÞÉÓÌÉÍÙÈ ÆÕÎË-
ÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. íÙ ÈÏÔÉÍ ÐÒÉÄÁÔØ ÓÍÙÓÌ ×ÙÒÁÖÅÎÉÀ ¥ÐÏÓÌÅÄÏ×Á-
ÔÅÌØÎÏÓÔØ i 7→ fi ×ÙÞÉÓÌÉÍÁ¥. üÔÏ ÍÏÖÎÏ ÓÄÅÌÁÔØ Ä×ÕÍÑ ÓÐÏÓÏÂÁÍÉ:
    • ÍÏÖÎÏ ÎÁÚÙ×ÁÔØ ÜÔÕ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ×ÙÞÉÓÌÉÍÏÊ, ÅÓÌÉ ÆÕÎËÃÉÑ F
      Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×, ÚÁÄÁÎÎÁÑ ÆÏÒÍÕÌÏÊ F (i, n) = fi(n), Ñ×ÌÑÅÔÓÑ ×ÙÞÉ-
      ÓÌÉÍÏÊ.
    • ÍÏÖÎÏ ÎÁÚÙ×ÁÔØ ÜÔÕ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ×ÙÞÉÓÌÉÍÏÊ, ÅÓÌÉ ÓÕÝÅ-
      ÓÔ×ÕÅÔ ×ÙÞÉÓÌÉÍÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÞÉÓÅÌ c0 , c1, . . . , ÄÌÑ ËÏÔÏÒÏÊ
      ci Ñ×ÌÑÅÔÓÑ ÏÄÎÉÍ ÉÚ ÎÏÍÅÒÏ× ÆÕÎËÃÉÉ fi .
   ÷ÔÏÒÏÅ ÏÐÒÅÄÅÌÅÎÉÅ (× ÏÔÌÉÞÉÅ ÏÔ ÐÅÒ×ÏÇÏ) ÚÁ×ÉÓÉÔ ÏÔ ×ÙÂÏÒÁ ÎÕÍÅÒÁ-
ÃÉÉ.
   ôÅÏÒÅÍÁ 60. åÓÌÉ ÎÕÍÅÒÁÃÉÑ Ñ×ÌÑÅÔÓÑ ×ÙÞÉÓÌÉÍÏÊ (ÔÏ ÅÓÔØ ÓÏÏÔ-
×ÅÔÓÔ×ÕÀÝÁÑ ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÆÕÎËÃÉÑ ×ÙÞÉÓÌÉÍÁ), ÔÏ ÉÚ ×ÔÏÒÏÇÏ ÏÐÒÅ-
ÄÅÌÅÎÉÑ ÓÌÅÄÕÅÔ ÐÅÒ×ÏÅ. åÓÌÉ ÎÕÍÅÒÁÃÉÑ Ñ×ÌÑÅÔÓÑ Ë ÔÏÍÕ ÖÅ ÇÌÁ×ÎÏÊ, ÔÏ
ÉÚ ÐÅÒ×ÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ ÓÌÅÄÕÅÔ ×ÔÏÒÏÅ.

Страницы