Geodesic
A new proof of the theorem on exponential diophantine representation of enumerable sets
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VII, Tome 60 (1976), pp. 75-92

Voir la notice de l'article provenant de la source Math-Net.Ru

A new proof is given for the well-known theorem of Putnam, Davis, and Robinson on exponential diophantine representation of recursively enumerable sets. Starting from the usual definition of r.e. sets via Turing machines, a new method of arithmetization is given. This new method leads directly to a purely existential exponential formula. The new proof may be more suitable for a course on the theory of algorithms because it requires less knowledge of number theory. 
@article{ZNSL_1976_60_a7,
     author = {Yu. V. Matiyasevich},
     title = {A new proof of the theorem on exponential diophantine representation of enumerable sets},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {75--92},
     publisher = {mathdoc},
     volume = {60},
     year = {1976},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a7/}
}
TY  - JOUR
AU  - Yu. V. Matiyasevich
TI  - A new proof of the theorem on exponential diophantine representation of enumerable sets
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1976
SP  - 75
EP  - 92
VL  - 60
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a7/
LA  - ru
ID  - ZNSL_1976_60_a7
ER  - 
%0 Journal Article
%A Yu. V. Matiyasevich
%T A new proof of the theorem on exponential diophantine representation of enumerable sets
%J Zapiski Nauchnykh Seminarov POMI
%D 1976
%P 75-92
%V 60
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a7/
%G ru
%F ZNSL_1976_60_a7
Yu. V. Matiyasevich. A new proof of the theorem on exponential diophantine representation of enumerable sets. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VII, Tome 60 (1976), pp. 75-92. http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a7/