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 integer (n₁,...n_j) is in S if and only if there exist some integers x₁,...,x_k with f(n,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

Matiyasevich's theorem states that a set of integers is Diophantine if and only if it is recursively enumerable. The phrase recursively enumerable is not very suggestive. A set S of integers (or tuples of integers) is recursively enumerable 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.