Кіріспе
Диофантикалық теңдеудің шешімі Математикада Диофантикалық теңдеу P(x1, …, xj, y1, …, yk) = 0 (әдетте P( , ) = 0) түріндегі теңдеу, мұнда P( , ) – x1, …, xj параметрлерді, y1, …, yk белгісіздерді көрсететін бүтін сандар коэффициенттері бар полиномиал. Диофантикалық жиын – S, табиғи сандардың барлық j-туплиялары жиынтығы, сондықтан кейбір Диофантикалық теңдеу үшін P( , ) = 0 орындалады.
In mathematics, a Diophantine equation is an equation of the form P(x1, , xj, y1, , yk) = 0 (usually abbreviated P(, ) = 0) where P(, ) is a polynomial with integer coefficients, where x1, , xj indicate parameters and y1, , yk indicate unknowns. A Diophantine set is a subset S of , the set of all j tuples of natural numbers, so that for some Diophantine equation P(, ) = 0,
That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. The use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability theory and model theory. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. Also it is sufficient to assume P is a polynomial over and multiply P by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem. The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is computably enumerable. A set of integers S is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of S and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or computability theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work. Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problem was to find a general algorithm that can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.
Яғни, параметрлік мән Диофантикалық жиын S-те болады, егер және тек қана егер сәйкес Диофантикалық теңдеу сол параметрлік мән бойынша орындалса. S-те де, экзистенциалдық сандық есепте де табиғи сандарды қолдану есептеу теориясы мен модель теориясындағы әдеттегі қолданыстарды ғана көрсетеді. Табиғи сандар теріс емес бүтін сандар жиынтығына немесе оң бүтін сандарға қатысты ма, жоқ па, маңызды емес, өйткені Диофантикалық жиын үшін екі анықтама да тең. Сонымен қатар біз бүтін сандардың Диофантикалық жиыны туралы да айтуға болады және табиғи сандар бойынша сандық есептеуді бүтін сандар бойынша сандық есептеумен еркін ауыстыруға болады. Сондай-ақ, P-ді полиномиалдық бөлшек деп санау және P-ді тиісті бөлгіштермен көбейту арқылы бүтін сан коэффициенттерін алу жеткілікті. Алайда, рационалды сандар бойынша сандық есептеуді бүтін сандар бойынша сандық есептеудің орнына қолдануға бола ма, жоқ па – бұл өте қиын, ашық мәселе. MRDP теоремасы (оның шешімін табуға негізгі төрт адам үлес қосқан атынан аталған) бүтін сандар жиыны егер және тек егер ол есептеу арқылы саналатын болса, онда ол Диофантикалық деп аталады. S бүтін сандар жиыны егер және тек егер бүтін сан берілген кезде, егер ол S мүшесі болса, тоқтап, басқаша мәңгілік жүретін алгоритм болса, есептелуге болады. Бұл жалпы Диофантикалық жиын түсінігі, әрине, сандар теориясына тиесілі, бірақ логикалық немесе есептеу теориялық терминдермен қарастырылуы мүмкін дегенді білдіреді. Алайда бұл анық емес, бұл бірнеше онжылдық жұмыстың қорытындысы болды. Матиясевичтің MRDP теоремасын толықтыруы Хилберттің оныншы проблемасын шешті. Хилберттің оныншы мәселесі – берілген Диофантикалық теңдеудің бүтін сандар арасында шешімі бар-жоғын анықтай алатын жалпы алгоритмді табу болды. Хилберттің оныншы мәселесі ресми математикалық мәлімдеме емес, бірақ шешім алгоритмін (философиялық тұрғыдан) жалпы есептік предикатпен сәйкестендірудің кең таралған қабылдануы оныншы мәселенің шешілмейтіндігі туралы қорытынды жасауға MRDP теоремасын пайдалануға мүмкіндік береді.
In mathematics, a Diophantine equation is an equation of the form P(x1, , xj, y1, , yk) = 0 (usually abbreviated P(, ) = 0) where P(, ) is a polynomial with integer coefficients, where x1, , xj indicate parameters and y1, , yk indicate unknowns. A Diophantine set is a subset S of , the set of all j tuples of natural numbers, so that for some Diophantine equation P(, ) = 0,
That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. The use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability theory and model theory. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. Also it is sufficient to assume P is a polynomial over and multiply P by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem. The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is computably enumerable. A set of integers S is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of S and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or computability theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work. Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problem was to find a general algorithm that can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.
Сынау әдісі
Юрий Матиясевич Диофантилік теңдеулердің шешімдері экспоненциалды түрде өсе алатынын көрсету үшін экспоненциалды түрде өсетін Фибоначчи сандарын қолданатын әдіс пайдаланды. Джулия Робинсон, Мартин Дэвис және Хилари Путнамның бұрынғы жұмыстары – сол себепті, MRDP – әрбір есептеуге болатын санамалы жиынның Диофантилік екенін көрсету үшін жеткілікті екенін көрсеткен.
Хилберттің оныншы проблемасына қолдану
Хилберттің оныншы мәселесі Диофанти теңдеулерінің шешімділігін анықтайтын жалпы алгоритмнің болуын сұрайды. Матиясевичтің нәтижесі және көптеген рекурсивті түрде саналатын тілдердің шешілмейтіндігінің фактісі Хилберттің оныншы мәселесіне шешім табу мүмкін емес екенін көрсетеді.
Тазартулар
Кейінгі зерттеулер көрсеткендей, Диофанти теңдеуінің шешімділігі мәселесі, егер теңдеуде тек 9 натурал сан айнымалысы (Матиясевич, 1977) немесе 11 бүтін сан айнымалысы (Цзи Вэй Сун, 1992) болса да, шешілмейді.