ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# 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.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.