proposition: Theorem Markov_Post : Markovs_princ -> Posts_thm.
proof: Proof. intros MP X P H1 H2 x. apply bi_rec_enum_t_dec; auto. destruct H1 as (f & Hf). destruct H2 as (g & Hg). set (h n := orb (f n x) (g n x)). assert (exists n, h n = true). { apply MP. assert (~~ (P x \/ ~ P x)) as H by tauto. do 2 contradict H. rewrite Hg, Hf in H. destruct H as [ (n & Hn) | (n & Hn) ]; exists n; unfold h; rewrite Hn; simpl; auto. destruct (f n x); simpl; auto. } destruct H as (n & Hn); unfold h in Hn. case_eq (f n x). + left; apply Hf; exists n; auto. + intros E; rewrite E in Hn; simpl in Hn. right; apply Hg; exists n; auto. Qed.
imports: List Arith Bool Lia Eqdep_dec Undecidability.Synthetic.Definitions Undecidability.Synthetic.ReducibilityFacts Undecidability.Synthetic.InformativeDefinitions Undecidability.Synthetic.InformativeReducibilityFacts Undecidability.Shared.Libs.DLW.Utils(utils_tac utils_list utils_nat finite) Undecidability.Shared.Libs.DLW.Vec(pos vec) Undecidability.FOL.TRAKHTENBROT(notations utils fol_ops decidable)