Diophantine set

In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n₁, ..., n_j, x₁, ..., x_k) such that an tuple (n₁, ..., n_j) of integers is in S if and only if there exist some integers x₁, ..., x_k with f(n₁, ..., n_j, x₁, ..., x_k) = 0. (Such a polynomial equation over the integers is also called a Diophantine equation.) In other words, a Diophantine set is a set of the form

<math>\{\, (n_1,\dots,n_j) : \exists x_1\,\dots\,\exists x_k\, f(n_1,\dots,n_j,x_1,\dots,x_k )=0 \,\}<math>

where f is a polynomial function with integer coefficients.

Matiyasevich's theorem, published in 1970, states that a set of integers is Diophantine if and only if it is recursively enumerable. The phrase recursively enumerable is not very suggestive; semi-decidable conveys the intuition far better. A set S of integers (or tuples of integers) is recursively enumerable (or semi-decidable) precisely if one can write a computer program that, when given an integer (or tuple) n, eventually halts if n is a member of S, and runs forever otherwise. Matiyasevich's theorem effectively settled Hilbert's tenth problem.