proposition: Theorem reduction : TM.HaltTM 1 ⪯ SBTM_HALT.
proof: Proof. apply: (reduces_transitive Arbitrary_to_Binary.reduction). exists (fun '(M, t) => existT _ (M' M) (encode_config M (TM_facts.mk_mconfig (TM.start M) t))). move=> [M t]. split. - move=> /simulation [k Hk]. exists k. by move: Hk => /steps_truncate. - by move=> [k] /steps_truncate /inverse_simulation. Qed.
imports: Undecidability(TM.SBTM TM.Util.SBTM_facts) Undecidability.Shared.Libs.PSL.FiniteTypes.FinTypes PeanoNat Lia List ssreflect ssrbool ssrfun Undecidability.Synthetic.Definitions Undecidability.Synthetic.ReducibilityFacts