+include "basics/core_notation/fintersects_2.ma".
include "turing/mono.ma".
include "basics/vectors.ma".
record mTM (sig:FinSet) (tapes_no:nat) : Type[1] ≝
{ states : FinSet;
trans : states × (Vector (option sig) (S tapes_no)) →
- states × (Vector (option (sig × move))(S tapes_no));
+ states × (Vector ((option sig) × move) (S tapes_no));
start: states;
halt : states → bool
}.
definition current_chars ≝ λsig.λn.λtapes.
vec_map ?? (current sig) (S n) tapes.
+lemma nth_current_chars : ∀sig,n,tapes,i.
+ nth i ? (current_chars sig n tapes) (None ?)
+ = current sig (nth i ? tapes (niltape sig)).
+#sig #n #tapes #i >(nth_vec_map … (current sig) i (S n)) %
+qed.
+
+definition tape_move_multi ≝
+ λsig,n,ts,mvs.
+ pmap_vec ??? (tape_move_mono sig) n ts mvs.
+
+lemma tape_move_multi_def : ∀sig,n,ts,mvs.
+ tape_move_multi sig n ts mvs = pmap_vec ??? (tape_move_mono sig) n ts mvs.
+// qed.
+
definition step ≝ λsig.λn.λM:mTM sig n.λc:mconfig sig (states ?? M) n.
let 〈news,mvs〉 ≝ trans sig n M 〈cstate ??? c,current_chars ?? (ctapes ??? c)〉 in
- mk_mconfig ???
- news
- (pmap_vec ??? (tape_move sig) ? (ctapes ??? c) mvs).
+ mk_mconfig ??? news (tape_move_multi sig ? (ctapes ??? c) mvs).
definition empty_tapes ≝ λsig.λn.
mk_Vector ? n (make_list (tape sig) (niltape sig) n) ?.
definition nop ≝
λalpha:FinSet.λn.mk_mTM alpha n nop_states
- (λp.let 〈q,a〉 ≝ p in 〈q,mk_Vector ? (S n) (make_list ? (None ?) (S n)) ?〉)
+ (λp.let 〈q,a〉 ≝ p in 〈q,mk_Vector ? (S n) (make_list ? (〈None ?,N〉) (S n)) ?〉)
start_nop (λ_.true).
elim n normalize //
qed.
(************************** Sequential Composition ****************************)
definition null_action ≝ λsig.λn.
-mk_Vector ? (S n) (make_list (option (sig × move)) (None ?) (S n)) ?.
+mk_Vector ? (S n) (make_list (option sig × move) (〈None ?,N〉) (S n)) ?.
elim (S n) // normalize //
qed.
lemma tape_move_null_action: ∀sig,n,tapes.
- pmap_vec ??? (tape_move sig) (S n) tapes (null_action sig n) = tapes.
+ tape_move_multi sig (S n) tapes (null_action sig n) = tapes.
#sig #n #tapes cases tapes -tapes #tapes whd in match (null_action ??);
#Heq @Vector_eq <Heq -Heq elim tapes //
#a #tl #Hind whd in ⊢ (??%?); @eq_f2 // @Hind