Формализация теории вычислимости в Coq

Я пытаюсь ~~учить себя Коку путем формализации~~ формализовать ~~математическая теорема, с которой я знаком: неразрешимость проблемы остановки~~ различные теоремы теории вычислимости.

Поскольку я не заинтересован в оформлении деталей вычислительных моделей (например, машин Тьюринга, регистрационных машин, лямбда-исчислений и т.д.), Я пытаюсь это сделать ~~"преподавание тезиса Кок-Церкви-Тьюринга", а именно,~~ предполагая, что 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 *)

Ответы

Ответ 1

Во-первых, некоторые разъяснения:

Функции, которые Coq считает вычислимыми (т.е. Определяемые функции типа nat → nat)

Строго говоря, Coq не считает, что функции вычислимы. Логика Coq утверждает, что определенные функции могут быть определены и что вы можете делать с ними определенные вещи, но произвольная функция - это черный ящик, насколько это касается Coq. В частности, согласуется постулировать существование не вычислимой функции.

Теперь, к актуальным вопросам. Здесь решение, которое более или менее следует Атсби, отвечает. Мы будем представлять функцию машины Тьюринга функцией Coq типа nat → nat → option bool. Идея состоит в том, что первым аргументом является ввод, а второй - максимальное количество шагов, за которые мы будем работать. Результатом является None если мы не можем дать ответ, а Some b если вычисление завершается с получением b в качестве ответа. Я воспользовался Ssreflect, чтобы сделать код немного проще:

Require Import Ssreflect.ssreflect Ssreflect.ssrfun Ssreflect.ssrbool.
Require Import Ssreflect.ssrnat Ssreflect.choice.

Section Halting.

(* [code f c] holds if [f] is representable by some
   Turing machine code [c]. Notice that we don't assume that
   [code] is computable, nor do we assume that all functions 
   [nat -> nat -> option bool] can be represented by some code, 
   which means that we don't rule out the existence of
   non-computable functions. *)
Variable code : (nat -> nat -> option bool) -> nat -> Prop.

(* We assume that we have a [decider] for the halting problem, with
   its specification given by [deciderP]. Specifically, when running
   on a number [m] that represents a pair [(c, n)], where [c] is the
   code for some Turing machine [f] and [n] some input for [f], we
   know that [decider m] will halt at some point, producing [true] iff
   [f] halts on input [n].

   This definition uses a few convenience features from Ssreflect to
   make our lives simpler, namely, the [pickle] function, that
   converts from [nat * nat] to [nat], and the implicit coercion from
   [option] to [bool] ([Some] is mapped to [true], [None] to [false]) *)
Variable decider : nat -> nat -> option bool.
Hypothesis deciderP :
  forall f c, code f c ->
  forall (n : nat),
     (forall s,
        match decider (pickle (c, n)) s with
        | Some true  => exists s', f n s'
        | Some false => forall s', negb (f n s')
        | None => True
        end) /\
     exists s, decider (pickle (c, n)) s.

(* Finally, we define the usual diagonal function, and postulate that
   it is representable by some code [f_code]. *)
Definition f (n : nat) s :=
  match decider (pickle (n, n)) s with
  | Some false => Some false
  | _ => None
  end.
Variable f_code : nat.
Hypothesis f_codeP : code f f_code.

(* The actual proof is straightforward (8 lines long). 
   I'm omitting it to avoid spoiling the fun. *)
Lemma pandora : False.
Proof. (* ... *) Qed.

End Halting.

Таким образом, вполне разумно использовать функции Coq, чтобы говорить о проблеме Halting, и результат довольно прост. Обратите внимание, что приведенная выше теорема не приводит к тому, что code вообще связан с машинами Тьюринга, например, вы могли бы интерпретировать приведенную выше теорему, говоря, что проблема остановки для машин Оракула Тьюринга не может быть решена машиной оракула Тьюринга. В конце концов, то, что делает эти результаты отличными друг от друга, - это формализация базовой модели вычислений, которую вы хотели бы избежать.

Что касается шаблона, с которым вы пытались начать, считая, что Phi существует и имеет обратный, это уже приводит к противоречию. Это обычный диагональный аргумент:

Require Import Ssreflect.ssreflect Ssreflect.ssrfun Ssreflect.ssrbool.
Require Import Ssreflect.ssrnat Ssreflect.choice.

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.

Lemma pandora : False.
Proof.
pose f n (m : nat) :=
  if Phi n n n is Some p then None
  else Some 0.
pose f_code := Phi_inverse f.
move/effective_enumeration: (erefl f_code) => P.
move: (erefl (f f_code f_code)).
rewrite {1}/f P.
by case: (f _ _).
Qed.

Проблема в том, что, хотя внешне мы знаем, что Кок-определимые функции находятся в биекции с nat, мы не можем утверждать этот факт внутренне. Утверждение о существовании неэффективного code отношения решает эту проблему.

Что касается оракулов, то наличие оракула в функции типа nat → bool имеет смысл, но вам нужно убедиться, что вы не нарушаете другие предположения, которые вы имеете в доказательстве, делая это. Например, вы можете постулировать, что все функции nat → nat являются вычислимыми, аксиоматизируя, что у вас есть функция, подобная вашему Phi, но это будет означать, что ваш оракул также будет вычислимым. Использование отношения, такого как code выше, позволяет вам иметь несколько лучших из обоих миров.

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

Definition foo (oracle : nat -> bool) (n : nat) : bool :=
  (* some definition ... *).

Definition oracle_spec (oracle : nat -> bool) : Prop :=
  (* some definition ... *).

Lemma fooP oracle :
  oracle_spec oracle ->
  (* some property of [foo oracle]. *)

Наконец, здесь интересная ссылка, в которой обсуждается церковная диссертация в зависимой теории типов, которую вы можете найти интересной: https://existentialtype.wordpress.com/2012/08/09/churchs-law/

Ответ 2

Здесь, как бы вы представили значимую аксиому (я все еще изучаю Coq так, надеюсь, если бы я сделал это неправильно, кто-то меня поправит).

С Parameter мы оговариваем существование функции, называемой compute не давая определения. С Axiom мы фиксируем некоторые ее свойства (надеюсь, без введения противоречия). Предположительно, Параметр и Аксиома делают то же самое внутри.

Аналогично декларации о compute, ваш Axiom Phi оговаривает существование функции Phi от nat до partial, но вы ничего не можете с ней сделать в Coq поскольку у нее нет известных свойств. Заметим, что существование Phi не подразумевает ничего подобного "есть эффективное перечисление частичных вычислимых функций".

Здесь аксиома утверждает, что при вызове с большим количеством разрешенных шагов вычисления compute никогда не изменяет ACCEPT на REJECT или наоборот или не поддерживает NOTYET. С этими определениями я проверил, что можно доказать тривиальный test леммы как стартера.

Очевидно, я не выполнил это, чтобы убедиться, что вы можете доказать неразрешимость проблемы остановки, но это должно быть возможно, добавив аксиому, утверждающую существование nat представляющего программу, которая вычисляет эквивалентно конструкции, необходимой для доказательства проблема с остановкой. Конечно, в значительной степени весь смысл доказательства теряется, делая это таким образом, но все равно осталось бы еще немного, чтобы доказать.

Inductive result :=
| ACCEPT : result
| REJECT : result
| NOTYET : result.

Definition narrowing a b : Prop :=
(match a with
| ACCEPT => b = ACCEPT
| REJECT => b = REJECT
| NOTYET => True
end).

Parameter compute : nat (* program *) -> nat (* argument *) -> nat (* steps *) -> result.

Axiom compute_narrowing:
forall program input steps steps',
(steps' >= steps) ->
(narrowing (compute program input steps) (compute program input steps')).

Lemma test: ~ exists program input steps, (compute program input steps) = ACCEPT /\ (compute program input (steps + 1)) = NOTYET

EDIT: Здесь немного больше. Немного подумав о проблеме, я понимаю, что я определенно ошибался, что такое доказательство обязательно должно было бы аксиомизировать интересные конструкции. Можно подключить аксиомы, которые позволяют использовать только простые низкоуровневые конструкции и строить над ними более высокие уровни. Я предполагаю, что цель состоит в том, чтобы следовать доказательству Минского, поскольку кажется более простым формализовать:

http://www.cs.odu.edu/~toida/nerzic/390teched/computability/unsolv-1.html

Здесь дополнительные аксиомы утверждают: 1) существование программы, которая всегда принимает 2) существование программы, которая всегда отвергает, и 3) для любых трех программ conditional when_accept when_reject, существование программы, которая сначала работает conditional а затем основана на этом запускается when_accept или when_reject (все вызовы подпрограммы находятся на том же входе, что и в when_reject программе). С помощью этих аксиом можно доказать, что для любой target программы существует программа, которая запускает target а затем выводит противоположный результат (но также и циклически навешивается, если target циклы навсегда). Эта конструкция "отрицания" является просто примером, а не одной из конструкций, используемых в доказательстве Минского.

Чтобы следовать доказательству Минского, нужно было бы добавить дополнительные аксиомы для существования программы, которая циклы, и для построения копира. Затем добавьте определение, когда программа является решающим, и докажите, что нет решения для проблемы с остановкой. Аксиома codec сохраняет необходимость определять функции encode_pair и decode_pair в Coq и доказывать codec как лемму. Я думаю, что свойства encode_pair и decode_pair понадобятся для построения копира и в окончательном доказательстве (конечно, определение решающего фактора для проблемы остановки потребует его, поскольку машинный ввод представляет собой пару).

Require Import List.
Require Import Arith.
Require Import Omega.

Ltac mp_cancel :=
  repeat match goal with
  | [ H2 : ?P -> ?Q , H1 : ?P |- _ ] => specialize (H2 H1)
  end.

Ltac mp_cancel_reflexivity :=
  repeat match goal with
  | [ H1 : ?P = ?P -> ?Q |- _ ] => assert (H_mp_cancel_reflexivity : P = P) by reflexivity; specialize (H1 H_mp_cancel_reflexivity); clear H_mp_cancel_reflexivity
  end.

Inductive result :=
| ACCEPT : result
| REJECT : result
| NOTYET : result
.

Definition narrowing a b : Prop :=
  (match a with
  | ACCEPT => b = ACCEPT
  | REJECT => b = REJECT
  | NOTYET => True
  end)
.

Parameter encode_pair : (nat * nat) -> nat.
Parameter decode_pair : nat -> (nat * nat).

Axiom codec:
  forall a b,
  (decode_pair (encode_pair (a, b))) = (a, b).

Parameter compute : nat (* program *) -> nat (* input *) -> nat (* steps *) -> result.

Axiom compute_narrowing:
  forall program input steps steps',
  (steps' >= steps) -> (narrowing (compute program input steps) (compute program input steps')).

Axiom exists_always_accept:
  exists program_always_accept,
  forall input,
  exists steps,
  (compute program_always_accept input steps) = ACCEPT.

Axiom exists_always_reject:
  exists program_always_reject,
  forall input,
  exists steps,
  (compute program_always_reject input steps) = REJECT.

Definition result_compose_conditional (result_conditional : result) (result_when_accept : result) (result_when_reject : result) : result :=
  (match result_conditional with
  | ACCEPT => result_when_accept
  | REJECT => result_when_reject
  | NOTYET => NOTYET
  end).

Axiom exists_compose_conditional:
  forall program_conditional program_when_accept program_when_reject,
  exists program_composition,
  forall input steps_control steps_when result_conditional result_when_accept result_when_reject,
  (
    ((compute program_conditional input steps_control) = result_conditional) ->
    ((compute program_when_accept input steps_when) = result_when_accept) ->
    ((compute program_when_reject input steps_when) = result_when_reject) ->
    (exists steps_composition, (compute program_composition input steps_composition) = (result_compose_conditional result_conditional result_when_accept result_when_reject))
  ).

Definition result_negation (result_target : result) : result :=
  (match result_target with
  | ACCEPT => REJECT
  | REJECT => ACCEPT
  | NOTYET => NOTYET
  end).

Lemma exists_negation:
  forall program_target,
  exists program_negation,
  forall input steps_target result_target,
  (
    ((compute program_target input steps_target) = result_target) ->
    (exists steps_negation, (compute program_negation input steps_negation) = (result_negation result_target))
  ).
intros.
elim exists_always_accept; intros program_always_accept H_always_accept.
elim exists_always_reject; intros program_always_reject H_always_reject.
elim exists_compose_conditional with (program_conditional := program_target) (program_when_accept := program_always_reject) (program_when_reject := program_always_accept); intros program_negation H_program_negation.
exists program_negation.
intros.
specialize H_always_accept with input. elim H_always_accept; clear H_always_accept; intros steps_accept H_always_accept.
specialize H_always_reject with input. elim H_always_reject; clear H_always_reject; intros steps_reject H_always_reject.
pose (steps_when := (steps_accept + steps_reject)).
specialize H_program_negation with input steps_target steps_when result_target (compute program_always_reject input steps_when) (compute program_always_accept input steps_when).
mp_cancel.
mp_cancel_reflexivity.
elim H_program_negation; clear H_program_negation; intros steps_negation H_program_negation.
exists (steps_negation).
rewrite H_program_negation; clear H_program_negation.
replace (compute program_always_reject input steps_when) with REJECT; symmetry.
replace (compute program_always_accept input steps_when) with ACCEPT; symmetry.
unfold result_compose_conditional.
unfold result_negation.
reflexivity.
assert (T := (compute_narrowing program_always_accept input steps_accept steps_when)).
assert (steps_when >= steps_accept).
unfold steps_when.
omega.
mp_cancel.
unfold narrowing in T.
rewrite H_always_accept in T.
assumption.
assert (T := (compute_narrowing program_always_reject input steps_reject steps_when)).
assert (steps_when >= steps_reject).
unfold steps_when.
omega.
mp_cancel.
unfold narrowing in T.
rewrite H_always_reject in T.
assumption.
Qed.

EDIT # 2: я понял, что вы хотите иметь возможность программировать конструкции в Coq, но я не понял, как это можно сделать во время моего предыдущего редактирования. В следующем фрагменте это делается с использованием exists_program_of_procedure, который утверждает, что существует nat представляющий программу, которая имеет такое же поведение, как любая данная процедура (по крайней мере, для хорошо выполненных процедур, которые "сужаются" при их вычислении). Включено прямое оформление доказательства Минского. У вашего подхода, безусловно, более чистые аксиомы, и, вероятно, это приведет к более коротким доказательствам из-за использования modulus для оракула, а не шагов по стабилизации, а не для narrowing. Самое интересное, чтобы посмотреть, может ли ваш подход быть выполнен без использования Classical. Обновление. Похоже, что ваши аксиомы вводят противоречие, поскольку modulus не должен быть вычислимым (?).

Require Import List.
Require Import Arith.
Require Import Omega.

Ltac mp_cancel :=
  repeat match goal with
  | [ H2 : ?P -> ?Q , H1 : ?P |- _ ] => specialize (H2 H1)
  end.

Ltac mp_cancel_reflexivity :=
  repeat match goal with
  | [ H1 : ?P = ?P -> ?Q |- _ ] => assert (H_mp_cancel_reflexivity : P = P) by reflexivity; specialize (H1 H_mp_cancel_reflexivity); clear H_mp_cancel_reflexivity
  end.

Parameter encode_pair: (nat * nat) -> nat.
Parameter decode_pair: nat -> (nat * nat).

Axiom decode_encode: forall a b, (decode_pair (encode_pair (a, b))) = (a, b).

Inductive result :=
| ACCEPT : result
| REJECT : result
| NOTYET : result.

Definition result_narrowing (a : result) (b : result) : Prop :=
  (match a with
  | ACCEPT => b = ACCEPT
  | REJECT => b = REJECT
  | NOTYET => True
  end).

Lemma result_narrowing_trans: forall a b c, result_narrowing a b -> result_narrowing b c -> result_narrowing a c.
intros until 0.
destruct a; destruct b; destruct c;
  unfold result_narrowing;
  intros;
  try discriminate;
  reflexivity.
Qed.

Parameter compute: nat (* program *) -> nat (* input *) -> nat (* steps *) -> result.

Axiom compute_narrowing:
  forall program input steps steps',
  (steps' >= steps) -> (result_narrowing (compute program input steps) (compute program input steps')).

Require Import Classical.

Lemma compute_non_divergent:
  forall program input steps steps',
  (compute program input steps) = ACCEPT ->
  (compute program input steps') = REJECT ->
  False.
intros.
assert (T := (classic (steps' >= steps))).
destruct T.
assert (T := (compute_narrowing program input steps steps')).
mp_cancel.
rewrite H, H0 in T.
unfold result_narrowing in T.
discriminate T.
unfold not in H1.
assert (T := (classic (steps' = steps))).
destruct T.
rewrite H2 in H0.
rewrite H in H0.
discriminate.
assert (steps >= steps').
omega.
assert (T := (compute_narrowing program input steps' steps)).
mp_cancel.
rewrite H, H0 in T.
unfold result_narrowing in T.
discriminate.
Qed.

Definition procedure_type := nat (* input *) -> nat (* depth *) -> result.

Definition procedure_narrowing (procedure : procedure_type) : Prop :=
  forall input depth depth',
  (depth' >= depth) -> (result_narrowing (procedure input depth) (procedure input depth')).

Axiom exists_program_of_procedure:
  forall procedure : procedure_type,
  (procedure_narrowing procedure) ->
  exists program,
  forall input,
  (
    forall depth,
    exists steps,
    (result_narrowing (procedure input depth) (compute program input steps))
  ) /\
  (
    forall steps,
    exists depth,
    (result_narrowing (compute program input steps) (procedure input depth))
  ).

Definition program_halts_on_input (program : nat) (input : nat) : Prop :=
  (exists steps, (compute program input steps) <> NOTYET).

Definition program_is_decider (program : nat) : Prop :=
  forall input,
  exists steps,
  (compute program input steps) <> NOTYET.

Definition program_solves_halting_problem_partially (program : nat) : Prop :=
  forall input,
  forall steps,
  (
       ((compute program input steps) = ACCEPT)
    -> (match (decode_pair input) with | (target_program, target_input) => (  (program_halts_on_input target_program target_input)) end)
  ) /\
  (
       ((compute program input steps) = REJECT)
    -> (match (decode_pair input) with | (target_program, target_input) => (~ (program_halts_on_input target_program target_input)) end)
  ).

Lemma minsky: (~ (exists halts, (program_is_decider halts) /\ (program_solves_halting_problem_partially halts))).
unfold not.
intros H_ph.
elim H_ph; clear H_ph; intros invocation_halts [H_ph_d H_ph_b].
pose
  (procedure_modified := (fun (input : nat) (depth : nat) =>
    (match (compute invocation_halts input depth) with
    | ACCEPT => NOTYET
    | REJECT => REJECT
    | NOTYET => NOTYET
    end))).
pose
  (procedure_wrapper := (fun (input : nat) (depth : nat) =>
    (procedure_modified (encode_pair (input, input)) depth))).
unfold procedure_modified in procedure_wrapper.
clear procedure_modified.
assert (T1 := (exists_program_of_procedure procedure_wrapper)).
assert (T2 : (procedure_narrowing procedure_wrapper)).
{
  clear T1.
  unfold procedure_narrowing, procedure_wrapper.
  intros.
  unfold result_narrowing.
  case_eq (compute invocation_halts (encode_pair (input, input)) depth); try intuition.
  assert (T := (compute_narrowing invocation_halts (encode_pair (input, input)) depth depth')).
  mp_cancel.
  rewrite H0 in T.
  unfold result_narrowing in T.
  rewrite T.
  reflexivity.
}
mp_cancel.
clear T2.
elim T1; clear T1; intros program_wrapper H_pw.
unfold procedure_wrapper in H_pw.
clear procedure_wrapper.
specialize (H_pw program_wrapper).
destruct H_pw as [H_pw_fwd H_pw_rev].
unfold program_is_decider in H_ph_d.
specialize (H_ph_d (encode_pair (program_wrapper, program_wrapper))).
elim H_ph_d; clear H_ph_d; intros steps_inner H_ph_d.
unfold program_solves_halting_problem_partially in H_ph_b.
specialize (H_ph_b (encode_pair (program_wrapper, program_wrapper)) steps_inner).
destruct H_ph_b as [H_ph_b_1 H_ph_b_2].
case_eq (compute invocation_halts (encode_pair (program_wrapper, program_wrapper)) steps_inner).
{
  intros.
  rewrite H in *.
  mp_cancel_reflexivity.
  unfold program_halts_on_input in H_ph_b_1.
  rewrite decode_encode in H_ph_b_1.
  elim H_ph_b_1; clear H_ph_b_1; intros steps_outer H_ph_b_1.
  specialize (H_pw_rev steps_outer).
  case_eq (compute program_wrapper program_wrapper steps_outer).
  {
    intros.
    rewrite H0 in *.
    unfold result_narrowing in H_pw_rev.
    elim H_pw_rev; clear H_pw_rev; intros depth H_pw_rev.
    case_eq (compute invocation_halts (encode_pair (program_wrapper, program_wrapper)) depth); intros Hx; rewrite Hx in *; try discriminate.
  }
  {
    intros.
    rewrite H0 in *.
    unfold result_narrowing in H_pw_rev.
    elim H_pw_rev; clear H_pw_rev; intros depth H_pw_rev.
    case_eq (compute invocation_halts (encode_pair (program_wrapper, program_wrapper)) depth); intros Hx; rewrite Hx in *; try discriminate.
    assert (T := (compute_non_divergent invocation_halts (encode_pair (program_wrapper, program_wrapper)) steps_inner depth)).
    mp_cancel.
    assumption.
  }
  {
    intros.
    intuition.
  }
}
{
  intros.
  rewrite H in *.
  mp_cancel_reflexivity.
  unfold not, program_halts_on_input in H_ph_b_2.
  specialize (H_pw_fwd steps_inner).
  rewrite H in H_pw_fwd.
  unfold result_narrowing in H_pw_fwd.
  elim H_pw_fwd; intros.
  rewrite decode_encode in H_ph_b_2.
  contradict H_ph_b_2.
  exists x.
  unfold not.
  intros.
  rewrite H0 in H1.
  discriminate.
}
{
  intros.
  unfold not in H_ph_d.
  mp_cancel.
  assumption.
}
Qed.

Ответ 3

Я думал, что добавлю новый ответ, чтобы описать детали схемы, которую я предложил в комментариях к сообщению OP относительно обработки оракулов.

Я не уверен, может ли схема DeAmorim обрабатывать оракулы, чтобы работать так же хорошо. Философия здесь заключается в том, что следует избегать постулирования существования конструкций с различными свойствами и просто определять их вместо (например, как функции Кок) и показать, что они обладают требуемыми свойствами. Поскольку мы не хотим обрабатывать фактические описания машин Тьюринга до уровня государственных машин, используемым хакером является постулирование сопоставления функций Coq с программами. Когда предполагается, что функции Coq могут быть сопоставлены с программами, логика неизбежно становится непоследовательной, когда вводится бесспорный оракул в виде функции Coq (хотя, по-видимому, он не будет давать конструктивного определения). Хотя маловероятно, что можно было бы использовать такую возникающую несогласованность логики в ручном доказательстве, более обнадеживающе избегать противоречивой логики.

(Тем не менее, неясно, достигает ли предлагаемая стратегия. Статья, связанная с ответом ДеАморима, гласит: "Утверждение состоит в том, что Закон Церкви, заявленный как тип (предложение) в рамках ETT, является ложным, то есть он подразумевает противоречие ". Математика позади этого, кажется, немного выше моего уровня, мне не ясно, применяется ли она.)

Примером рассматриваемой здесь проблемы является решение H_TM, предполагающее, что у нас есть оракул для A_TM. H_TM сообщает нам, что машина Тьюринга ("программа") останавливается для определенного входа, тогда как A_TM сообщает нам, принимает ли машина Тьюринга определенный вход.

Ясно, что обратный случай наличия оракула для H_TM и попытки решить A_TM совершенно тривиален. Просто запросите оракул, чтобы определить, приостанавливается ли программа, и если да, программа может быть запущена до завершения, чтобы определить, принимает ли она.

Несколько менее тривиально, H_TM можно решить, если нам дается оракул для A_TM. Очевидно, что если машина примет вход, запрос оракула может определить это. Теперь трюк состоит в том, чтобы построить модифицированную программу, которая делает противоположную исходную программу (обменивает ACCEPT и REJECT), и запрос оракула в этой модифицированной программе теперь определяет, будет ли исходная программа отклонять вход. Если оракул отклонил оба случая, исходная программа циклы на данном входе, и мы отказываемся (в других случаях мы принимаем).

Используемый здесь "механизм" позволяет определять верификаторы оракула типа nat (* query *) → nat (* wisdom *) → bool (* advice *). Настоящий оракул, соответствующий верификатору, выдаст true, если существует значение мудрости, которое заставляет верификатор выводить true. Умный бит заключается в том, что невычислимые оракулы могут быть сгенерированы из вычислимых верификаторов, а одного квантора существования достаточно для создания довольно мощных оракулов.

"Процедура с oracle" (pwo) должна быть реализована в терминах состояния цикла, так как нельзя просто использовать приложение функции для вызова оракула в этой настройке.

Индуктивный pwo_entails основном определяет оценку pwo s, аналогично тому, как оценка программ Imp определяется ceval в Software Foundations.

Верификатор оракула для A_TM orv_atm просто выполняет программу для шагов мудрости, чтобы определить, принимает ли она, в то время как pwo_hfa составляет до двух вызовов оракула, чтобы решить H_TM. Лемма H_from_A показывает, что это работает.

Одно большое изменение в предыдущем ответе на проблему Halting заключается в том, что основная аксиома, позволяющая преобразовывать функции Coq в программы, которые могут быть переданы для compute, была усилена, теперь предполагается, что существует вычислимая функция для выполнения такого преобразования. Раньше постулировалось только существование соответствующей программы. Это изменение необходимо, так как pwo_hfa необходимо сгенерировать программу "программно".

Require Import List.
Require Import Arith.
Require Import Omega.

Ltac mp_cancel :=
  repeat match goal with
  | [ H2 : ?P -> ?Q , H1 : ?P |- _ ] => specialize (H2 H1)
  end.

Ltac mp_cancel_reflexivity :=
  repeat match goal with
  | [ H1 : ?P = ?P -> ?Q |- _ ] => assert (H_mp_cancel_reflexivity : P = P) by reflexivity; specialize (H1 H_mp_cancel_reflexivity); clear H_mp_cancel_reflexivity
  end.

Parameter encode_pair: (nat * nat) -> nat.
Parameter decode_pair: nat -> (nat * nat).

Axiom decode_encode: forall a b, (decode_pair (encode_pair (a, b))) = (a, b).
Axiom encode_decode: forall x,   (encode_pair (decode_pair x)) = x.

Inductive result :=
| ACCEPT : result
| REJECT : result
| NOTYET : result.

Definition result_narrowing (a : result) (b : result) : Prop :=
  (match a with
  | ACCEPT => b = ACCEPT
  | REJECT => b = REJECT
  | NOTYET => True
  end).

Lemma result_narrowing_trans: forall a b c, result_narrowing a b -> result_narrowing b c -> result_narrowing a c.
intros until 0.
destruct a; destruct b; destruct c;
  unfold result_narrowing;
  intros;
  try discriminate;
  reflexivity.
Qed.

Lemma result_push_accept: forall x, result_narrowing ACCEPT x -> x = ACCEPT.
unfold result_narrowing.
intuition.
Qed.

Lemma result_push_reject: forall x, result_narrowing REJECT x -> x = REJECT.
unfold result_narrowing.
intuition.
Qed.

Parameter compute: nat (* program *) -> nat (* input *) -> nat (* steps *) -> result.

Axiom compute_narrowing:
  forall program input steps steps',
  (steps' >= steps) -> (result_narrowing (compute program input steps) (compute program input steps')).

Require Import Classical.

Lemma compute_non_divergent:
  forall program input steps steps',
  (compute program input steps) = ACCEPT ->
  (compute program input steps') = REJECT ->
  False.
intros.
assert (T := (classic (steps' >= steps))).
destruct T.
assert (T := (compute_narrowing program input steps steps')).
mp_cancel.
rewrite H, H0 in T.
unfold result_narrowing in T.
discriminate T.
unfold not in H1.
assert (T := (classic (steps' = steps))).
destruct T.
rewrite H2 in H0.
rewrite H in H0.
discriminate.
assert (steps >= steps').
omega.
assert (T := (compute_narrowing program input steps' steps)).
mp_cancel.
rewrite H, H0 in T.
unfold result_narrowing in T.
discriminate.
Qed.

Definition procedure_type := nat (* input *) -> nat (* depth *) -> result.

Definition procedure_narrowing (procedure : procedure_type) : Prop :=
  forall input depth depth',
  (depth' >= depth) -> (result_narrowing (procedure input depth) (procedure input depth')).

Parameter program_of_procedure: procedure_type (* procedure *) -> nat (* program *).

Axiom program_of_procedure_behavior:
  forall procedure : procedure_type,
  (procedure_narrowing procedure) ->
  forall input,
  (
    forall depth,
    exists steps,
    (result_narrowing (procedure input depth) (compute (program_of_procedure procedure) input steps))
  ) /\
  (
    forall steps,
    exists depth,
    (result_narrowing (compute (program_of_procedure procedure) input steps) (procedure input depth))
  ).

Definition program_halts_on_input (program : nat) (input : nat) : Prop :=
  (exists steps, (compute program input steps) <> NOTYET).

(* orv = oracle verifier *)

Definition orv_type := nat (* query *) -> nat (* wisdom *) -> bool (* advice *).

Definition oracle_accepts (oracle : orv_type) (query : nat) :=
  exists wisdom, (oracle query wisdom) = true.

Definition oracle_rejects (orv : orv_type) (inp : nat) := (~ (oracle_accepts orv inp)).

(* pwo = procedure with oracle *)

Inductive pwo_out :=
| PWO_RESULT : bool (* result *) -> pwo_out
| PWO_ORACLE : nat (* state *) -> nat (* query *) -> pwo_out
.

Definition pwo_type := nat (* input *) -> nat (* state *) -> bool (* advice *) -> pwo_out.

Inductive pwo_entails: orv_type (* oracle *) -> pwo_type (* procedure *) -> nat (* input *) -> nat (* state *) -> bool (* advice *) -> bool (* result *) -> Prop :=
| PwoEntailsResult:
forall oracle procedure input state advice result,
(procedure input state advice) = (PWO_RESULT result) ->
(pwo_entails oracle procedure input state advice result)
| PwoEntailsOracleAccept:
forall oracle procedure input state advice result state' query,
(procedure input state advice) = (PWO_ORACLE state' query) ->
(oracle_accepts oracle query) ->
(pwo_entails oracle procedure input state' true   result) ->
(pwo_entails oracle procedure input state  advice result)
| PwoEntailsOracleReject:
forall oracle procedure input state advice result state' query,
(procedure input state advice) = (PWO_ORACLE state' query) ->
(oracle_rejects oracle query) ->
(pwo_entails oracle procedure input state' false  result) ->
(pwo_entails oracle procedure input state  advice result)
.

Definition pwo_decider_relative (orv : orv_type) (pwo : pwo_type) :=
  forall input,
  (pwo_entails orv pwo input 0 false false) \/
  (pwo_entails orv pwo input 0 false true).

(* define oracle for A_TM (turing machine accepts a particular input) *)

Definition orv_atm (pair_program_input : nat) (wisdom : nat) : bool :=
  (match (decode_pair pair_program_input) with
  | (target_program, target_input) =>
      (match (compute target_program target_input wisdom) with
      | ACCEPT => true
      | _ => false
      end)
  end).

(* define procedure for H_TM (turing machine halts on a particular input) relative to an oracle for A_TM *)

Definition pwo_hfa_construction (target_program : nat) :=
  (fun input depth =>
    (match (compute target_program input depth) with
    | ACCEPT => REJECT
    | REJECT => ACCEPT
    | NOTYET => NOTYET
  end)).

Lemma pwo_hfa_construction_narrowing: forall target_program, (procedure_narrowing (pwo_hfa_construction target_program)).
intros.
unfold procedure_narrowing, result_narrowing, pwo_hfa_construction.
intros.
case_eq (compute target_program input depth); intro; try
(
case_eq (compute target_program input depth'); intro; try reflexivity; try
(
assert (T := (compute_narrowing target_program input depth depth'));
mp_cancel;
unfold result_narrowing in T;
rewrite H0 in T;
rewrite H1 in T;
discriminate
)
).
Qed.

Definition pwo_hfa (input : nat) (state : nat) (advice : bool) : pwo_out :=
  (match (decode_pair input) with
  | (target_program, target_input) =>
      (match state with
      | O =>
        (PWO_ORACLE 1 (encode_pair (target_program, target_input)))
      | (S O) =>
        (if advice
         then (PWO_RESULT true)
         else (PWO_ORACLE 2 (encode_pair ((program_of_procedure (pwo_hfa_construction target_program)), target_input))))
      | _ =>
        (PWO_RESULT advice)
      end)
  end).

Lemma H_from_A:
  exists pwo_hfa,
  (pwo_decider_relative orv_atm pwo_hfa) /\
  (
    forall input,
      (pwo_entails orv_atm pwo_hfa input 0 false true  ->
        (match (decode_pair input) with | (target_program, target_input) => (  (program_halts_on_input target_program target_input)) end)) /\
      (pwo_entails orv_atm pwo_hfa input 0 false false ->
        (match (decode_pair input) with | (target_program, target_input) => (~ (program_halts_on_input target_program target_input)) end))
  )
.
exists pwo_hfa.
split.
{
  unfold pwo_decider_relative.
  intros.
  pose (pair := (decode_pair input)).
  case_eq (pair); intros target_program target_input H_pair.
  replace input with (encode_pair (target_program, target_input)).
  Focus 2.
  {
    rewrite <- H_pair.
    unfold pair.
    apply encode_decode.
  }
  Unfocus.
  assert (T1 := (classic (oracle_accepts orv_atm (encode_pair (target_program, target_input))))).
  destruct T1 as [T1 | T1].
  {
    right.
    eapply PwoEntailsOracleAccept.
    Focus 2.
    eexact T1.
    unfold pwo_hfa.
    rewrite decode_encode.
    instantiate (1 := 1).
    reflexivity.
    apply PwoEntailsResult.
    unfold pwo_hfa.
    rewrite decode_encode.
    reflexivity.
  }
  {
    assert (T2 := (classic (oracle_accepts orv_atm (encode_pair ((program_of_procedure (pwo_hfa_construction target_program)), target_input))))).
    destruct T2 as [T2 | T2].
    {
      right.
      eapply PwoEntailsOracleReject.
      Focus 2.
      unfold oracle_rejects.
      eexact T1.
      unfold pwo_hfa.
      rewrite decode_encode.
      instantiate (1 := 1).
      reflexivity.
      eapply PwoEntailsOracleAccept.
      Focus 2.
      eexact T2.
      unfold pwo_hfa.
      rewrite decode_encode.
      instantiate (1 := 2).
      reflexivity.
      apply PwoEntailsResult.
      unfold pwo_hfa.
      rewrite decode_encode.
      reflexivity.
    }
    {
      left.
      eapply PwoEntailsOracleReject.
      Focus 2.
      unfold oracle_rejects.
      eexact T1.
      unfold pwo_hfa.
      rewrite decode_encode.
      instantiate (1 := 1).
      reflexivity.
      eapply PwoEntailsOracleReject.
      Focus 2.
      eexact T2.
      unfold pwo_hfa.
      rewrite decode_encode.
      instantiate (1 := 2).
      reflexivity.
      apply PwoEntailsResult.
      unfold pwo_hfa.
      rewrite decode_encode.
      reflexivity.
    }
  }
}
{
  intros.
  case_eq (decode_pair input); intros target_program target_input H_input.
  replace input with (encode_pair (target_program, target_input)).
  Focus 2.
  {
    rewrite <- H_input.
    rewrite encode_decode.
    reflexivity.
  }
  Unfocus.
  clear H_input.
  split.
  {
    intros.
    inversion H; subst.
    {
      unfold pwo_hfa in H0.
      rewrite decode_encode in H0.
      discriminate H0.
    }
    {
      unfold pwo_hfa in H0.
      rewrite decode_encode in H0.
      injection H0.
      intros.
      rewrite <- H3 in H1.
      unfold oracle_accepts in H1.
      unfold program_halts_on_input.
      elim H1; intros.
      exists x.
      unfold orv_atm in H5.
      rewrite decode_encode in H5.
      destruct (compute target_program target_input x); try intuition; try discriminate.
    }
    {
      unfold pwo_hfa in H0.
      rewrite decode_encode in H0.
      injection H0.
      intros.
      rewrite <- H4 in *.
      inversion H2; subst.
      {
        unfold pwo_hfa in H5.
        rewrite decode_encode in H5.
        discriminate.
      }
      {
        unfold pwo_hfa in H5.
        rewrite decode_encode in H5.
        injection H5; intros.
        subst.
        unfold oracle_accepts in H6.
        unfold program_halts_on_input.
        elim H6; intros.
        unfold orv_atm in H3.
        rewrite decode_encode in H3.
        case_eq (compute (program_of_procedure (pwo_hfa_construction target_program)) target_input x); intros; rewrite H4 in H3; try discriminate.
        assert
          (T :=
            (program_of_procedure_behavior
              (pwo_hfa_construction target_program)
              (pwo_hfa_construction_narrowing target_program)
              target_input
            )).
        destruct T.
        specialize H9 with x.
        elim H9; intros.
        assert ((pwo_hfa_construction target_program target_input x0) = ACCEPT).
        eapply result_push_accept.
        rewrite <- H4.
        assumption.
        unfold pwo_hfa_construction in H11.
        case_eq (compute target_program target_input x0); intros; rewrite H12 in H11; try discriminate.
        exists x0.
        unfold not.
        intros.
        rewrite H12 in H13.
        discriminate.
      }
      {
        unfold pwo_hfa in H5.
        rewrite decode_encode in H5.
        injection H5; intros.
        subst.
        inversion H7.
        unfold pwo_hfa in H3.
        rewrite decode_encode in H3.
        discriminate H3.
        unfold pwo_hfa in H3.
        rewrite decode_encode in H3.
        discriminate H3.
        unfold pwo_hfa in H3.
        rewrite decode_encode in H3.
        discriminate H3.
      }
    }
  }
  {
    intros.
    unfold not.
    intros.
    inversion H; subst; unfold pwo_hfa in H1; rewrite decode_encode in H1; try discriminate; injection H1; intros; subst.
    {
      inversion H3; subst; unfold pwo_hfa in H4; rewrite decode_encode in H4; try discriminate; injection H4; intros; subst.
    }
    {
      inversion H3; subst; unfold pwo_hfa in H4; rewrite decode_encode in H4; try discriminate; injection H4; intros; subst.
      {
        inversion H6; subst; unfold pwo_hfa in H7; rewrite decode_encode in H7; try discriminate.
      }
      {
        (* oracle rejected both on a program that halts *)
        clear H H3 H1 H6 H4.
        unfold program_halts_on_input in H0.
        elim H0; clear H0; intros.
        unfold not in H.
        case_eq (compute target_program target_input x); intros; try ( solve [ intuition ] ).
        {
          rename H2 into HH.
          unfold oracle_rejects, not in HH.
          apply HH.
          clear HH.
          unfold oracle_accepts.
          exists x.
          unfold orv_atm.
          rewrite decode_encode.
          rewrite H0.
          reflexivity.
        }
        {
          rename H5 into HH.
          unfold oracle_rejects, not in HH.
          apply HH.
          clear HH.
          unfold oracle_accepts.
          assert
          (T :=
            (program_of_procedure_behavior
              (pwo_hfa_construction target_program)
              (pwo_hfa_construction_narrowing target_program)
              target_input
            )).
          destruct T.
          assert ((pwo_hfa_construction target_program target_input x) = ACCEPT).
          unfold pwo_hfa_construction.
          rewrite H0.
          reflexivity.
          specialize H1 with x.
          elim H1; intros.
          rewrite H4 in H5.
          unfold result_narrowing in H5.
          exists x0.
          unfold orv_atm.
          rewrite decode_encode.
          rewrite H5.
          reflexivity.
        }
      }
    }
  }
}
Qed.