1982/09/01 by James P. Jones · 1 citation
Computer Science · Mathematics · #Artificial Intelligence in Games #Logic, programming, and type systems #Polynomial and algebraic computation #Diophantine equation #Recursively enumerable language #Recursively enumerable set #Diophantine set #Maximal set #Mathematics #Integer (computer science) #Discrete mathematics #Exponential function #Relation (database) #Combinatorics #Set (abstract data type) #Mathematical analysis #Computer science
paper · doi:10.2307/2273588
openalex publication_date 1982/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
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 = 2 x is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set W can 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 W 1 , W 2 , W 3 , … can be enumerated in such a way that the binary relation x ∈ W v is also recursively enumerable. Thus Matijasevič's theorem implies the existence of a diophantine equation U such that for all x and v ,