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

UptoLike

ВУЗ: 

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

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

Рубрика: 

184 çÌÁ×Á XII. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
åÓÌÉ ÍÙ ÚÁÐÉÓÙ×ÁÅÍ ÞÉÓÌÁ × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ, ÔÏ ÐÒÏÂÌÅÍÙ Ó ÐÅÒÅËÏ-
ÄÉÒÏ×ÁÎÉÅÍ ÐÒÉ ××ÏÄÅ-×Ù×ÏÄÅ ÍÉÎÉÍÁÌØÎÙ (ÎÁÄÏ ÌÉÛØ ÄÏÐÉÓÁÔØ ÎÕÌÉ ÄÌÑ
ÚÎÁÞÅÎÉÊ ÏÓÔÁÌØÎÙÈ ÐÅÒÅÍÅÎÎÙÈ × ÎÁÞÁÌÅ ÒÁÂÏÔÙ É ×ÓÔÁÔØ × ÎÕÖÎÏÅ ÍÅÓÔÏ
ÌÅÎÔÙ × ËÏÎÃÅ).
§3. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
óÅÊÞÁÓ ÍÙ ÄÏËÁÖÅÍ, ÞÔÏ ÆÕÎËÃÉÉ, ×ÙÞÉÓÌÉÍÙÅ ÐÒÏÇÒÁÍÍÁÍÉ Ó ËÏÎÅÞÎÙÍ
ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ, ÁÒÉÆÍÅÔÉÞÎÙ, ÔÏ ÅÓÔØ ÉÈ ÇÒÁÆÉËÉ Ñ×ÌÑÀÔÓÑ ÁÒÉÆÍÅ-
ÔÉÞÅÓËÉÍÉ ÍÎÏÖÅÓÔ×ÁÍÉ. ÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÍÙ ×ÎÏ×Ø ÐÒÅÄÐÏÌÁÇÁÅÍ ÎÅËÏÔÏÒÏÅ
ÚÎÁËÏÍÓÔ×Ï ÞÉÔÁÔÅÌÑ Ó ÌÏÇÉÞÅÓËÉÍÉ ÏÂÏÚÎÁÞÅÎÉÑÍÉ, É ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ-
×ÁÔØ ÁÒÉÆÍÅÔÉÞÅÓËÉÅ ÆÏÒÍÕÌÙ, ÓÏÄÅÒÖÁÝÉÅ ÐÅÒÅÍÅÎÎÙÅ ÐÏ ÎÁÔÕÒÁÌØÎÙÍ
ÞÉÓÌÁÍ, ÒÁ×ÅÎÓÔ×Ï, ËÏÎÓÔÁÎÔÙ 0 É 1, ÏÐÅÒÁÃÉÉ ÓÌÏÖÅÎÉÑ É ÕÍÎÏÖÅÎÉÑ, ÌÏ-
ÇÉÞÅÓËÉÅ Ó×ÑÚËÉ (é, éìé, îå) É Ë×ÁÎÔÏÒÙ ¥ÄÌÑ ×ÓÅÈ¥ É ¥ÓÕÝÅÓÔ×ÕÅÔ¥.
æÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÍÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ÓÉÇÎÁÔÕÒÕ, ÓÏÄÅÒÖÁÝÕÀ ÅÄÉÎÓÔ×ÅÎ-
ÎÙÊ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ (ÒÁ×ÅÎÓÔ×Ï), Ä×Å ËÏÎÓÔÁÎÔÙ 0 É 1 É
Ä×Á Ä×ÕÍÅÓÔÎÙÈ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÓÉÍ×ÏÌÁ (ÓÌÏÖÅÎÉÅ É ÕÍÎÏÖÅÎÉÅ). çÏ×ÏÒÑ
Ï ÉÓÔÉÎÎÏÓÔÉ ÔÁËÉÈ ÆÏÒÍÕÌ, ÍÙ ÉÍÅÅÍ × ×ÉÄÕ ÉÈ ÉÓÔÉÎÎÏÓÔØ × ÓÔÁÎÄÁÒÔ-
ÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÎÏÓÉÔÅÌÅÍ ËÏÔÏÒÏÊ Ñ×ÌÑÅÔÓÑ ÍÎÏÖÅÓÔ×Ï N ÎÁÔÕÒÁÌØÎÙÈ
ÞÉÓÅÌ.
íÎÏÖÅÓÔ×Ï A ⊂ N
k
ÎÁÚÙ×ÁÅÔÓÑ ÁÒÉÆÍÅÔÉÞÅÓËÉÍ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÅÔ ÁÒÉÆ-
ÍÅÔÉÞÅÓËÁÑ ÆÏÒÍÕÌÁ α Ó ÐÁÒÁÍÅÔÒÁÍÉ x
1
, . . . , x
k
, ËÏÔÏÒÁÑ ÅÇÏ ÐÒÅÄÓÔÁ×ÌÑÅÔ ×
ÓÌÅÄÕÀÝÅÍ ÓÍÙÓÌÅ: hn
1
, . . . , n
k
i ∈ A ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒÍÕÌÁ α
ÉÓÔÉÎÎÁ ÐÒÉ ÚÎÁÞÅÎÉÑÈ ÐÁÒÁÍÅÔÒÏ× x
1
= n
1
, . . . ,x
k
= n
k
.
ôÅÏÒÅÍÁ 71. çÒÁÆÉË ÌÀÂÏÊ ÆÕÎËÃÉÉ, ×ÙÞÉÓÌÑÅÍÏÊ ÐÒÏÇÒÁÍÍÏÊ Ó ËÏ-
ÎÅÞÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ, Ñ×ÌÑÅÔÓÑ ÁÒÉÆÍÅÔÉÞÅÓËÉÍ ÍÎÏÖÅÓÔ×ÏÍ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ f : N → N ¡ ÆÕÎËÃÉÑ, ×ÙÞÉÓÌÉÍÁÑ ÎÅËÏÔÏÒÏÊ
ÐÒÏÇÒÁÍÍÏÊ P Ó ËÏÎÅÞÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ k
1
, . . . , k
N
. âÕÄÅÍ ÓÞÉÔÁÔØ,
ÞÔÏ ×ÈÏÄÎÏÊ ÐÅÒÅÍÅÎÎÏÊ Ñ×ÌÑÅÔÓÑ k
1
, Á ×ÙÈÏÄÎÏÊ ¡ k
2
. îÁÍ ÎÕÖÎÏ ÎÁÐÉ-
ÓÁÔØ ÆÏÒÍÕÌÕ Ó Ä×ÕÍÑ ÐÅÒÅÍÅÎÎÙÍÉ x, y, ËÏÔÏÒÁÑ ÂÙÌÁ ÂÙ ÉÓÔÉÎÎÁ ÔÏÇÄÁ
É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ y = f(x). óÏÓÔÏÑÎÉÅ ÐÒÏÇÒÁÍÍÙ Ó ËÏÎÅÞÎÙÍ ÞÉÓÌÏÍ
ÐÅÒÅÍÅÎÎÙÈ ÐÏÌÎÏÓÔØÀ ÏÐÉÓÙ×ÁÅÔÓÑ ÚÎÁÞÅÎÉÑÍÉ ÐÅÒÅÍÅÎÎÙÈ É ÎÏÍÅÒÏÍ ÔÅ-
ËÕÝÅÊ ËÏÍÁÎÄÙ (× ÐÒÏÃÅÓÓÏÒÁÈ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÒÅÇÉÓÔÒ ÞÁÓÔÏ ÎÁÚÙ×ÁÀÔ
program counter, ÐÏ-ÒÕÓÓËÉ ÓÞ¾ÔÞÉË ËÏÍÁÎÄ). ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÓÏÏÔ×ÅÔ-
ÓÔ×ÉÅ ÍÅÖÄÕ Ä×ÕÍÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÍÉ ÓÏÓÔÏÑÎÉÑÍÉ ÐÒÏÇÒÁÍÍÙ Ó ËÏÎÅÞ-
ÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ ÁÒÉÆÍÅÔÉÞÎÏ. íÙ ÉÍÅÅÍ × ×ÉÄÕ, ÞÔÏ ÍÏÖÎÏ ÎÁÐÉ-
ÓÁÔØ ÁÒÉÆÍÅÔÉÞÅÓËÕÀ ÆÏÒÍÕÌÕ
Step(s
1
, . . . , s
N
, p, s
0
1
, . . . , s
0
N
, p
0
),
184                    çÌÁ×Á XII. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ

   åÓÌÉ ÍÙ ÚÁÐÉÓÙ×ÁÅÍ ÞÉÓÌÁ × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ, ÔÏ ÐÒÏÂÌÅÍÙ Ó ÐÅÒÅËÏ-
ÄÉÒÏ×ÁÎÉÅÍ ÐÒÉ ××ÏÄÅ-×Ù×ÏÄÅ ÍÉÎÉÍÁÌØÎÙ (ÎÁÄÏ ÌÉÛØ ÄÏÐÉÓÁÔØ ÎÕÌÉ ÄÌÑ
ÚÎÁÞÅÎÉÊ ÏÓÔÁÌØÎÙÈ ÐÅÒÅÍÅÎÎÙÈ × ÎÁÞÁÌÅ ÒÁÂÏÔÙ É ×ÓÔÁÔØ × ÎÕÖÎÏÅ ÍÅÓÔÏ
ÌÅÎÔÙ × ËÏÎÃÅ).


  §3. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
   óÅÊÞÁÓ ÍÙ ÄÏËÁÖÅÍ, ÞÔÏ ÆÕÎËÃÉÉ, ×ÙÞÉÓÌÉÍÙÅ ÐÒÏÇÒÁÍÍÁÍÉ Ó ËÏÎÅÞÎÙÍ
ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ, ÁÒÉÆÍÅÔÉÞÎÙ, ÔÏ ÅÓÔØ ÉÈ ÇÒÁÆÉËÉ Ñ×ÌÑÀÔÓÑ ÁÒÉÆÍÅ-
ÔÉÞÅÓËÉÍÉ ÍÎÏÖÅÓÔ×ÁÍÉ. ÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÍÙ ×ÎÏ×Ø ÐÒÅÄÐÏÌÁÇÁÅÍ ÎÅËÏÔÏÒÏÅ
ÚÎÁËÏÍÓÔ×Ï ÞÉÔÁÔÅÌÑ Ó ÌÏÇÉÞÅÓËÉÍÉ ÏÂÏÚÎÁÞÅÎÉÑÍÉ, É ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ-
×ÁÔØ ÁÒÉÆÍÅÔÉÞÅÓËÉÅ ÆÏÒÍÕÌÙ, ÓÏÄÅÒÖÁÝÉÅ ÐÅÒÅÍÅÎÎÙÅ ÐÏ ÎÁÔÕÒÁÌØÎÙÍ
ÞÉÓÌÁÍ, ÒÁ×ÅÎÓÔ×Ï, ËÏÎÓÔÁÎÔÙ 0 É 1, ÏÐÅÒÁÃÉÉ ÓÌÏÖÅÎÉÑ É ÕÍÎÏÖÅÎÉÑ, ÌÏ-
ÇÉÞÅÓËÉÅ Ó×ÑÚËÉ (é, éìé, îå) É Ë×ÁÎÔÏÒÙ ¥ÄÌÑ ×ÓÅÈ¥ É ¥ÓÕÝÅÓÔ×ÕÅÔ¥.
æÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÍÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ÓÉÇÎÁÔÕÒÕ, ÓÏÄÅÒÖÁÝÕÀ ÅÄÉÎÓÔ×ÅÎ-
ÎÙÊ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ (ÒÁ×ÅÎÓÔ×Ï), Ä×Å ËÏÎÓÔÁÎÔÙ 0 É 1 É
Ä×Á Ä×ÕÍÅÓÔÎÙÈ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÓÉÍ×ÏÌÁ (ÓÌÏÖÅÎÉÅ É ÕÍÎÏÖÅÎÉÅ). çÏ×ÏÒÑ
Ï ÉÓÔÉÎÎÏÓÔÉ ÔÁËÉÈ ÆÏÒÍÕÌ, ÍÙ ÉÍÅÅÍ × ×ÉÄÕ ÉÈ ÉÓÔÉÎÎÏÓÔØ × ÓÔÁÎÄÁÒÔ-
ÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÎÏÓÉÔÅÌÅÍ ËÏÔÏÒÏÊ Ñ×ÌÑÅÔÓÑ ÍÎÏÖÅÓÔ×Ï N ÎÁÔÕÒÁÌØÎÙÈ
ÞÉÓÅÌ.
   íÎÏÖÅÓÔ×Ï A ⊂ Nk ÎÁÚÙ×ÁÅÔÓÑ ÁÒÉÆÍÅÔÉÞÅÓËÉÍ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÅÔ ÁÒÉÆ-
ÍÅÔÉÞÅÓËÁÑ ÆÏÒÍÕÌÁ α Ó ÐÁÒÁÍÅÔÒÁÍÉ x1 , . . . , xk , ËÏÔÏÒÁÑ ÅÇÏ ÐÒÅÄÓÔÁ×ÌÑÅÔ ×
ÓÌÅÄÕÀÝÅÍ ÓÍÙÓÌÅ: hn1 , . . . , nk i ∈ A ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒÍÕÌÁ α
ÉÓÔÉÎÎÁ ÐÒÉ ÚÎÁÞÅÎÉÑÈ ÐÁÒÁÍÅÔÒÏ× x1 = n1 , . . . ,xk = nk .
   ôÅÏÒÅÍÁ 71. çÒÁÆÉË ÌÀÂÏÊ ÆÕÎËÃÉÉ, ×ÙÞÉÓÌÑÅÍÏÊ ÐÒÏÇÒÁÍÍÏÊ Ó ËÏ-
ÎÅÞÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ, Ñ×ÌÑÅÔÓÑ ÁÒÉÆÍÅÔÉÞÅÓËÉÍ ÍÎÏÖÅÓÔ×ÏÍ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ f : N → N ¡ ÆÕÎËÃÉÑ, ×ÙÞÉÓÌÉÍÁÑ ÎÅËÏÔÏÒÏÊ
ÐÒÏÇÒÁÍÍÏÊ P Ó ËÏÎÅÞÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ k1, . . . , kN . âÕÄÅÍ ÓÞÉÔÁÔØ,
ÞÔÏ ×ÈÏÄÎÏÊ ÐÅÒÅÍÅÎÎÏÊ Ñ×ÌÑÅÔÓÑ k1 , Á ×ÙÈÏÄÎÏÊ ¡ k2 . îÁÍ ÎÕÖÎÏ ÎÁÐÉ-
ÓÁÔØ ÆÏÒÍÕÌÕ Ó Ä×ÕÍÑ ÐÅÒÅÍÅÎÎÙÍÉ x, y, ËÏÔÏÒÁÑ ÂÙÌÁ ÂÙ ÉÓÔÉÎÎÁ ÔÏÇÄÁ
É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ y = f (x). óÏÓÔÏÑÎÉÅ ÐÒÏÇÒÁÍÍÙ Ó ËÏÎÅÞÎÙÍ ÞÉÓÌÏÍ
ÐÅÒÅÍÅÎÎÙÈ ÐÏÌÎÏÓÔØÀ ÏÐÉÓÙ×ÁÅÔÓÑ ÚÎÁÞÅÎÉÑÍÉ ÐÅÒÅÍÅÎÎÙÈ É ÎÏÍÅÒÏÍ ÔÅ-
ËÕÝÅÊ ËÏÍÁÎÄÙ (× ÐÒÏÃÅÓÓÏÒÁÈ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÒÅÇÉÓÔÒ ÞÁÓÔÏ ÎÁÚÙ×ÁÀÔ
program counter, ÐÏ-ÒÕÓÓËÉ ÓÞ¾ÔÞÉË ËÏÍÁÎÄ). ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÓÏÏÔ×ÅÔ-
ÓÔ×ÉÅ ÍÅÖÄÕ Ä×ÕÍÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÍÉ ÓÏÓÔÏÑÎÉÑÍÉ ÐÒÏÇÒÁÍÍÙ Ó ËÏÎÅÞ-
ÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ ÁÒÉÆÍÅÔÉÞÎÏ. íÙ ÉÍÅÅÍ × ×ÉÄÕ, ÞÔÏ ÍÏÖÎÏ ÎÁÐÉ-
ÓÁÔØ ÁÒÉÆÍÅÔÉÞÅÓËÕÀ ÆÏÒÍÕÌÕ
                       Step(s1 , . . . , sN , p, s01, . . . , s0N , p0),

Страницы