Дискретная математика. Кулабухов С.Ю. - 145 стр.

                                                       x 4. aLGORITMI^ESKI NERAZREIMYE PROBLEMY

tEOREMA 1. sOWOKUPNOSTX WSEH OB]EZNA^IMYH FORMUL ALGEBRY PREDIKATOW QWLQETSQ NEREKUR           -
SIWNYM MNOVESTWOM.
   oDNAKO, OTSUTSTWIE ALGORITMA, POZWOLQ@]EGO USTANOWITX QWLQETSQ LI PROIZWOLXNAQ FORMULA
ALGEBRY PREDIKATOW OB]EZNA^IMOJ, E]E NE OZNA^AET, ^TO DLQ KAVDOJ KONKRETNOJ FORMULY \TOT
WOPROS NELXZQ REITX. bOLEE TOGO, SU]ESTWU@T ALGORITMY, POZWOLQ@]IE OPREDELQTX OB]EZNA-
^IMOSTX FORMULY DLQ NEKOTORYH ^ASTNYH WIDOW FORMUL. nAPRIMER, IZWESTNO, ^TO DLQ FORMUL
ALGEBRY PREDIKATOW, SODERVA]IH TOLXKO ODNOMESTNYE PREDIKATNYE PEREMENNYE \TA PROBLEMA
IMEET REENIE. sU]ESTWU@T I NEKOTORYE DRUGIE MNOVESTWA FORMUL ALGEBRY PREDIKATOW, KOTO-
RYE QWLQ@TSQ REKURSIWNYMI, TO ESTX DLQ KOTORYH ALGORITMI^ESKAQ PROBLEMA OB]EZNA^IMOSTI
RAZREIMA.

    4.5. dIOFANTOWY URAWNENIQ. pUSTX F(x1
 x2
 : : :
 xn) | MNOGO^LEN OT PEREMENNYH x1,
x2
 : : :
 xn S CELYMI KO\FFICIENTAMI. uRAWNENIE WIDA
                                      F(x1
 x2
 : : :
 xn) = 0

NAZYWAETSQ DIOFANTOWYM . nA MEVDUNARODNOM MATEMATI^ESKOM KONGRESSE W pARIVE W 1901 GODU
d. gILXBERTOM BYLA SFORMULIROWANA ODNA IZ NAIBOLEE ZNAMENITYH ALGORITMI^ESKIH PROBLEM
MATEMATIKI: \nAJTI ALGORITM, POZWOLQ@]IJ DLQ L@BOGO DIOFANTOWA URAWNENIQ OPREDELITX EGO
RAZREIMOSTX ILI NERAZREIMOSTX W CELYH ^ISLAH". |TA PROBLEMA IZWESTNA KAK 10-Q PROBLEMA
gILXBERTA.
   |TA I MNOGIE DRUGIE ALGORITMI^ESKIE PROBLEMY STIMULIROWALI POQWLENIE W 30-H GODAH NA-
EGO STOLETIQ I DALXNEJEE BURNOE RAZWITIE TEORII ALGORITMOW. 10-Q VE PROBLEMA gILXBERTA
BYLA OTRICATELXNO REENA W 1970 GODU. sOWETSKIM MATEMATIKOM `. w. mATIQSEWI^EM BYLA
DOKAZANA ALGORITMI^ESKAQ NERAZREIMOSTX W OB]EM WIDE 10-OJ PROBLEMY gILXBERTA.
   e]E RAZ OTMETIM, ^TO ALGORITMI^ESKAQ NERAZREIMOSTX OZNA^AET LIX OTSUTSTWIE EDINOGO
SPOSOBA DLQ REENIQ WSEH EDINI^NYH ZADA^ DANNOJ SERII, W TO WREMQ KAK KAVDAQ INDIWIDUALXNAQ
ZADA^A SERII WPOLNE MOVET BYTX REENA SWOIM INDIWIDUALXNYM SPOSOBOM. bOLEE TOGO, MOVET
SU]ESTWOWATX ALGORITM DLQ REENIQ ZADA^ NEKOTOROGO BESKONE^NOGO PODKLASSA DANNOGO KLASSA
ZADA^. nAPRIMER, DLQ ^ASTNOGO SLU^AQ DIOFANTOWA URAWNENIQ
                  an xn + an;1xn;1 + : : : + a1x + a0 = 0
 GDE a0
 : : :
 an 2 N0            (1)
HOROO IZWESTNO, ^TO WSE EGO CELYE KORNI SLEDUET ISKATX SREDI DELITELEJ SWOBODNOGO ^LENA a0.
tAKIM OBRAZOM, DLQ KLASSA DIOFANTOWYH URAWNENIJ, SOSTOQ]EGO IZ URAWNENIJ WIDA (1) SU]EST-
WUET ALGORITM, POZWOLQ@]IJ NAHODITX WSE CELYE REENIQ KAVDOGO URAWNENIQ \TOGO KLASSA.

   4.6. nOWYE TERMINY. nEWY^ISLIMAQ FUNKCIQ. hARAKTERISTI^ESKAQ FUNKCIQ DANNOGO
MNOVESTWA. rEKURSIWNOE MNOVESTWO. pROBLEMA WHOVDENIQ. uSE^ENNAQ RAZNOSTX. dIOFANTOWO URA-
WNENIE.

   4.7. kONTROLXNYE WOPROSY.
  1. iZ KAKIH OB]IH SOOBRAVENIJ SLEDUET SU]ESTWOWANIE NEWY^ISLIMYH FUNKCIJ?
  2. sLEDUET LI IZ REKURSIWNOSTI DANNOGO ^ISLOWOGO MNOVESTWA SU]ESTWOWANIE ALGORITMA, POZ-
     WOLQ@]EGO OPREDELITX, QWLQETSQ LI PROIZWOLXNOE ^ISLO \LEMENTOM \TOGO MNOVESTWA ILI
     NET?
  3. qWLQETSQ LI REKURSIWNYM MNOVESTWO WSEH ^ETNYH ^ISEL?
  4. oPIITE ALGORITM NAHOVDENIQ WSEH CELYH KORNEJ MNOGO^LENA OT x S CELYMI KO\FFICIEN-
     TAMI.
                                                145