Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T11:53:26.343Z Has data issue: false hasContentIssue false

Universal diophantine equation

Published online by Cambridge University Press:  12 March 2014

James P. Jones*
Affiliation:
Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta, Canada, T2N 1N4

Extract

In 1961 Martin Davis, Hilary Putnam and Julia Robinson [2] proved that every recursively enumerable set W is exponential diophantine, i.e. can be represented in the form

Here P is a polynomial with integer coefficients and the variables range over positive integers.

In 1970 Ju. V. Matijasevič used this result to establish the unsolvability of Hilbert's tenth problem. Matijasevič proved [11] that the exponential relation y = 2x is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set Wcan be represented in the form

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.

Now it is well known that the recursively enumerable sets W1, W2, W3, … can be enumerated in such a way that the binary relation x ∈ Wv is also recursively enumerable. Thus Matijasevič's theorem implies the existence of a diophantine equation U such that for all x and v,

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1982

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable