Binary encodings of implicit parity systems
Lax119563.ImplicitSystemEncodings · concepts/Lax119563/ImplicitSystemEncodings.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An implicit parity system with coordinates is given to a Turing machine explicitly, as a list of natural numbers encoded as in the binary encodings of graph pairs.
- A block coordinate is written with fixed width, as its bits , and a coordinate as . Thus every coordinate and every shift listed in the input costs bits.
- A coordinate domain is described by followed by its coordinates, ordered by the numbers .
- A block-induced permutation is described by followed by .
- A binary schema is described by , the domain , and the permutations ; a ternary schema by , the domain, and .
- The initialization value is written , and the values are written .
The system is described by , then for each location its initialization value followed by its domain , then , and finally the descriptions of the schemas in order. Its bit length is the length of the binary code of this list; it accounts for the explicit domains, argument maps and initializations, including their indices.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Finset.Sort |
| 2 | import Lax119563.BinaryEncodings |
| 3 | import Lax119563.ImplicitParitySystems |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Binary encodings of implicit parity systems |
| 8 | type: definition |
| 9 | --- |
| 10 | An implicit parity system |
| 11 | with coordinates is given to a |
| 12 | Turing machine explicitly, as a list of natural numbers encoded as in the binary encodings of |
| 13 | graph pairs. |
| 14 | |
| 15 | * A block coordinate is written with fixed width, as its bits |
| 16 | , and a coordinate as . Thus |
| 17 | every coordinate and every shift listed in the input costs bits. |
| 18 | * A coordinate domain is described by followed by its |
| 19 | coordinates, ordered by the numbers . |
| 20 | * A block-induced permutation is described by |
| 21 | followed by . |
| 22 | * A binary schema is described by , the |
| 23 | domain , and the permutations ; a ternary schema |
| 24 | by , the domain, and |
| 25 | . |
| 26 | * The initialization value is written , and the values are written . |
| 27 | |
| 28 | The system is described by , then for each location |
| 29 | its initialization value followed by its domain , then , and |
| 30 | finally the descriptions of the schemas in order. Its *bit length* is the length of the |
| 31 | binary code of this list; it accounts for the explicit domains, argument maps and |
| 32 | initializations, including their indices. |
| 33 | |
| 34 | # Implementation notes |
| 35 | |
| 36 | The fixed width of block coordinates matters for running times: with a variable-length code |
| 37 | of block coordinates, small coordinates would be cheaper than the -bit coordinates |
| 38 | the matrix compiler has to compute from them, and would undercount the input. |
| 39 | -/ |
| 40 | |
| 41 | open Lax119563.ImplicitParitySystems Lax119563.BinaryEncodings |
| 42 | |
| 43 | namespace Lax119563.ImplicitSystemEncodings |
| 44 | |
| 45 | variable {k ℓ w : ℕ} |
| 46 | |
| 47 | /-- The number `∑_t b_t 2^t` of a block coordinate. -/ |
| 48 | def blockNum (b : BlockCoord ℓ) : ℕ := |
| 49 | ∑ t : Fin ℓ, (b t).val * 2 ^ (t : ℕ) |
| 50 | |
| 51 | /-- The number `i · 2^ℓ + b` of a coordinate `(i, b)`. -/ |
| 52 | def coordNum (c : Coord k ℓ) : ℕ := |
| 53 | (c.1 : ℕ) * 2 ^ ℓ + blockNum c.2 |
| 54 | |
| 55 | /-- The fixed-width description `b₀, …, b_{ℓ-1}` of a block coordinate. -/ |
| 56 | def blockDescription (b : BlockCoord ℓ) : List ℕ := |
| 57 | (List.finRange ℓ).map fun t => (b t).val |
| 58 | |
| 59 | /-- The description `i, b₀, …, b_{ℓ-1}` of the coordinate with number `c = i · 2^ℓ + b`. -/ |
| 60 | def coordNumDescription (ℓ c : ℕ) : List ℕ := |
| 61 | c / 2 ^ ℓ :: (List.range ℓ).map fun t => if c.testBit t then 1 else 0 |
| 62 | |
| 63 | /-- The description `|D|, c₁, …, c_{|D|}` of a coordinate domain, with the coordinates in |
| 64 | increasing order of their numbers. -/ |
| 65 | def domainDescription (D : Finset (Coord k ℓ)) : List ℕ := |
| 66 | let l := (D.image coordNum).sort (· ≤ ·) |
| 67 | l.length :: l.flatMap (coordNumDescription ℓ) |
| 68 | |
| 69 | /-- The description `f(0), …, f(k-1), δ₀, …, δ_{k-1}` of a block-induced permutation, with the |
| 70 | shifts written with fixed width. -/ |
| 71 | def permDescription (π : BlockPerm k ℓ) : List ℕ := |
| 72 | (List.finRange k).map (fun i => (π.perm i : ℕ)) ++ |
| 73 | (List.finRange k).flatMap (fun i => blockDescription (π.shift i)) |
| 74 | |
| 75 | /-- The description of an equation schema. -/ |
| 76 | def schemaDescription : Schema k ℓ w → List ℕ |
| 77 | | .binary u v D σ τ => |
| 78 | [2, (u : ℕ), (v : ℕ)] ++ domainDescription D ++ permDescription σ ++ permDescription τ |
| 79 | | .ternary u v w' D σ τ π => |
| 80 | [3, (u : ℕ), (v : ℕ), (w' : ℕ)] ++ domainDescription D ++ permDescription σ ++ |
| 81 | permDescription τ ++ permDescription π |
| 82 | |
| 83 | /-- The number of an initialization value: `⋆ ↦ 0`, `0 ↦ 1`, `1 ↦ 2`. -/ |
| 84 | def initNum : Option (ZMod 2) → ℕ |
| 85 | | none => 0 |
| 86 | | some b => b.val + 1 |
| 87 | |
| 88 | /-- The description of an implicit parity system as a list of natural numbers. -/ |
| 89 | def systemDescription (I : ImplicitParitySystem k ℓ) : List ℕ := |
| 90 | [k, ℓ, I.numLocations] ++ |
| 91 | (List.finRange I.numLocations).flatMap |
| 92 | (fun v => initNum (I.init v) :: domainDescription (I.domain v)) ++ |
| 93 | I.schemas.length :: I.schemas.flatMap schemaDescription |
| 94 | |
| 95 | /-- The binary encoding of an implicit parity system. -/ |
| 96 | def encodeSystem (I : ImplicitParitySystem k ℓ) : List Bool := |
| 97 | encodeNats (systemDescription I) |
| 98 | |
| 99 | /-- The bit length `H` of an implicit parity system. -/ |
| 100 | def bitLength (I : ImplicitParitySystem k ℓ) : ℕ := |
| 101 | (encodeSystem I).length |
| 102 | |
| 103 | end Lax119563.ImplicitSystemEncodings |
| 104 |
Implementation notes
The fixed width of block coordinates matters for running times: with a variable-length code of block coordinates, small coordinates would be cheaper than the -bit coordinates the matrix compiler has to compute from them, and would undercount the input.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments