From Undecidability.TM Require Import TM Util.TM_facts.
Definition Assert (sig : Type) (n : nat) : Type := tapes sig n -> Prop.
Definition Triple_Rel {sig : finType} {n : nat} {F : Type} (P : Assert sig n) (Q : F -> Assert sig n) : pRel sig F n :=
fun tin '(yout, tout) => P tin -> Q yout tout.
Inductive Triple {sig : finType} {n : nat} {F : Type} P (pM : pTM sig F n) Q :=
TripleI : pM ⊨ Triple_Rel P Q -> Triple P pM Q.
Lemma TripleE {sig : finType} {n : nat} {F : Type} P (pM : pTM sig F n) Q:
Triple P pM Q -> pM ⊨ Triple_Rel P Q.
Proof. now inversion 1. Qed.
Lemma Triple_iff {sig : finType} {n : nat} {F : Type} P (pM : pTM sig F n) Q:
Triple P pM Q <-> pM ⊨ Triple_Rel P Q.
Proof. split;eauto using TripleE,TripleI. Qed.
Definition Triple_TRel {sig : finType} {n : nat} (P : Assert sig n) (k : nat) : tRel sig n :=
fun tin k' => P tin /\ k <= k'.
Inductive TripleT {sig : finType} {n : nat} {F : Type} (P : Assert sig n) (k : nat) (pM : pTM sig F n) (Q : F -> Assert sig n) :=
TripleTI : Triple P pM Q -> projT1 pM ↓ Triple_TRel P k -> TripleT P k pM Q.
Lemma TripleTE {sig : finType} {n : nat} {F : Type} P k (pM : pTM sig F n) Q:
TripleT P k pM Q -> Triple P pM Q /\ projT1 pM ↓ Triple_TRel P k.
Proof. now inversion 1. Qed.
Lemma TripleT_iff {sig : finType} {n : nat} {F : Type} P k (pM : pTM sig F n) Q:
TripleT P k pM Q <-> (Triple P pM Q /\ projT1 pM ↓ Triple_TRel P k).
Proof. split;firstorder eauto using TripleTE,TripleTI. Qed.
Lemma TripleT_Triple {sig : finType} {n : nat} {F : Type} P k (pM : pTM sig F n) Q :
TripleT P k pM Q ->
Triple P pM Q.
Proof. now intros ?%TripleTE. Qed.
Hint Resolve TripleT_Triple : core.
Lemma Triple_False {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n) Q :
Triple (fun _ => False) pM Q.
Proof. hnf. firstorder. Qed.
Hint Resolve Triple_False : core.
Lemma TripleT_False {sig : finType} {n : nat} {F : Type} k (pM : pTM sig F n) Q :
TripleT (fun _ => False) k pM Q.
Proof. hnf. firstorder. Qed.
Hint Resolve TripleT_False : core.
Lemma Triple_True {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n) P :
Triple P pM (fun _ _ => True).
Proof. hnf. firstorder. Qed.
Hint Resolve Triple_True : core.
Lemma Realise_Triple {sig : finType} {n : nat} {F : Type} (P : Assert sig n) (pM : pTM sig F n) (Q : F -> Assert sig n) (R : pRel sig F n) :
pM ⊨ R ->
(forall tin yout tout, R tin (yout, tout) -> P tin -> Q yout tout) ->
Triple P pM Q.
Proof.
intros H1 H2. apply TripleI. unfold Triple_Rel. eapply Realise_monotone.
+ eapply H1.
+ intros tin (yout, tout). firstorder.
Qed.
Lemma Realise_TripleT {sig : finType} {n : nat} {F : Type} (P : Assert sig n) (k : nat) (pM : pTM sig F n) (Q : F -> Assert sig n) (R : pRel sig F n) (T : tRel sig n) :
pM ⊨ R ->
projT1 pM ↓ T ->
(forall tin yout tout, R tin (yout, tout) -> P tin -> Q yout tout) ->
(forall tin k', P tin -> k <= k' -> T tin k') ->
TripleT P k pM Q.
Proof.
intros H1 H2. split.
- eapply Realise_Triple; eauto.
- unfold Triple_TRel. eapply TerminatesIn_monotone; eauto.
intros tin k' (?&Hk). firstorder.
Qed.
Lemma Triple_Realise {sig : finType} {n : nat} {F : Type} (P : Assert sig n) (pM : pTM sig F n) (Q : F -> Assert sig n) :
Triple P pM Q ->
pM ⊨ (fun tin '(yout,tout) => P tin -> Q yout tout).
Proof.
intros ?%TripleE. now unfold Triple_Rel in *.
Qed.
Lemma TripleT_Realise {sig : finType} {n : nat} {F : Type} (P : Assert sig n) k (pM : pTM sig F n) (Q : F -> Assert sig n) :
TripleT P k pM Q ->
pM ⊨ (fun tin '(yout,tout) => P tin -> Q yout tout).
Proof.
intros ?%TripleTE. now apply Triple_Realise .
Qed.
Lemma TripleT_TerminatesIn {sig : finType} {n : nat} {F : Type} (P : Assert sig n) (k : nat) (pM : pTM sig F n) (Q : F -> Assert sig n):
TripleT P k pM Q ->
projT1 pM ↓ (fun tin k' => P tin /\ k <= k').
Proof.
intros ?%TripleTE. unfold Triple_TRel in *. tauto.
Qed.
Lemma RealiseIn_TripleT {sig : finType} {n : nat} {F : Type} (P : Assert sig n) k (pM : pTM sig F n) (Q : F -> Assert sig n) (R : pRel sig F n) :
pM ⊨c(k) R ->
(forall tin yout tout, R tin (yout, tout) -> P tin -> Q yout tout) ->
TripleT P k pM Q.
Proof.
intros H1 H2. split.
- eapply Realise_Triple.
+ eapply RealiseIn_Realise; eauto.
+ firstorder.
- unfold Triple_TRel. eapply TerminatesIn_monotone.
+ eapply Realise_total. apply H1.
+ now intros tin k' (H&Hk).
Qed.
Inductive Entails (sig : Type) (n : nat) (P1 P2 : Assert sig n) :=
EntailsI : (forall tin, P1 tin -> P2 tin) -> Entails P1 P2.
Lemma EntailsE (sig : Type) (n : nat) (P1 P2 : Assert sig n):
Entails P1 P2 -> (forall tin, P1 tin -> P2 tin).
Proof. now inversion 1. Qed.
Arguments Entails {_ _} _ _.
Lemma Entails_iff (sig : Type) (n : nat) (P1 P2 : Assert sig n):
Entails P1 P2 <-> (forall tin, P1 tin -> P2 tin).
Proof. split;firstorder eauto using EntailsE,EntailsI. Qed.
Hint Resolve EntailsI : core.
Instance Entails_PO (sig : Type) (n : nat): PreOrder (@Entails sig n).
Proof. split;hnf. all:setoid_rewrite Entails_iff. all:eauto. Qed.
Lemma Consequence (sig : finType) (n : nat) (F : Type) (P1 P2 : Assert sig n) (Q1 Q2 : F -> Assert sig n) (pM : pTM sig F n) :
Triple P2 pM Q2 ->
Entails P1 P2 ->
(forall y, Entails (Q2 y) (Q1 y)) ->
Triple P1 pM Q1.
Proof.
intros H1%TripleE H2 H3. apply TripleI. setoid_rewrite Entails_iff in H2. setoid_rewrite Entails_iff in H3.
eapply Realise_monotone.
{ apply H1. }
{ intros tin (yout, tout) H4. cbn in H4. cbn. intros H5. auto.
}
Qed.
Lemma asPointwise A X (R: A -> A -> Prop) f g: (forall (x:X), R (f x) (g x)) -> pointwise_relation X R f g.
Proof. now cbv. Qed.
Instance Triple_Entails_Proper sig n F: Proper (Entails --> eq ==> pointwise_relation F Entails ==> Basics.impl) (@Triple sig n F).
Proof. repeat intro. subst. eapply Consequence;eauto. Qed.
Lemma Consequence_pre (sig : finType) (n : nat) (F : Type) (P1 P2 : Assert sig n) (Q : F -> Assert sig n) (pM : pTM sig F n) :
Triple P2 pM Q ->
Entails P1 P2 ->
Triple P1 pM Q.
Proof. now intros ? ->. Qed.
Lemma Consequence_post (sig : finType) (n : nat) (F : Type) (P : Assert sig n) (Q1 Q2 : F -> Assert sig n) (pM : pTM sig F n) :
Triple P pM Q2 ->
(forall y, Entails (Q2 y) (Q1 y)) ->
Triple P pM Q1.
Proof. now intros ? <-%asPointwise. Qed.
Lemma ConsequenceT (sig : finType) (n : nat) (F : Type) (P1 P2 : Assert sig n) (k1 k2 : nat) (Q1 Q2 : F -> Assert sig n) (pM : pTM sig F n) :
TripleT P2 k2 pM Q2 ->
Entails P1 P2 ->
(forall y, Entails (Q2 y) (Q1 y)) ->
k2 <= k1 ->
TripleT P1 k1 pM Q1.
Proof.
intros (H0&H1)%TripleTE H2 H3%asPointwise H4.
split. now rewrite H2, <- H3.
- eapply TerminatesIn_monotone.
+ apply H1.
+ unfold Triple_TRel. intros tin k (H&H'). split. 2: lia. setoid_rewrite Entails_iff in H2. eauto.
Qed.
Instance TripleT_Entails_Proper sig n F: Proper (Entails --> le ==> eq ==> pointwise_relation F Entails ==> Basics.impl) (@TripleT sig n F).
Proof. repeat intro. subst. eapply ConsequenceT;eauto. Qed.
Lemma ConsequenceT_post (sig : finType) (n : nat) (F : Type) (P : Assert sig n) (k : nat) (Q1 Q2 : F -> Assert sig n) (pM : pTM sig F n) :
TripleT P k pM Q2 ->
(forall y, Entails (Q2 y) (Q1 y)) ->
TripleT P k pM Q1.
Proof. intros. eapply ConsequenceT; eauto. Qed.
Lemma ConsequenceT_pre (sig : finType) (n : nat) (F : Type) (P1 P2 : Assert sig n) (k1 k2 : nat) (Q : F -> Assert sig n) (pM : pTM sig F n) :
TripleT P2 k2 pM Q ->
Entails P1 P2 ->
k2 <= k1 ->
TripleT P1 k1 pM Q.
Proof. intros. eapply ConsequenceT; eauto. Qed.
Lemma Triple_exists_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : X -> Assert sig n) (Q : F -> Assert sig n) :
(forall (x : X), Triple (P x) pM Q) ->
Triple (fun tin => exists x : X, P x tin) pM (Q).
Proof. setoid_rewrite Triple_iff. unfold Triple_Rel. firstorder. Qed.
Lemma Triple_exists_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : Assert sig n) (Q : X -> F -> Assert sig n) :
(exists (x : X), Triple P pM (Q x)) ->
Triple P pM (fun yout tout => exists x : X, Q x yout tout).
Proof. setoid_rewrite Triple_iff. unfold Triple_Rel. firstorder. Qed.
Lemma Triple_forall_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : X -> Assert sig n) (Q : F -> Assert sig n) :
(exists (x : X), Triple (P x) pM Q) ->
Triple (fun tin => forall x : X, P x tin) pM (Q).
Proof. setoid_rewrite Triple_iff. unfold Triple_Rel. firstorder. Qed.
Lemma Triple_forall_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : Assert sig n) (Q : X -> F -> Assert sig n) :
(forall (x : X), Triple P pM (Q x)) ->
Triple P pM (fun yout tout => forall x : X, Q x yout tout).
Proof. setoid_rewrite Triple_iff. unfold Triple_Rel. firstorder. Qed.
Lemma Triple_eta_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q : F -> Assert sig n) :
Triple P pM Q ->
Triple (fun tin => P tin) pM Q.
Proof. exact id. Qed.
Lemma Triple_eta_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q : F -> Assert sig n) :
Triple P pM Q ->
Triple P pM (fun yout => Q yout).
Proof. exact id. Qed.
Lemma Triple_eta_con2 {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q : F -> Assert sig n) :
Triple P pM Q ->
Triple P pM (fun yout tout => Q yout tout).
Proof. exact id. Qed.
Lemma Triple_and_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P1 : Assert sig n) (P2 : Prop) (Q : F -> Assert sig n) :
(P2 -> Triple P1 pM Q) ->
Triple (fun tin => P2 /\ P1 tin) pM Q.
Proof. setoid_rewrite Triple_iff. unfold Triple_Rel. firstorder. Qed.
Lemma Triple_and_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q1 : F -> Assert sig n) (Q2 : Prop) :
Triple P pM Q1 ->
Q2 ->
Triple P pM (fun yout tout => Q2 /\ Q1 yout tout).
Proof. setoid_rewrite Triple_iff. unfold Triple_Rel. firstorder. Qed.
Lemma TripleT_exists_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : X -> Assert sig n) (Q : F -> Assert sig n) k :
(forall (x : X), TripleT (P x) k pM Q) ->
TripleT (fun tin => exists x : X, P x tin) k pM (Q).
Proof. setoid_rewrite TripleT_iff;setoid_rewrite Triple_iff. unfold Triple_Rel,Triple_TRel. firstorder. Qed.
Lemma TripleT_exists_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : Assert sig n) (Q : X -> F -> Assert sig n) k :
(exists (x : X), TripleT P k pM (Q x)) ->
TripleT P k pM (fun yout tout => exists x : X, Q x yout tout).
Proof. setoid_rewrite TripleT_iff;setoid_rewrite Triple_iff. unfold Triple_Rel,Triple_TRel. firstorder. Qed.
Lemma TripleT_forall_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : X -> Assert sig n) (Q : F -> Assert sig n) k :
(exists (x : X), TripleT (P x) k pM Q) ->
TripleT (fun tin => forall x : X, P x tin) k pM (Q).
Proof. setoid_rewrite TripleT_iff;setoid_rewrite Triple_iff. unfold Triple_Rel,Triple_TRel. firstorder. Qed.
Lemma TripleT_forall_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(X : Type) (P : Assert sig n) (Q : X -> F -> Assert sig n) k {inhX: inhabitedC X} :
(forall (x : X), TripleT P k pM (Q x)) ->
TripleT P k pM (fun yout tout => forall x : X, Q x yout tout).
Proof.
intros H; split.
- apply Triple_forall_con. apply H.
- apply H. apply default.
Qed.
Lemma TripleT_eta_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q : F -> Assert sig n) k :
TripleT P k pM Q ->
TripleT (fun tin => P tin) k pM Q.
Proof. exact id. Qed.
Lemma TripleT_eta_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q : F -> Assert sig n) k :
TripleT P k pM Q ->
TripleT P k pM (fun yout => Q yout).
Proof. exact id. Qed.
Lemma TripleT_eta_con2 {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q : F -> Assert sig n) k :
TripleT P k pM Q ->
TripleT P k pM (fun yout tout => Q yout tout).
Proof. exact id. Qed.
Lemma TripleT_and_pre {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P1 : Assert sig n) (P2 : Prop) (Q : F -> Assert sig n) k :
(P2 -> TripleT P1 k pM Q) ->
TripleT (fun tin => P2 /\ P1 tin) k pM Q.
Proof. setoid_rewrite TripleT_iff;setoid_rewrite Triple_iff. unfold Triple_Rel,Triple_TRel. firstorder. Qed.
Lemma TripleT_and_con {sig : finType} {n : nat} {F : Type} (pM : pTM sig F n)
(P : Assert sig n) (Q1 : F -> Assert sig n) (Q2 : Prop) k :
TripleT P k pM Q1 ->
Q2 ->
TripleT P k pM (fun yout tout => Q2 /\ Q1 yout tout).
Proof. setoid_rewrite TripleT_iff;setoid_rewrite Triple_iff. unfold Triple_Rel,Triple_TRel. firstorder. Qed.