Diophantine set
In
mathematics, a
set S of
j-tuples of
integers is
Diophantine precisely if there is some
polynomial with integer coefficients
f(
n1,...,
nj,
x1,...,
xk) such that an integer (
n1,...
nj) is in
S if and only if there exist some integers
x1,...,
xk with
f(
n,
x1,...,
xk)=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.