Теорема, получающаяся из объединения работ Мартина Дэвиса, Юрия Владимировича Матиясевича, Хилари Патнема и Джулии Робинсон, утверждает, что перечислимость — единственное(!) необходимое условие:

Теорема [M. Davis, Ю. В. Матиясевич, H. Putnam, J. Robinson]
Любое перечислимое множество диофантово. Более того, порождающий его многочлен P может быть построен по алгоритму перечисления алгоритмическим образом.