Алгебраическая характеризация вычислимости

Многие знают, что существует много эквивалентных определений алгоритма: можно определять через лямбда-исчисления, можно через машины Тьюринга, можно через term-rewritting systems, можно через мю-рекурсивные функции. Не все однако знают, что есть и чисто алгебраическая характеризация алгоритма: через диофантовы уравнения (полиномиальные уравнения в целых числах). Для любого алгоритма, возвращающего набор чисел, можно построить диофантово уравнение, проекция решения которого на одну из осей состоит в точности из этих чисел. Доказывается более чем конструктивно: совершенно прямолинейно строится интерпретация Тьюринг-полного языка программирования в огромное диофантово уравнение.

К слову, это достаточно диофантовых уравнений четвёртой степени с не более чем N переменными: для любого диофантового уравнения любой степени можно сконструировать диофантово уравнение четвёртой, имеющее то же множество решений. Естественно, не для любого диофантового уравнения, а для любого уравнения в целых числах, содержащее вычислимые функции — хоть возведение в степень, хоть функцию Аккермана. В это сложно поверить, но это так: любую программу можно закодировать, как пересечение N-мерной поверхности четвёртого порядка, и решётки точек с целыми координатами.
(Точное значение N сейчас неизвестно: известно, что больше трёх и меньше 4^11, что ли.)

Кстати, с диофантовыми уравнениями второго порядка всё совсем наоборот: их множества решений структурно очень простые и существует эффективный алгоритм, позволяющий найти множество решений такого уравнения. Как обстоит дело с третьим порядком — открытый вопрос. Может быть они разрешимы, а может быть наоборот универсальны. Ещё известно, что диофантовы уравнения любой степени с одной переменной разрешимы и вероятно с двумя переменными тоже, а как обстоит дело с уравнениями с количеством переменных больше 2 и меньше N совершенно неизвестно.