RUS  ENG
Full version
JOURNALS // Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya // Archive

Izv. Akad. Nauk SSSR Ser. Mat., 1971 Volume 35, Issue 1, Pages 3–30 (Mi im1910)

This article is cited in 23 papers

Diophantine representation of enumerable predicates

Yu. V. Matiyasevich


Abstract: An example is given of a diophantine relation which has exponential growth. This, together with the well-known results of Martin Davis, Hilary Putnam, and Julia Robinson, yields a proof that every enumerable predicate is Diophantine. This theorem implies that Hilbert's tenth problem is algorithmically unsolvable.

UDC: 511

MSC: 02E10, 10B99, 10N05

Received: 17.09.1970


 English version:
Mathematics of the USSR-Izvestiya, 1971, 5:1, 1–28

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024