Matiyasevich's Theorem states that every recursively enumerable set of natural numbers can be defined as the set of nonnegative values taken by some polynomial with integer coefficients, which together with earlier work by Julia Robinson, Martin Davis and Hilary Putnam establishes that no algorithm can decide, in general, whether a given Diophantine equation has an integer solution. Named for Yuri Matiyasevich, it resolves Hilbert's tenth problem in the negative and is a foundational result linking number theory to computability theory.
Facts
StatementEvery computably enumerable set is Diophantine, and the converse. 1 Sources
1. Matiyasevich's theorem, Wikipedia
Lead section
Every computably enumerable set is Diophantine, and the converse.
History section
The theorem was established in 1970 by Matiyasevich and is thus also known as Matiyasevich's theorem.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.