Module: Mathlib.Computability.TuringMachine.StackTuringMachine

Goal state before:
pp: K : Type u_1
Γ : K → Type u_2
Λ : Type u_3
σ : Type u_4
inst✝ : DecidableEq K
M : Λ → TM2.Stmt Γ Λ σ
q : TM2.Stmt Γ Λ σ
v : σ
T : ListBlank ((i : K) → Option (Γ i))
k : K
S : (k : K) → List (Γ k)
hT : ∀ (k : K), ListBlank.map (proj k) T = ListBlank.mk (List.map some (S k)).reverse
o : StAct K Γ σ k
IH :
  ∀ {v : σ} {S : (k : K) → List (Γ k)} {T : ListBlank ((k : K) → Option (Γ k))},
    (∀ (k : K), ListBlank.map (proj k) T = ListBlank.mk (List.map some (S k)).reverse) →
      ∃ b,
        TrCfg (TM2.stepAux q v S) b ∧
          Reaches (TM1.step (tr M)) (TM1.stepAux (trNormal q) v (Tape.mk' ∅ (addBottom T))) b
hgo :
  Reaches₀ (TM1.step (tr M)) { l := some (go k o q), var := v, Tape := Tape.mk' ∅ (addBottom T) }
    { l := some (go k o q), var := v, Tape := (Tape.move Dir.right)^[(S k).length] (Tape.mk' ∅ (addBottom T)) }
T' : ListBlank ((k : K) → Option (Γ k))
hT' :
  ∀ (k_1 : K), ListBlank.map (proj k_1) T' = ListBlank.mk (List.map some (update S k (stWrite v (S k) o) k_1)).reverse
hrun :
  TM1.stepAux (trStAct (goto fun x x_1 ↦ ret q) o) v ((Tape.move Dir.right)^[(S k).length] (Tape.mk' ∅ (addBottom T))) =
    TM1.stepAux (goto fun x x_1 ↦ ret q) (stVar v (S k) o)
      ((Tape.move Dir.right)^[(update S k (stWrite v (S k) o) k).length] (Tape.mk' ∅ (addBottom T')))
this :
  Reaches₁ (TM1.step (tr M)) { l := some (go k o q), var := v, Tape := Tape.mk' ∅ (addBottom T) }
    { l := some (ret q), var := stVar v (S k) o,
      Tape := (Tape.move Dir.right)^[(update S k (stWrite v (S k) o) k).length] (Tape.mk' ∅ (addBottom T')) }
c : TM1.Cfg (Γ' K Γ) (Λ' K Γ Λ σ) σ
gc : TrCfg (TM2.stepAux q (stVar v (S k) o) (update S k (stWrite v (S k) o))) c
rc : Reaches (TM1.step (tr M)) (TM1.stepAux (trNormal q) (stVar v (S k) o) (Tape.mk' ∅ (addBottom T'))) c
⊢ ReflTransGen (fun a b ↦ b ∈ TM1.step (tr M) a)
    (bif true then TM1.stepAux (trNormal q) (stVar v (S k) o) (Tape.mk' ∅ (addBottom T'))
    else TM1.stepAux (move Dir.left (goto fun x x_1 ↦ ret q)) (stVar v (S k) o) (Tape.mk' ∅ (addBottom T')))
    c

Tactic:
]

Goal state after:
K : Type u_1
Γ : K → Type u_2
Λ : Type u_3
σ : Type u_4
inst✝ : DecidableEq K
M : Λ → TM2.Stmt Γ Λ σ
q : TM2.Stmt Γ Λ σ
v : σ
T : ListBlank ((i : K) → Option (Γ i))
k : K
S : (k : K) → List (Γ k)
hT : ∀ (k : K), ListBlank.map (proj k) T = ListBlank.mk (List.map some (S k)).reverse
o : StAct K Γ σ k
IH :
  ∀ {v : σ} {S : (k : K) → List (Γ k)} {T : ListBlank ((k : K) → Option (Γ k))},
    (∀ (k : K), ListBlank.map (proj k) T = ListBlank.mk (List.map some (S k)).reverse) →
      ∃ b,
        TrCfg (TM2.stepAux q v S) b ∧
          Reaches (TM1.step (tr M)) (TM1.stepAux (trNormal q) v (Tape.mk' ∅ (addBottom T))) b
hgo :
  Reaches₀ (TM1.step (tr M)) { l := some (go k o q), var := v, Tape := Tape.mk' ∅ (addBottom T) }
    { l := some (go k o q), var := v, Tape := (Tape.move Dir.right)^[(S k).length] (Tape.mk' ∅ (addBottom T)) }
T' : ListBlank ((k : K) → Option (Γ k))
hT' :
  ∀ (k_1 : K), ListBlank.map (proj k_1) T' = ListBlank.mk (List.map some (update S k (stWrite v (S k) o) k_1)).reverse
hrun :
  TM1.stepAux (trStAct (goto fun x x_1 ↦ ret q) o) v ((Tape.move Dir.right)^[(S k).length] (Tape.mk' ∅ (addBottom T))) =
    TM1.stepAux (goto fun x x_1 ↦ ret q) (stVar v (S k) o)
      ((Tape.move Dir.right)^[(update S k (stWrite v (S k) o) k).length] (Tape.mk' ∅ (addBottom T')))
this :
  Reaches₁ (TM1.step (tr M)) { l := some (go k o q), var := v, Tape := Tape.mk' ∅ (addBottom T) }
    { l := some (ret q), var := stVar v (S k) o,
      Tape := (Tape.move Dir.right)^[(update S k (stWrite v (S k) o) k).length] (Tape.mk' ∅ (addBottom T')) }
c : TM1.Cfg (Γ' K Γ) (Λ' K Γ Λ σ) σ
gc : TrCfg (TM2.stepAux q (stVar v (S k) o) (update S k (stWrite v (S k) o))) c
rc : Reaches (TM1.step (tr M)) (TM1.stepAux (trNormal q) (stVar v (S k) o) (Tape.mk' ∅ (addBottom T'))) c
⊢ ReflTransGen (fun a b ↦ b ∈ TM1.step (tr M) a)
    (bif true then TM1.stepAux (trNormal q) (stVar v (S k) o) (Tape.mk' ∅ (addBottom T'))
    else TM1.stepAux (move Dir.left (goto fun x x_1 ↦ ret q)) (stVar v (S k) o) (Tape.mk' ∅ (addBottom T')))
    c