Изменения
→Вклад Ю.В. Матиясевича
В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной
форме можно построить его диофантово представление:
* построить арифметическую формулу со многими ограниченными кванторами общности;
* преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности;
Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гильберта является неразрешимой.
