Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Canonical Numeric Tape Alphabet and Readout

Definition
Monodromy_CanonicalIO

by Xiaoyang Liu · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitycovering-spacesmonodromy-computation

Defines 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.

Definition code
-- 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
Source
Authoritative local working-tree snapshot SHA-256 e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c; repository https://github.com/ERHUTUZI123/monodromy. The remote Git base is incomplete and is not asserted to contain these declarations. src/Monodromy/CanonicalIO.lean (file SHA-256 f4a53eb6dc2c54bd821f9eca4e2ac07619611d2794a5a065d4e940d1e16f627f): Monodromy.CanonicalIO.Alphabet at L21-L21 [UTF-8 464:511]. Monodromy.CanonicalIO.readBit at L23-L26 [UTF-8 513:640]. Monodromy.CanonicalIO.readSymbol at L28-L31 [UTF-8 642:779]. Monodromy.CanonicalIO.decodeWord at L33-L33 [UTF-8 781:851]. Monodromy.CanonicalIO.decodeBits at L35-L35 [UTF-8 853:944]. Monodromy.CanonicalIO.read_blank at L78-L78 [UTF-8 2662:2757]. Monodromy.CanonicalIO.fold_blank at L80-L84 [UTF-8 2759:3052]. Monodromy.CanonicalIO.decode_blank_extension at L86-L90 [UTF-8 3054:3379]. Monodromy.CanonicalIO.decodeTape at L92-L94 [UTF-8 3381:3586]. Monodromy.CanonicalIO.alphabetPrimcodable at L99-L101 [UTF-8 3701:3934]. Monodromy.CanonicalIO.factor at L103-L106 [UTF-8 3936:4047]. Monodromy.CanonicalIO.offset at L108-L111 [UTF-8 4049:4147]. Monodromy.CanonicalIO.symbolPrimcodable at L130-L131 [UTF-8 5034:5165]. Monodromy.CanonicalIO.increment at L133-L137 [UTF-8 5167:5324]. Monodromy.CanonicalIO.incrementStep at L151-L154 [UTF-8 5784:5963]. Monodromy.CanonicalIO.pack at L185-L187 [UTF-8 7104:7269]. Monodromy.CanonicalIO.bottomMarker at L189-L189 [UTF-8 7271:7338]. Monodromy.CanonicalIO.markBottom at L191-L192 [UTF-8 7340:7435].
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 {consL,cons,bit0,bit1}\{\mathrm{cons}_L,\mathrm{cons},\mathrm{bit0},\mathrm{bit1}\}{consL​,cons,bit0,bit1}; blank is false marker and all track symbols absent. For a natural accumulator vvv, readBit maps bit0\mathrm{bit0}bit0 to 2v2v2v, bit1\mathrm{bit1}bit1 to 2v+12v+12v+1 and either cons symbol to vvv; readSymbol applies that rule to the main-track symbol if present and otherwise returns vvv, ignoring the marker and other tracks. decodeWord is the left fold of readSymbol from 000, whereas decodeBits is the right fold of readBit from 000, 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 222 exactly for a main-track bit and 111 otherwise; offset is 111 exactly for a main-track bit1 and 000 otherwise. increment on symbol lists sends the empty list to [bit1][\mathrm{bit1}][bit1], 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 [bit1][\mathrm{bit1}][bit1]. 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 [bit1][\mathrm{bit1}][bit1]. 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.

Human review
  • Endorsed by marwahaha · Nov 6, 2026

  • Endorsed by Xiaoyang Liu · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me