×

A new technique for obtaining diophantine representations via elimination of bounded universal quantifiers. (English. Russian original) Zbl 0940.03052

J. Math. Sci., New York 87, No. 1, 3228-3233 (1997); translation from Zap. Nauchn. Semin. POMI 220, 83-92 (1995).
Author’s summary: “M. Davis proved in J. Symb. Log. 18, 33-41 (1953; Zbl 0051.24509) that every recursively enumerable set has an arithmetic representation with a unique bounded universal quantifier, known today as the Davis normal form. M. Davis, H. Putnam and J. Robinson showed in Ann. Math., II. Ser. 74, 425-436 (1961; Zbl 0111.01003) how the Davis normal form can be transformed into a purely existential exponential diophantine representation which uses not only addition and multiplication, but also exponentiation. The present author eliminated the exponentiation in Dokl. Akad. Nauk SSSR 191, 279-282 (1970; Zbl 0212.33401) and thus obtained the unsolvability of Hilbert’s tenth problem. The paper presents a new method for transforming the Davis normal form into the exponential diophantine representation”.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
11U05 Decidability (number-theoretic aspects)
12L05 Decidability and field theory
03C10 Quantifier elimination, model completeness, and related topics
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] M. Davis, ”Arthmetical problems and recursively enumerable predicates,”J. Symbolic Logic,18, 33–41 (1953). · Zbl 0051.24509 · doi:10.2307/2266325
[2] M. Davis, Yu. Matiyasevich (Matijasevič), and J. Robinson, ”Hilbert’s tenth problem Diophantine equations: positive aspects of a negative solution”,Proc. Symp. Pure Math.,28, 323–378 (1976).
[3] M. Davis, H. Putnam, and J. Robinson, ”The decision problem for exponential Diophantine equations,”Ann. Math., Second Series,74, 425–436 (1961). · Zbl 0111.01003 · doi:10.2307/1970289
[4] K. Hirose and I. Shigeaki, ”A proof of negative answer to Hilbert’s 10th Problem,”Proc. Jpn. Acad.,49, 10–12 (1973). · Zbl 0279.02028 · doi:10.3792/pja/1195519486
[5] E. E. Kummer, ”Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen,”J. Reine Angew. Math.,44, 93–146 (1852). · ERAM 044.1198cj · doi:10.1515/crll.1852.44.93
[6] E. E. Kummer,Collected Papers, Vol. 1, A. Weil, ed., Springer-Verlag, Berlin (1975). · Zbl 0327.01019
[7] Yu. V. Matiyasevich, ”Enumerable sets are Diophantine,”Dokl. Akad. Nauk SSSR,191, 278–282 (1970). · Zbl 0212.33401
[8] Yu. V. Matiyasevich, ”Diophantine sets,”Usp. Mat. Nauk,27, No. 5 (167), 185–222 (1972). · Zbl 0269.02019
[9] Yu. V. Matiyasevich,Hilbert’s Tenth Problem [in Russian], Nauka, Moscow (1993). · Zbl 0790.03009
[10] Yu. V. Matiyasevich, ”A direct method for simulating partial recursive functions by Diophantine equations,”Ann. Pure Appl. Logic,67, 325–348 (1994). · Zbl 0795.03054 · doi:10.1016/0168-0072(94)90014-0
[11] J. Robinson, ”Existential definability in arithmetic,”Trans. Am. Math. Soc.,72, 437–449 (1952). · Zbl 0047.24802 · doi:10.1090/S0002-9947-1952-0048374-2
[12] D. Singmaster, ”Notes on binomial coefficients”,J. London Math. Soc. (2),8, 545–548 (1974). · Zbl 0293.05005 · doi:10.1112/jlms/s2-8.3.545
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.