Blank-Invariant Positional Codes for Finite Tapes
DefinitionMonodromy_TapeDefines positional codes for blank-padded half-tapes over a finite alphabet, with digit zero representing the blank and base one larger than the alphabet size. The encoding preserves tape cells and supports the arithmetic head, tail and tape-movement operations needed by the finite counter compiler.
-- Generated by Lean-fact skeleton subtraction; original source is frozen in imports/monodromy/source.
module
public import Mathlib.Computability.TuringMachine.PostTuringMachine
public import Mathlib.Data.Nat.Digits.Lemmas
@[expose] public section
/-!
# Canonical half-tape codes
Positional encoding descends to blank-padded tapes and preserves every cell.
-/
@[expose] public section
namespace Monodromy.TapeCode
open Turing
variable {a : ℕ} [NeZero a]
/-- Zero is the blank digit; appending blanks leaves this natural number unchanged. -/
def encode (tape : ListBlank (Fin a)) : ℕ :=
tape.liftOn (fun word => Nat.ofDigits (a + 1) (word.map Fin.val)) (by
rintro word _ ⟨count, rfl⟩
simp [List.map_append, List.map_replicate, Fin.default_eq_zero])
end Monodromy.TapeCode
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For every positive natural , a half-tape over digits is taken as a finite list modulo trailing copies of its distinguished blank digit . The definition assigns to such a tape represented by a word the natural number , using the digit values as naturals and base , so the first list entry is the least significant digit and the possible base digit is unused. Its supplied well-definedness proof states that appending any natural number of blank zeros leaves this value unchanged, allowing the function to descend to the blank-padded list quotient. Empty lists and all-blank representatives have code ; the case is included and then every symbol is the blank. The definition requires so that the finite symbol type has its distinguished zero element; no injectivity or cell-recovery theorem is declared in this bundle.
Confirmed by the mission captain (proposal self-audit).