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 Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
Principal Result Of
Source Julia Robinson (Wikipedia)
Sources
1. Matiyasevich's theorem, Wikipedia
Lead section
Every computably enumerable set is Diophantine, and the converse.
References
The theorem was established in 1970 by Matiyasevich and is thus also known as Matiyasevich's theorem.
View the SourceDiophantine set (Wikipedia)
In Group: Computability and Complexity Theory, Lead or opening sectionQuote, In Group: Computability and Complexity Theory, Lead or opening section
states that a set of integers is Diophantine if and only if it is computably enumerable
Julia Robinson (Wikipedia)
Principal Result Of: Julia Robinson, LeadQuote, Principal Result Of: Julia Robinson, Lead
Her work on Hilbert's tenth problem (now known as Matiyasevich's theorem or the MRDP theorem) played a crucial role in its ultimate resolution.
Reader 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.