Abstract:
In this paper we give a detailed account of some results obtained by a group of specialists in mathematical logic in connection with an investigation of Hilbert's 10th problem. This problem was formulated in his well-known lecture [1], in the following way.
“10. The problem of the solubility of diophantine equations. Given a Diophantine equation in arbitrary unknowns and with rational integral coefficients, to indicate a general method whereby it is possible to determine in a finite number of steps whether it is soluble in rational integers”.
The theorem stating that no such method exists is one of the results expounded below. The technique developed to prove this theorem has made it possible to give a number of other interesting results connected with Diophantine equations.
The author has striven to provide an account that is accessible to mathematicians unfamiliar with mathematical logic and having only an elementary knowledge of number theory; a compendium of necessary results from number theory is given in the appendix.
This publication is cited in the following 16 articles:
F. M. Malyshev, “Vstraivanie dokazuemo nerazreshimykh zadach v shifry gammirovaniya”, Matem. vopr. kriptogr., 14:1 (2023), 65–83
Christian Dernehl, 2016 European Control Conference (ECC), 2016, 441
Yuri Matiyasevich, “Four color theorem from three points of view”, Illinois J. Math., 60:1 (2016)
Yuri Matiyasevich, Outstanding Contributions to Logic, 10, Martin Davis on Computability, Computational Logic, and Mathematical Foundations, 2016, 35
V. O. Osipyan, A. V. Mirzayan, Yu. A. Karpenko, A. S. Zhuk, A. Kh. Arutyunyan, “Matematicheskaya model sistemy zaschity informatsii na osnove diofantova mnozhestva”, Chebyshevskii sb., 15:1 (2014), 146–154
Yuri Matiyasevich, “Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets”, Mathematics and Computers in Simulation, 67:1-2 (2004), 125
M. Hazewinkel, Encyclopaedia of Mathematics, 1997, 1
A. G. El'kin, M. G. M. van Doorn, A. K. Gushchin, L. D. Kudryavtsev, V. V. Rumyantsev, V. I. Sobolev, B. A. Efimov, N. Kh. Rozov, V. T. Bazylev, I. A. Kvasnikov, B. I. Golubov, A. A. Konyushkov, L. N. Eshukov, P. P. Korovkin, A. V. Efimov, A. A. Zakharov, S. M. Vorazhin, Yu. N. Subbotin, A. L. Onishchik, D. P. Kostomarov, N. M. Nagornyǐ, V. E. Plisko, N. M. Khalfina, S. A. Stepanov, M. S. Nikulin, S. I. Adyan, P. S. Soltan, A. V. Zabrodin, L. A. Bokut', S. Yu. Maslov, G. E. Mints, E. M. Chirka, M. V. Fedoryuk, N. K. Nikol'skiǐ, B. S. Pavlov, A. L. Shmel'kin, A. V. Arkhangel'skiǐ, A. B. Bakushinskiǐ, D. A. Ponomarev, I. V. Dolgachev, A. A. Boyarkin, A. V. Mikhalev, M. I. Voǐtsekhovskiǐ, A. V. Prokhorov, L. E. Reǐzin', A. M. Il'in, G. N. Dyubin, D. P. Zhelobenko, V. P. Chistyakov, A. V. Khokhlov, V. A. Dushskiǐ, M. Sh. Farber, E. D. Solomentsev, V. D. Kukin, A. A. Mal'tsev, M. A. Shtan'ko, T. P., Encyclopaedia of Mathematics, 1995, 79
I. A. Vinogradova, A. G. El'kin, Yu. V. Prokhorov, B. A. Efimov, L. P. Kuptsov, N. Kh. Rozov, V. A. Oskolkov, L. D. Kudryavtsev, B. V. Khvedelidze, A. A. Zakharov, M. Sh. Tsalenko, E. D. Solomentsev, Yu. L. Ershov, I. V. Dolgachev, B. B. Venkov, A. N. Parshin, A. I. Kostrikin, A. B. Ivanov, A. P. Terekhin, V. F. Emelyanov, V. V. Sazonov, M. I. Voǐtsekhovskiǐ, I. I. Volkov, P. S. Aleksandrov, A. V. Prokhorov, A. M. Zubkov, V. N. Grishin, A. A. Danilevich, N. M. Nagornyǐ, E. G. D'yakonov, Kh. D. Ikramov, N. S. Bakhvalov, A. V. Arkhangel'skiǐ, V. V. Rumyantsev, A. V. Zarelua, A. A. Mal'tsev, O. A. Ivanova, V. P. Fedotov, I. P. Kubilyus, B. M. Bredikhin, P. L. Dobrushin, V. V. Prelov, A. V. Mikhalev, V. A. Andrunakievich, V. V. Fedorchuk, V. P. Platonov, A. P. Favorskiǐ, D. V. Anosov, V. I. Danilov, E. L. Tonkov, A. L. Onishchik, T. S. Pigolkina, T. S. Pogolkina, L. A. Skornyakov, V. I. Sobolev, I. Kh. Sabitov, V. I. Lebedev, A. V. Lykov, A., Encyclopaedia of Mathematics, 1995, 1
M. Hazewinkel, Encyclopaedia of Mathematics, 1994, 2
M. Hazewinkel, Encyclopaedia of Mathematics, 1989, 1
M. Hazewinkel, Encyclopaedia of Mathematics, 1988, 1
Yu. Matijasevich, Lecture Notes in Computer Science, 278, Fundamentals of Computation Theory, 1987, 301
N. N. Repin, “The solvability problem for equations in one unknown in nilpotent groups”, Math. USSR-Izv., 25:3 (1985), 601–618
A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125
A. I. Kokorin, A. G. Pinus, “Decidability problems of extended theories”, Russian Math. Surveys, 33:2 (1978), 53–96
Citation in format AMSBIB
Contact us: