Возвращаясь к диофантовости всех перечислимых множеств — собственно говоря, идея "сертификата" работает и тут.

А именно — представим себе, что какая-то машина долго-долго работала и наконец закончила работу. Давайте соберём все состояния её "регистров" во все моменты времени в один "протокол" ("в момент времени t=1 состояние такое-то; в момент t=2 состояние такое-то; ..."). Так вот — машина заканчивает работу за конечное время тогда и только тогда, когда существует конечный "протокол", в котором в начальный момент времени стоит её начальное состояние, корректно выполнен переход от каждого момента к следующему, и конечное состояние соответствует команде "стоп". Этот "протокол" мы и захотим добавить в дополнительные переменные.
Правда, мы не знаем, сколько машина будет работать — но не страшно, просто пусть у нас будет система счисления с большим-большим основанием N, а последовательные состояния машины — последовательными "цифрами" в записи одной из переменных в этой системе счисления. Собственно, мы уже применили почти этот подход к выражению биномиальных коэффициентов — только тогда мы "доставали" из большого числа (N+1)^M одну его цифру, а тут придётся научиться работать со всеми цифрами одновременно, каким-то образом одновременно обеспечивая, что переход от каждого момента времени t к следующему t+1 корректен.
В качестве одного из шагов возникает теорема Куммера о делимости биномиальных коэффициентов на простые:

И если вот этим путём (на который я, конечно, пока только намекнул) пройти — то получается
Теорема (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-е число Фибоначчи" диофантово.

Два кусочка из статьи Матиясевича:

И собственно явное задание —

Собственно, эта статья замечательна тем, что её можно спокойно разобрать сильному школьнику.

Вот основные идеи:
а) Соотношение x^2-xy-y^2=1 на неотрицательные x и y равносильно тому, что x и y это два последовательных числа Фибоначчи, x=F_{2m+1}, y=F_{2m}. А если бы в правой части было (-1), то было бы x=F_{2m}, y=F_{2m-1}.
Утверждение само по себе симпатичное — и мгновенно доказывающееся по индукции (достаточно написать, что x=y+z).
И тут можно посмотреть на равенства (2) и (3) из кусочка выше — гарантирующие, что l, z, g и h это числа Фибоначчи.

(соответствующая пара лемм)

б) Делимость чисел Фибоначчи. Во-первых, F_m делится на F_n тогда и только тогда, когда m делится на n. Что несложно увидеть, приведя числа Фибоначчи по модулю F_n: будет
номер — 0, 1, 2, ..., n-1, n, n+1,...
число — 0, 1, 1, ..., * , 0, * , ...,
и после n будет то же, что и после нуля, только умноженное на F_{n-1} (взаимно простое с F_n).
Но вот — и это ключевой шаг — если F_m делится не просто на F_n, а на F_n^2, то вот это равносильно тому, что номер m делится на nF_n.

И вот здесь начинает возникать экспоненциальный сдвиг: возникает связь между номерами и соответствующими числами Фибоначчи — а это как раз экспонента с основанием в золотое сечение.
И тут можно посмотреть на условие (4) из теоремы — как раз гарантирующее, что номер числа g делится на само число l.

в) И третья идея — нужно как-то суметь связать число Фибоначчи v с его номером 2u, причём в виде именно равенства. Для этого — для ещё одного, очень большого, числа m запускается ещё одна рекуррентная последовательность:
ψ_0=0, ψ_1=1, ψ_{k+1}= m ψ_k - ψ_{k-1}.
Точно так же, как для чисел Фибоначчи, свойство чисел (x,y) быть последовательной парой чисел оттуда проверяется полиномиально: необходимо и достаточно, чтобы
x^2 - m*xy + y^2 =1.
(Без условия целочисленности получилась бы гипербола — так что это описание того, как выглядят целочисленные точки на ней)

Так вот — давайте эту последовательность ψ_k приводить по какому-нибудь модулю, по которому m чему-нибудь хорошему равно. А именно: если m сравнимо с 2 по модулю N, то приведение по модулю N превращает соотношение на ψ_k в
ψ_{k+1}= 2 ψ_k - ψ_{k-1},
а это соотношение арифметической прогрессии. Поэтому тогда ψ_k сравнимо со своим номером k.

А если m сравнимо с 3 по модулю N, то соотношение превращается в
ψ_{k+1}= 3 ψ_k - ψ_{k-1},
а это как раз соотношение на числа Фибоначчи F_{2k} с чётными номерами! То есть ψ_k сравнимо с F_{2k} по модулю N.

И если попросить, чтобы сравнивалось одно и то же число x — то как раз получится связать его номер и соответствующее число Фибоначчи.

Условие (7) как раз говорит, что x — это одно из чисел последовательности ψ_k; условие (8) — что его номер k сравним с u; а условие (9) — что v сравнимо с F_{2k}. Так что если v=F_{2u}, то как раз можно взять x=ψ_{2u} — и остаётся достроить все остальные числа.

Остаётся аккуратно посмотреть, как из всех сравнимостей получается переход в другую сторону — но давайте я это замету под ковёр. И закончу рассказ добавлением пары ссылок:
*) вот тут — http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=3647 — видеозаписи курса Матиясевича в ЛШСМ-2011
*) а вот тут — статья в "Кванте" 1970 года (первый год, когда "Квант" начал выходить!) Ф. Варпаховского и А. Колмогорова (да-да!), озаглавленная "О решении десятой проблемы Гильберта" — заканчивающаяся как раз предъявлением (но без подробного разбора) этой системы:
https://kvant.ras.ru/1970/07/o_reshenii_desyatoj_problemy_g.htm

И один абзац из этой статьи —