+definition WRealize ≝ λsig.λM:TM sig.λR:relation (tape sig).
+∀t,i,outc.
+ loop ? i (step sig M) (λc.halt sig M (cstate ?? c)) (initc sig M t) = Some ? outc →
+ R t (ctape ?? outc).
+
+definition Terminate ≝ λsig.λM:TM sig.λt. ∃i,outc.
+ loop ? i (step sig M) (λc.halt sig M (cstate ?? c)) (initc sig M t) = Some ? outc.
+
+lemma WRealize_to_Realize : ∀sig.∀M: TM sig.∀R.
+ (∀t.Terminate sig M t) → WRealize sig M R → Realize sig M R.
+#sig #M #R #HT #HW #t cases (HT … t) #i * #outc #Hloop
+@(ex_intro … i) @(ex_intro … outc) % // @(HW … i) //
+qed.
+
+lemma loop_eq : ∀sig,f,q,i,j,a,x,y.
+ loop sig i f q a = Some ? x → loop sig j f q a = Some ? y → x = y.
+#sig #f #q #i #j @(nat_elim2 … i j)
+[ #n #a #x #y normalize #Hfalse destruct (Hfalse)
+| #n #a #x #y #H1 normalize #Hfalse destruct (Hfalse)
+| #n1 #n2 #IH #a #x #y normalize cases (q a) normalize
+ [ #H1 #H2 destruct %
+ | /2/ ]
+]
+qed.
+
+theorem Realize_to_WRealize : ∀sig,M,R.Realize sig M R → WRealize sig M R.
+#sig #M #R #H1 #inc #i #outc #Hloop
+cases (H1 inc) #k * #outc1 * #Hloop1 #HR
+>(loop_eq … Hloop Hloop1) //
+qed.
+
+definition accRealize ≝ λsig.λM:TM sig.λacc:states sig M.λRtrue,Rfalse:relation (tape sig).
+∀t.∃i.∃outc.
+ loop ? i (step sig M) (λc.halt sig M (cstate ?? c)) (initc sig M t) = Some ? outc ∧
+ (cstate ?? outc = acc → Rtrue t (ctape ?? outc)) ∧
+ (cstate ?? outc ≠ acc → Rfalse t (ctape ?? outc)).
+
+(* NO OPERATION
+
+ t1 = t2
+ *)
+
+definition nop_states ≝ initN 1.
+
+definition nop ≝
+ λalpha:FinSet.mk_TM alpha nop_states
+ (λp.let 〈q,a〉 ≝ p in 〈q,None ?〉)
+ O (λ_.true).
+
+definition R_nop ≝ λalpha.λt1,t2:tape alpha.t2 = t1.
+
+lemma sem_nop :
+ ∀alpha.Realize alpha (nop alpha) (R_nop alpha).
+#alpha #intape @(ex_intro ?? 1) @ex_intro [| % normalize % ]
+qed.
+