И если вот этим путём (на который я, конечно, пока только намекнул) пройти — то получается
Теорема (Davis, Putnam, Robinson, 1961; https://doi.org/10.2307/1970289 )
Любое перечислимое множество экспоненциально-диофантово.

Но что делать с экспонентой? Как выразить хоть что-то экспоненциальное, если у нас в руках только многочлены? Ну хоть что-нибудь экспоненциально растущее — скажем, уже было известно, что если есть какое-то отношение, которое растёт быстрее, чем u^k при любом k, но медленнее, чем u^u, то этого уже хватает. Но как это вытащить из полиномов? И полноте, возможно ли это? [Это сейчас мы знаем, что да — а вот обзор в Mathematical Reviews на их работу в этом смысле не горит энтузиазмом...]

И — последний удар!

Теорема (Ю.В. Матиясевич, 1970; см. http://mi.mathnet.ru/dan35274 )
Отношение "v — 2u-е число Фибоначчи" диофантово.