Skip to content
  1. CLRS-Lean
  2. Chapter 34. NP-Completeness
  3. 34.4. NP-Completeness Proofs
  4. 34.4. Verified bounded TM2 builders
  5. 34.4. Exact simulation of quoted delimiter materialization
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.PolyBuilder.UnaryFrameMarkedRowQuotedDelimiterMapCore import Mathlib.Tactic

Exact simulation of quoted delimiter materialization

noncomputable sectionopen StateTransitionnamespace CLRS.Chapter34.Turing.PolyBuilder

Exact instruction count. Payload symbols use one pop and two output pushes; a reserved row boundary uses one pop and one output push.

def unaryFrameQuotedDelimiterMapSteps : List UnaryFrameSym → Nat | [] => 2 | .tick :: rest => unaryFrameQuotedDelimiterMapSteps rest + 3 | .separator :: rest => unaryFrameQuotedDelimiterMapSteps rest + 3 | .frameEnd :: rest => unaryFrameQuotedDelimiterMapSteps rest + 2

Exact run from any cyclic delimiter position and any accumulated reversed output.

def unaryFrameQuotedDelimiterMap_scan_run (delimiters : List UnaryFrameSym) (hnonempty : 0 < delimiters.length) (index : Fin delimiters.length) (buffer : Option UnaryFrameSym) (input output : List UnaryFrameSym) : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) (unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan index) buffer input output) (some (haltCfg (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty) ((rewriteUnaryFrameQuotedDelimitersFrom delimiters hnonempty index input).reverse ++ output))) (unaryFrameQuotedDelimiterMapSteps input) := by induction input generalizing index buffer output with | nil => refine ⟨⟨2, ?_⟩, le_rfl⟩ rfl | cons symbol rest ih => cases symbol with | tick => let afterPop := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.emitFirst index .tick) (some .tick) rest output let afterFirst := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.emitSecond index .tick) (some .tick) rest (quoteUnaryFrameFirst .tick :: output) let afterSecond := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan index) (some .tick) rest (quoteUnaryFrameSecond .tick :: quoteUnaryFrameFirst .tick :: output) have hpop : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) (unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan index) buffer (.tick :: rest) output) (some afterPop) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have hfirst : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) afterPop (some afterFirst) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have hsecond : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) afterFirst (some afterSecond) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have htail := ih index (some .tick) (quoteUnaryFrameSecond .tick :: quoteUnaryFrameFirst .tick :: output) let h₁ := EvalsToInTime.trans _ 1 1 _ afterPop _ hpop hfirst let h₂ := EvalsToInTime.trans _ 2 1 _ afterFirst _ h₁ hsecond let full := EvalsToInTime.trans _ 3 (unaryFrameQuotedDelimiterMapSteps rest) _ afterSecond _ h₂ htail convert full using 1 <;> simp [This simp argument is unused: afterSecond Hint: Omit it from the simp argument list. simp [̵a̵f̵t̵e̵r̵S̵e̵c̵o̵n̵d̵,̵ ̵r̵e̵w̵r̵i̵t̵e̵U̵n̵a̵r̵y̵F̵r̵a̵m̵e̵Q̵u̵o̵t̵e̵d̵D̵e̵l̵i̵m̵i̵t̵e̵r̵s̵F̵r̵o̵m̵,̵[̲r̲e̲w̲r̲i̲t̲e̲U̲n̲a̲r̲y̲F̲r̲a̲m̲e̲Q̲u̲o̲t̲e̲d̲D̲e̲l̲i̲m̲i̲t̲e̲r̲s̲F̲r̲o̲m̲,̲ quoteUnaryFrameSym_eq_pair, ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲List.reverse_append, List.append_assoc, unaryFrameQuotedDelimiterMapSteps] Note: This linter can be disabled with `set_option linter.unusedSimpArgs false`afterSecond, rewriteUnaryFrameQuotedDelimitersFrom, quoteUnaryFrameSym_eq_pair, This simp argument is unused: List.reverse_append Hint: Omit it from the simp argument list. simp [afterSecond, rewriteUnaryFrameQuotedDelimitersFrom, quoteUnaryFrameSym_eq_pair, ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲L̵i̵s̵t̵.̵r̵e̵v̵e̵r̵s̵e̵_̵a̵p̵p̵e̵n̵d̵,̵List.append_assoc, unaryFrameQuotedDelimiterMapSteps] Note: This linter can be disabled with `set_option linter.unusedSimpArgs false`List.reverse_append, List.append_assoc, unaryFrameQuotedDelimiterMapSteps] <;> 'omega' tactic does nothing Note: This linter can be disabled with `set_option linter.unusedTactic false`this tactic is never executed Note: This linter can be disabled with `set_option linter.unreachableTactic false`omega | separator => let nextIndex := unaryFrameDelimiterNext delimiters hnonempty index let materialized := delimiters.get index let afterPop := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.emitFirst nextIndex materialized) (some .separator) rest output let afterFirst := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.emitSecond nextIndex materialized) (some .separator) rest (quoteUnaryFrameFirst materialized :: output) let afterSecond := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan nextIndex) (some .separator) rest (quoteUnaryFrameSecond materialized :: quoteUnaryFrameFirst materialized :: output) have hpop : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) (unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan index) buffer (.separator :: rest) output) (some afterPop) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have hfirst : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) afterPop (some afterFirst) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have hsecond : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) afterFirst (some afterSecond) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have htail := ih nextIndex (some .separator) (quoteUnaryFrameSecond materialized :: quoteUnaryFrameFirst materialized :: output) let h₁ := EvalsToInTime.trans _ 1 1 _ afterPop _ hpop hfirst let h₂ := EvalsToInTime.trans _ 2 1 _ afterFirst _ h₁ hsecond let full := EvalsToInTime.trans _ 3 (unaryFrameQuotedDelimiterMapSteps rest) _ afterSecond _ h₂ htail convert full using 1 <;> simp [This simp argument is unused: afterSecond Hint: Omit it from the simp argument list. simp [̵a̵f̵t̵e̵r̵S̵e̵c̵o̵n̵d̵,̵ ̵n̵e̵x̵t̵I̵n̵d̵e̵x̵,̵[̲n̲e̲x̲t̲I̲n̲d̲e̲x̲,̲ materialized, rewriteUnaryFrameQuotedDelimitersFrom, quoteUnaryFrameSym_eq_pair, List.reverse_append, List.append_assoc, ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲unaryFrameQuotedDelimiterMapSteps] Note: This linter can be disabled with `set_option linter.unusedSimpArgs false`afterSecond, nextIndex, materialized, rewriteUnaryFrameQuotedDelimitersFrom, quoteUnaryFrameSym_eq_pair, This simp argument is unused: List.reverse_append Hint: Omit it from the simp argument list. simp [afterSecond, nextIndex, materialized, rewriteUnaryFrameQuotedDelimitersFrom, quoteUnaryFrameSym_eq_pair, L̵i̵s̵t̵.̵r̵e̵v̵e̵r̵s̵e̵_̵a̵p̵p̵e̵n̵d̵,̵List.append_assoc, unaryFrameQuotedDelimiterMapSteps] Note: This linter can be disabled with `set_option linter.unusedSimpArgs false`List.reverse_append, List.append_assoc, unaryFrameQuotedDelimiterMapSteps] <;> this tactic is never executed Note: This linter can be disabled with `set_option linter.unreachableTactic false`'omega' tactic does nothing Note: This linter can be disabled with `set_option linter.unusedTactic false`omega | frameEnd => let afterPop := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.emitBoundary index) (some .frameEnd) rest output let afterBoundary := unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan index) (some .frameEnd) rest (.frameEnd :: output) have hpop : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) (unaryFrameQuotedDelimiterMapCfg delimiters hnonempty (.scan index) buffer (.frameEnd :: rest) output) (some afterPop) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have hboundary : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) afterPop (some afterBoundary) 1 := ⟨⟨1, rfl⟩, le_rfl⟩ have htail := ih index (some .frameEnd) (.frameEnd :: output) let hprefix := EvalsToInTime.trans _ 1 1 _ afterPop _ hpop hboundary let full := EvalsToInTime.trans _ 2 (unaryFrameQuotedDelimiterMapSteps rest) _ afterBoundary _ hprefix htail convert full using 1 <;> simp [This simp argument is unused: afterBoundary Hint: Omit it from the simp argument list. simp [̵a̵f̵t̵e̵r̵B̵o̵u̵n̵d̵a̵r̵y̵,̵ ̵r̵e̵w̵r̵i̵t̵e̵U̵n̵a̵r̵y̵F̵r̵a̵m̵e̵Q̵u̵o̵t̵e̵d̵D̵e̵l̵i̵m̵i̵t̵e̵r̵s̵F̵r̵o̵m̵,̵[̲r̲e̲w̲r̲i̲t̲e̲U̲n̲a̲r̲y̲F̲r̲a̲m̲e̲Q̲u̲o̲t̲e̲d̲D̲e̲l̲i̲m̲i̲t̲e̲r̲s̲F̲r̲o̲m̲,̲ List.append_assoc, ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲unaryFrameQuotedDelimiterMapSteps] Note: This linter can be disabled with `set_option linter.unusedSimpArgs false`afterBoundary, rewriteUnaryFrameQuotedDelimitersFrom, List.append_assoc, unaryFrameQuotedDelimiterMapSteps] <;> this tactic is never executed Note: This linter can be disabled with `set_option linter.unreachableTactic false`'omega' tactic does nothing Note: This linter can be disabled with `set_option linter.unusedTactic false`omega

Exact reversed-output run from the public initial configuration.

def unaryFrameQuotedDelimiterMapRev_run (delimiters : List UnaryFrameSym) (hnonempty : 0 < delimiters.length) (input : List UnaryFrameSym) : EvalsToInTime (step (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty)) (initialCfg (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty) input) (some (haltCfg (unaryFrameQuotedDelimiterMapRevProgram delimiters hnonempty) (rewriteUnaryFrameQuotedDelimiters delimiters hnonempty input).reverse)) (unaryFrameQuotedDelimiterMapSteps input) := by simpa [initialCfg, rewriteUnaryFrameQuotedDelimiters, unaryFrameQuotedDelimiterMapRevProgram, unaryFrameQuotedDelimiterMapCfg] using unaryFrameQuotedDelimiterMap_scan_run delimiters hnonempty ⟨0, hnonempty⟩ none input []
end CLRS.Chapter34.Turing.PolyBuilder