Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

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

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

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

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

Recent Posts from This Journal

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments

Recent Posts from This Journal

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)