{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T11:54:54Z","timestamp":1774007694970,"version":"3.50.1"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":11515,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1982,9]]},"abstract":"<jats:p>In 1961 Martin Davis, Hilary Putnam and Julia Robinson [2] proved that every recursively enumerable set <jats:italic>W<\/jats:italic> is exponential diophantine, i.e. can be represented in the form<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200043954_eqnU01\"\/><\/jats:disp-formula><\/jats:p><jats:p>Here <jats:italic>P<\/jats:italic> is a polynomial with integer coefficients and the variables range over positive integers.<\/jats:p><jats:p>In 1970 Ju. V. Matijasevi\u010d used this result to establish the unsolvability of Hilbert's tenth problem. Matijasevi\u010d proved [11] that the exponential relation <jats:italic>y<\/jats:italic> = 2<jats:sup><jats:italic>x<\/jats:italic><\/jats:sup> is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set <jats:italic>W<\/jats:italic>can be represented in the form<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200043954_eqnU02\"\/><\/jats:disp-formula><\/jats:p><jats:p>From this it follows that there does not exist an algorithm to decide solvability of diophantine equations. The nonexistence of such an algorithm follows immediately from the existence of r.e. nonrecursive sets.<\/jats:p><jats:p>Now it is well known that the recursively enumerable sets <jats:italic>W<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>W<\/jats:italic><jats:sub>2<\/jats:sub>, <jats:italic>W<\/jats:italic><jats:sub>3<\/jats:sub>, \u2026 can be enumerated in such a way that the binary relation <jats:italic>x<\/jats:italic> \u2208 <jats:italic>W<jats:sub>v<\/jats:sub><\/jats:italic> is also recursively enumerable. Thus Matijasevi\u010d's theorem implies the existence of a diophantine equation <jats:italic>U<\/jats:italic> such that for all <jats:italic>x<\/jats:italic> and <jats:italic>v<\/jats:italic>,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200043954_eqnU03\"\/><\/jats:disp-formula><\/jats:p>","DOI":"10.2307\/2273588","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:00:58Z","timestamp":1146952858000},"page":"549-571","source":"Crossref","is-referenced-by-count":67,"title":["Universal diophantine equation"],"prefix":"10.1017","volume":"47","author":[{"given":"James P.","family":"Jones","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200043954_ref011","first-page":"279","article-title":"Enumerable sets are diophantine","volume":"191","author":"Matijasevi\u010d","year":"1970","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200043954_ref006","volume-title":"Les Annales des Sciences Math\u00e9matiques du Qu\u00e9bec","author":"Jones"},{"key":"S0022481200043954_ref002","doi-asserted-by":"publisher","DOI":"10.2307\/1970289"},{"key":"S0022481200043954_ref010","first-page":"49","article-title":"Ondiophantine representation of the sequence of solutions of Pell's equation","volume":"20","author":"Kosovski\u01d0","year":"1971","journal-title":"Zapiski Nau\u010dnyh Seminarov Leningradskogo Otdelenija Matemati\u010deskogo Instituta im. V.A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200043954_ref007","first-page":"335","volume":"43","author":"Jones","year":"1978","journal-title":"Three universal representations of recursively enumerable sets"},{"key":"S0022481200043954_ref023","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1852.44.93"},{"key":"S0022481200043954_ref001","first-page":"173","volume-title":"Philosophical Transactions of the Royal Society of London, Series A","volume":"263","author":"Baker","year":"1968"},{"key":"S0022481200043954_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-1138-9_7"},{"key":"S0022481200043954_ref004","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1973.11993265"},{"key":"S0022481200043954_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1980-14832-6"},{"key":"S0022481200043954_ref003","first-page":"323","volume-title":"Proceedings of the Symposium on the Hilbert Problems (De Kalb, Illinois), May 1974","author":"Davis","year":"1976"},{"key":"S0022481200043954_ref015","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-521-553"},{"key":"S0022481200043954_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70352-0"},{"key":"S0022481200043954_ref013","first-page":"185","article-title":"Diophantine sets","volume":"27","author":"Matijasevi\u010d","year":"1972","journal-title":"Uspehi Matemati\u010deskih Nauk"},{"key":"S0022481200043954_ref022","first-page":"21","volume-title":"Nachrichten der Akademie der Wissenschaften in G\u00f6ttingen. II. Mathematisch-Physikalische Klasse","author":"Siegel","year":"1972"},{"key":"S0022481200043954_ref014","first-page":"77","article-title":"Arithmetical representation of enumerable sets with a small number of quantifiers","volume":"32","author":"Matijasevi\u010d","year":"1972","journal-title":"Zapiski Nau\u010dnyh Seminarov Leningradskogo Otdelenija Mathematiceskogo Instituto im. V.A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200043954_ref016","first-page":"75","article-title":"A new proof of the theorem on exponential diophantine representation of enumerable sets","volume":"60","author":"Matijasevi\u010d","year":"1976","journal-title":"Zapiski Nau\u010dnyh Seminarov Leningradskogo Otdelenija Mathemati\u010deskogo Instituto im. V.A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200043954_ref020","first-page":"69","volume-title":"Studies in the theory of algorithms and mathematical logic","author":"Matijasevi\u010d","year":"1979"},{"key":"S0022481200043954_ref017","first-page":"167","article-title":"A class of primality criteria formulated in terms of the divisibility of binomial coefficients","volume":"67","author":"Matijasevi\u010d","year":"1977","journal-title":"Zapiski Nau\u010dhnyh Seminarov Leningradskogo Otdelenija Mathemati\u010deskogo Instituta im. V.A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200043954_ref018","first-page":"62","article-title":"Primes are non-negative values of polynomial in 10 variables","volume":"68","author":"Matijasevi\u010d","year":"1977","journal-title":"Zapiski Nau\u010dnyh Seminarov Leningradskogo Otdelenija Mathemati\u010deskogo Instituto im. V.A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200043954_ref008","doi-asserted-by":"publisher","DOI":"10.4064\/aa-35-3-209-221"},{"key":"S0022481200043954_ref021","first-page":"191","volume-title":"Proceedings of the Symposium on Pure Mathematics","volume":"20","author":"Robinson","year":"1971"},{"key":"S0022481200043954_ref025","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1952-0048374-2"},{"key":"S0022481200043954_ref026","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-8.3.555"},{"key":"S0022481200043954_ref009","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1976.11994142"},{"key":"S0022481200043954_ref024","article-title":"Diophantine decision problems","volume":"6","author":"Robinson","year":"1969","journal-title":"MAA Studies in Mathematics"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200043954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T20:47:24Z","timestamp":1558730844000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200043954\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,9]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,9]]}},"alternative-id":["S0022481200043954"],"URL":"https:\/\/doi.org\/10.2307\/2273588","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,9]]}}}