Canonical Numeric Tape Alphabet and Readout
DefinitionMonodromy_CanonicalIODefines the fixed finite stack-to-tape alphabet and its numeric readers. Binary symbols update a natural accumulator while blank and delimiter symbols leave it unchanged; natural-number input words and their decodings are connected to Mathlib’s stack-machine encoding.
-- Generated by Lean-fact skeleton subtraction; original source is frozen in imports/monodromy/source.
module
public import Definitions.Def_Monodromy_FormalCompilation
public import Lean.Elab.Tactic.Omega
public import Mathlib.Analysis.Analytic.Constructions
public import Mathlib.Analysis.Analytic.IsolatedZeros
public import Mathlib.Analysis.Analytic.Linear
public import Mathlib.Analysis.Calculus.DSlope
public import Mathlib.Analysis.Calculus.Deriv.Add
public import Mathlib.Analysis.Calculus.Deriv.Comp
public import Mathlib.Analysis.Calculus.Deriv.Mul
public import Mathlib.Analysis.Calculus.Deriv.Pow
public import Mathlib.Analysis.Complex.Basic
public import Mathlib.Analysis.Complex.CoveringMap
public import Mathlib.Analysis.Real.Pi.Bounds
public import Mathlib.Analysis.SpecialFunctions.Complex.Analytic
public import Mathlib.Analysis.SpecialFunctions.Complex.Circle
public import Mathlib.Computability.Primrec.List
public import Mathlib.Computability.StateTransition
public import Mathlib.Computability.TuringMachine.PostTuringMachine
public import Mathlib.Computability.TuringMachine.ToPartrec
public import Mathlib.Data.Fin.Basic
public import Mathlib.Data.Fintype.Card
public import Mathlib.Data.Fintype.EquivFin
public import Mathlib.Data.Fintype.Sets
public import Mathlib.Data.Nat.Digits.Lemmas
public import Mathlib.Data.Nat.Factorization.Basic
public import Mathlib.Logic.Equiv.Fin.Basic
public import Mathlib.Logic.Equiv.Fin.Rotate
public import Mathlib.Logic.Function.Basic
public import Mathlib.Logic.Function.Conjugate
public import Mathlib.RingTheory.RootsOfUnity.Complex
public import Mathlib.Tactic.FieldSimp
public import Mathlib.Tactic.FinCases
public import Mathlib.Tactic.FunProp
public import Mathlib.Tactic.Linarith
public import Mathlib.Tactic.Ring
public import Mathlib.Topology.Homotopy.Lifting
@[expose] public section
/-!
# A fixed numeric tape interface
Binary symbols carry the number; delimiters, blank columns and the stack
bottom marker leave the accumulator unchanged. The decoder is independent
of the source program and its control labels.
-/
@[expose] public section
namespace Monodromy.CanonicalIO
open Turing PartrecToTM2
abbrev Alphabet := TM2to1.Γ' K' (fun _ => Γ')
def readBit (value : ℕ) : Γ' → ℕ
| .bit0 => value + value
| .bit1 => value + value + 1
| .cons | .consₗ => value
def readSymbol (value : ℕ) (letter : Alphabet) : ℕ :=
match letter.2 .main with
| none => value
| some bit => readBit value bit
def decodeWord (word : List Alphabet) : ℕ := word.foldl readSymbol 0
def decodeBits (word : List Γ') : ℕ := word.foldr (fun bit value => readBit value bit) 0
@[simp] theorem read_blank (value : ℕ) : readSymbol value (default : Alphabet) = value := rfl
theorem fold_blank (count value : ℕ) :
(List.replicate count (default : Alphabet)).foldl readSymbol value = value := by
induction count generalizing value with
| zero => rfl
| succ count previous => simpa only [List.replicate_succ, List.foldl_cons, read_blank] using previous value
/-- Appending arbitrary blank padding leaves the fixed numeric readout unchanged. -/
theorem decode_blank_extension {first second : List Alphabet} (extension : BlankExtends first second) :
decodeWord first = decodeWord second := by
obtain ⟨count, rfl⟩ := extension
simp [decodeWord, List.foldl_append, fold_blank]
/-- The same readout is well-defined on the complete right half-tape. -/
def decodeTape (tape : ListBlank Alphabet) : ℕ :=
tape.liftOn decodeWord (fun _ _ extension => decode_blank_extension extension)
/-- One fixed finite coding is used for all tape-symbol computability statements. -/
noncomputable instance alphabetPrimcodable : Primcodable Alphabet :=
Primcodable.ofEquiv (Fin (Fintype.card Alphabet)) (Fintype.equivFin Alphabet)
def factor (letter : Alphabet) : ℕ :=
match letter.2 .main with
| some .bit0 | some .bit1 => 2
| _ => 1
def offset (letter : Alphabet) : ℕ :=
match letter.2 .main with
| some .bit1 => 1
| _ => 0
noncomputable instance symbolPrimcodable : Primcodable Γ' :=
Primcodable.ofEquiv (Fin (Fintype.card Γ')) (Fintype.equivFin Γ')
def increment : List Γ' → List Γ'
| [] => [.bit1]
| .bit0 :: tail => .bit1 :: tail
| .bit1 :: tail => .bit0 :: increment tail
| _ :: _ => [.bit1]
def incrementStep (state : Γ' × List Γ' × List Γ') : List Γ' :=
if state.1 = .bit0 then .bit1 :: state.2.1
else if state.1 = .bit1 then .bit0 :: state.2.2
else [.bit1]
/-- Packing a main-stack letter uses a fixed finite alphabet map. -/
def pack (bit : Γ') : Alphabet :=
(false, Function.update (fun _ => none) K'.main (some bit))
def bottomMarker (letter : Alphabet) : Alphabet := (true, letter.2)
def markBottom (word : List Alphabet) : List Alphabet :=
bottomMarker word.headI :: word.tail
end Monodromy.CanonicalIO
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
The alphabet here is the product of a Boolean marker with a function from the four track names main, reverse, auxiliary and stack to optional symbols from ; blank is false marker and all track symbols absent. For a natural accumulator , readBit maps to , to and either cons symbol to ; readSymbol applies that rule to the main-track symbol if present and otherwise returns , ignoring the marker and other tracks. decodeWord is the left fold of readSymbol from , whereas decodeBits is the right fold of readBit from , so the two folds have the explicitly different orders. The supplied equalities state that a blank leaves every accumulator unchanged, any finite repetition of blanks does so, and appending trailing blank padding preserves decodeWord; decodeTape therefore lifts decodeWord to half-tapes identified modulo trailing blanks. The alphabet and four-symbol type are given primitive-codable structures through chosen equivalences with finite initial segments of the naturals. factor is exactly for a main-track bit and otherwise; offset is exactly for a main-track bit1 and otherwise. increment on symbol lists sends the empty list to , changes a leading bit0 to bit1 with unchanged tail, changes a leading bit1 to bit0 followed by recursive increment of the tail, and sends any list headed by a cons symbol to . incrementStep takes a symbol and two symbol lists: on bit0 it prefixes bit1 to the first list, on bit1 it prefixes bit0 to the second, and otherwise returns . pack places a supplied symbol on the main track alone with marker false; bottomMarker changes only the marker to true; markBottom is bottomMarker of the default-valued head followed by the tail, so it produces a one-letter marked blank on an empty list rather than an empty list.
Confirmed by the mission captain (proposal self-audit).