Blank virtual tape zigzag work-bit pattern
Definitionsgl_blank_workbitscomplexity-theorysipser-gacs-lautemannturing-machines
This module computes the exact zigzag work-bit pattern for the blank virtual tape at virtual head position . The marked head record is [true, false, false], and every subsequent blank record is [false, false, false]; consequently the work area for recordCount + 1 records is the head marker followed by 3 * recordCount false bits.
This identifies the precise finite bit string that the remaining scheduler/padding phase must create before handing control to the published left-zigzag simulator.
Definition code
import Definitions.Def_sgl_raw_archive_layout
namespace SipserGacsLautemann
theorem zigzagRecordBits_blank_zero :
zigzagRecordBits blankVirtualTape 0 0 =
[true, false, false] := by
rfl
theorem zigzagRecordBits_blank_succ (n : Nat) :
zigzagRecordBits blankVirtualTape 0 (n + 1) =
[false, false, false] := by
have hne : n + 1 ≠ 0 := Nat.succ_ne_zero n
simp only [zigzagRecordBits, zigzagRecordFlag,
zigzagRecordSymbol, blankVirtualTape, zigzagIndex,
hne, ↓reduceIte, decide_false, encodeTapeSymbol]
cases hcoord : zigzagCoordinate (n + 1) with
| ofNat coordinate =>
cases coordinate <;> rfl
| negSucc coordinate =>
rfl
theorem zigzagWorkBitsFrom_blank_succ_start
(start recordCount : Nat) :
zigzagWorkBitsFrom blankVirtualTape 0 (start + 1)
recordCount =
List.replicate (3 * recordCount) false := by
induction recordCount generalizing start with
| zero =>
rfl
| succ recordCount ih =>
rw [zigzagWorkBitsFrom_succ,
zigzagRecordBits_blank_succ start,
ih (start + 1)]
rw [show 3 * (recordCount + 1) =
3 + 3 * recordCount by omega]
rw [List.replicate_add]
rfl
theorem zigzagWorkBits_blank_succ (recordCount : Nat) :
zigzagWorkBits blankVirtualTape 0 (recordCount + 1) =
[true, false, false] ++
List.replicate (3 * recordCount) false := by
simp only [zigzagWorkBits, zigzagWorkBitsFrom_succ,
zigzagRecordBits_blank_zero]
rw [zigzagWorkBitsFrom_blank_succ_start 0 recordCount]
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; direct computation from the published zigzag simulator encoding.