Stream

formal source

  13open Finset
  14
  15/-- Boolean stream as an infinite display. -/
  16def Stream := Nat → Bool
  17
  18/-- A finite window/pattern of length `n`. -/
  19def Pattern (n : Nat) := Fin n → Bool
  20
  21/-- Integer functional `Z` counting ones in a finite window. -/
  22def Z_of_window {n : Nat} (w : Pattern n) : Nat :=
  23  ∑ i : Fin n, (if w i then 1 else 0)
  24
  25/-- The cylinder set of streams whose first `n` bits coincide with the window `w`. -/
  26def Cylinder {n : Nat} (w : Pattern n) : Set Stream :=
  27  { s | ∀ i : Fin n, s i.val = w i }
  28
  29/-- Periodic extension of an 8‑bit window. -/
  30def extendPeriodic8 (w : Pattern 8) : Stream := fun t =>
  31  let i : Fin 8 := ⟨t % 8, Nat.mod_lt _ (by decide)⟩
  32  w i
  33
  34/-- Sum of the first `m` bits of a stream. -/
  35def sumFirst (m : Nat) (s : Stream) : Nat :=
  36  ∑ i : Fin m, (if s i.val then 1 else 0)
  37
  38/-- If a stream agrees with a window on its first `n` bits, then the first‑`n` sum equals `Z`. -/
  39lemma sumFirst_eq_Z_on_cylinder {n : Nat} (w : Pattern n)
  40  {s : Stream} (hs : s ∈ Cylinder w) :
  41  sumFirst n s = Z_of_window w := by
  42  classical
  43  unfold sumFirst Z_of_window Cylinder at *
  44  have : (fun i : Fin n => (if s i.val then 1 else 0)) =
  45         (fun i : Fin n => (if w i then 1 else 0)) := by
  46    funext i; simpa [hs i]