Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Язык диофантовых предикатов

В продолжение темы про характеризацию вычислимости через диофантовы уравнения, мне бы хотелось рассказать об одном интересном формальном языке. Идею этого языка наверняка возникала у множества разных людей, очень уж он естественнен становится, если знать о теореме Робинсон-Дэвиса-Путнама-Матиясевича, однако название впервые встречается в замечательной статье Hilbert's Tenth Problem is Unsolvable (Martin Davis, 1973). Кстати, эта статья это первое официальное и притом отлично написанное изложения RDPM-теоремы, там всё дельно объясняется, даются конкретные примеры, как выражаются диофантовыми уравнениями числа Фибоначчи, экспоненциальная функция, любые примитивно-рекурсивные и любые μ-рекурсивные функции.

Язык этот не содержит логических символов, символа равенства и кванторов: высказывания это просто многочлены P(x, a, b, c, ..) от произвольного числа переменных и выделенной переменной x, интерпретируемые как ∀x.∃a, b,..,c. P(x, a, b,.., c) = 0, где переменные принимают целые положительные значения, а квантор всеобщности понимается в слабом смысле “верность выражения сохраняется при наложении на x дополнительных ограничений диофентовыми уравнениями”.

Это очень сильный язык:
– любое перечислимое множество, любая вычислимая функция, любое вычислимое соотношение можно закодировать диофантовым уравнением;
– можно написать такой P, что P(x, a, b,.., c) тогда и только тогда, когда программа закодированная числом x завершается;
– то, что программа, выполняющая, скажем, cut-elimination, завершается для любого поданного на вход доказательства x в теории T эквивалентно высказыванию “T непротиворечива”.

Теперь детали. Обычно под многочленом над целмыми числами понимается выражение, составленное из констант и переменных операциями умножения, сложения и вычитания. Вычитание в целочисленных многочленах используется ограниченное снизу, т.е. a ∸ b := max(a - b, 0). Сейчас я покажу, что сложение не нужно вовсе (его можно определить через вычетание), а умножение можно заменить делением. Кроме минималистичности этот подход имеет тот плюс, что он увеличивает диапазон возможных на базе языка теорий. Дело в том, что если язык явно содержит умножение, то любая теория с этим языком (снабжающая символ умножения обычным смыслом) обладает силой ω2. Явное включение сложения гарантирует силу ω. Использование только операций, неувеличивающих операнды, без дополнительных аксиом никаких ограничений на силу теории не накладывает. Таким образом, снабжая такой язык более или менее сильными аксиомами мы сможем получить широчайший диапазон теорий.

Итак, наш язык будет состоять из следующего:
– Констант 0 и 1
- Выделенной переменой x и неограниченного алфавита других переменных
– Бинарных операторов ∸ и ÷.
Сегмент языка без оператора ÷ будем называть аддитивным.

Как работает ∸ я уже объяснил выше, а x÷y равно отношению x и y, если y ненулевой и x делится на него нацело, а во всех остальных случаях равно 0.

Теперь добавим обозначения:
– ¬A := 1 ∸ A
– A ∩ B := 1 ∸ ((1 ∸ B) ∸ A)
– A = B := (A ∸ B) ∩ (B ∸ A)

Если рассматривать термы A и B как множества решений уравнений A = 0 и B = 0 при фиксированном x, то ¬A строит дополнение ко множеству решений, а A ∩ B пересекает множества решений. Через “не” и “и” можно определить все другие булевы операции над множествами решений. Терм A = B имеет интуитивную интерпретацию — это множество решений уравнения A = B.

Теперь покажем, каким образом уравнения, содержащие термы A + B и A · B, исключённые из нашего языка, записать на нашем языке:
– Каждый терм A + B следует заменить на неиспользовавшуюся прежде в выражении переменную q, а в конце ко всему выражению добавить ∩ (q ∸ A ∸ B) ∩ (A ∸ B ∸ q) ∩ (B ∸ A ∸ q).
– Каждый терм A · B следует заменить на неиспользовавшуюся прежде в выражении переменную q, а в конце ко всему выражению добавить ∩ (((q + A) / A = (B + 1)) ∪ ((q + B) / B = (A + 1)))
– Аналогичным образом, при помощи методик кодирования описанных в вышеприведённой статье можно “вставлять” в любое место уравнения любую вычислимую функцию f(A, B,.., C) от любого количества любых других термов.

Мне этот язык кажется крайне перспективным в качестве прогрессивной замены примитивно-рекурсивной арифметике PRA, недостатком которой является излишняя для финитизма сила.

Задачи:
1) Сформулировать естественный набор правил вывода и аксиом, реализующих эквивалентность аддитивного сегмента П2-сегменту арифметики Пресбургера.
2) Сформулировать естественный набор правил вывода и аксиом, дающий самоверифицирующуюся систему силы ω, совпадающую с арифметикой Пеано на Δ1-высказываниях, т.е. нечто вроде IS(A) Уилларда.
3) Сформулировать естественный и минималистичный набор правил вывода и аксиом, делающий язык эквивалентным по силе PRA или IΣ1 (они эквивалентны на уровне П2 высказываний, а наш язык только такие и содержит).
4) Сформулировать естественный и минималистичный набор правил вывода и аксиом, делающий язык эквивалентным арифметике Пеано.
5) В идеале сформулировать их так, чтобы каждая последующая ступень была просто дополнением предыдущей. как в аксиоматизации логик из предыдущего поста.


Касательно задачи 3 я нашёл набор аксиом и правил вывода, таких что любое доказуемое в PRA высказывание, доказуемо и тут. Однако я совсем не уверен, что мой набор аксиом и правил вывода минимален, да и вообще как-то он кривоват; надо допиливать. Ну и потом надо показать, что над ним консервативна IΣ1 (арифметика Пеано с ослабленной до Σ1-высказываний индукцией). Видимо, решение 4 задачи получится, если допустить полноценную П2-индукцию. Задача 1 должна решаться просто, но я ещё не подступался. Ну и наконец задача 2 особенно сложна. Прямолинейное решение наверное можно получить методично реализовав IS(A), но особенно красивым набор аксиом не будет.
Subscribe

  • (no subject)

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

  • Прогресс

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

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

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

  • 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.
  • 2 comments