Я пытаюсь учить себя Коку путем формализации формализовать математическая теорема, с которой я знаком: неразрешимость проблемы остановки различные теоремы теории вычислимости.
Поскольку я не заинтересован в оформлении деталей вычислительных моделей (например, машин Тьюринга, регистрационных машин, лямбда-исчислений и т.д.), Я пытаюсь это сделать "преподавание тезиса Кок-Церкви-Тьюринга", а именно, предполагая, что Axiom утверждает свойства функций, которые Coq считает вычислимыми (т.е. определяемые функции типа nat → nat).
Например, если бы я хотел сказать Coq, что есть эффективное перечисление частичных вычислимых функций, я мог бы сказать
Definition partial := nat -> nat -> option nat.
Axiom Phi : nat -> partial.
Здесь частичные вычислимые функции мыслятся как (всего) вычислимых функций, что, учитывая первый аргумент s, имитирующего вычисление исходных частичных вычислимых функций для s многих шагов. Я мог бы также добавить другие Axiom s, такие как лепка простуды, и я мог бы доказать неразрешимость проблемы остановки и некоторые другие теоремы теории вычислимости.
Мои первые вопросы касаются того, действительно ли я на правильном пути. Не так ли, что то, что я пытаюсь сделать, очевидно невозможно для феноменов неполноты или характера системы типов Coq?
Мой второй вопрос касается релятивизации. Если бы я попытался доказать более серьезные вещи в теории вычислимости, я бы хотел рассмотреть вычисления в оракулах. Поскольку часто оракулы строятся как пределы частичных двузначных функций, кажется (по крайней мере наивно) естественным сделать оракулы с типом nat → bool. В то же время для того, чтобы оракулы были нетривиальными, они должны быть не вычислимыми. Учитывая это, имеет смысл оракул с типом nat → bool?
Вот еще вопрос о оракулах: было бы очень приятно, если бы для каждого оракула существовал тип частичных вычислимых функций относительно этого конкретного оракула. Могу ли я сделать это, используя систему зависимых типов в Coq? Оказывается ли эта возможность на выбор некоторых формалистических оракулов, как обсуждалось в параграфе выше?
EDIT: подход выше, безусловно, не работает, как есть, так как мне нужна дополнительная аксиома:
Axiom Phi_inverse: partial -> nat.
что не должно быть правдой для оракулов. Существует ли такой подход, как описанный выше (я имею в виду, тот, который не включает формализацию вычислительных моделей)?
EDIT: Чтобы уточнить мое намерение, я отредактировал выражение о проблеме выше. Кроме того, чтобы представить стиль формализации, который я имел в виду, я представляю неполное доказательство неразрешимости проблемы остановки здесь:
Require Import Arith.
Require Import Classical.
Definition ext_eq (A B : Set) (f g : A -> B) := forall (x : A), f x = g x.
Definition partial := nat -> nat -> option nat.
Axiom Phi : nat -> partial.
Axiom Phi_inverse : partial -> nat.
Axiom effective_enumeration :
forall (f : partial) (e : nat),
Phi e = f <-> Phi_inverse f = e.
Axiom modulus : partial -> nat -> nat.
Axiom persistence :
forall (f : partial) n s,
s >= modulus f n -> f s n = f (modulus f n) n.
Definition limit (f : partial) n := f (modulus f n) n.
Definition total (f : partial)
:= forall n, exists s, exists m, f s n = Some m.
Definition flip n := match n with O => 1 | S _ => 0 end.
Definition K e := exists n, limit (Phi e) e = Some n.
Theorem K_is_undecidable :
~ exists e,
total (Phi e)
/\ forall e', limit (Phi e) e' = Some 0 <-> ~K e'.
Proof.
intro.
destruct H as [e].
destruct H.
pose proof (H0 (Phi_inverse (fun s e' =>
match (Phi e s e') with
| Some n => Some (flip n)
| None => None end))).
(* to be continued *)
