Binary encodings of numbers and graph pairs
Lax119563.BinaryEncodings · concepts/Lax119563/BinaryEncodings.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Inputs of Turing machines are bit strings. We encode a natural number by its binary digits , least significant first, writing each digit as the two bits and terminating with a single ; this code is self-delimiting and has length . A list of natural numbers is encoded by concatenating the codes of its entries.
A colored graph with vertices and edges is described by the list
where are its edges with , in lexicographic order. A pair is encoded by the code of the description of followed by that of . For graphs with vertices, edges, and colors below , the encoding has length .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Nat.Bits |
| 2 | import Mathlib.Data.List.FinRange |
| 3 | import Lax119563.ColoredGraphs |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Binary encodings of numbers and graph pairs |
| 8 | type: definition |
| 9 | --- |
| 10 | Inputs of Turing machines are bit strings. We encode a natural number by its binary |
| 11 | digits , least significant first, writing each digit as the two bits |
| 12 | and terminating with a single ; this code is self-delimiting and has length |
| 13 | . A list of natural numbers is encoded by concatenating |
| 14 | the codes of its entries. |
| 15 | |
| 16 | A colored graph with vertices and edges is described by the list |
| 17 | |
| 18 | where are its edges with , in lexicographic order. A pair |
| 19 | is encoded by the code of the description of followed by that of . For graphs |
| 20 | with vertices, edges, and colors below , the encoding has length |
| 21 | . |
| 22 | -/ |
| 23 | |
| 24 | open Lax119563.ColoredGraphs |
| 25 | |
| 26 | namespace Lax119563.BinaryEncodings |
| 27 | |
| 28 | /-- The self-delimiting binary code of a natural number: its binary digits `d`, least |
| 29 | significant first, each written as `true, d`, followed by `false`. -/ |
| 30 | def encodeNat (m : ℕ) : List Bool := |
| 31 | (Nat.bits m).flatMap (fun d => [true, d]) ++ [false] |
| 32 | |
| 33 | /-- The code of a list of natural numbers: the concatenation of the codes of its entries. -/ |
| 34 | def encodeNats (l : List ℕ) : List Bool := |
| 35 | l.flatMap encodeNat |
| 36 | |
| 37 | open Classical in |
| 38 | /-- The edges `(u, v)` with `u < v` of a colored graph, in lexicographic order. -/ |
| 39 | noncomputable def edgeList (G : ColoredGraph) : List (ℕ × ℕ) := |
| 40 | (List.finRange G.n).flatMap fun u => |
| 41 | ((List.finRange G.n).filter fun v => u < v ∧ G.graph.Adj u v).map fun v => ((u : ℕ), (v : ℕ)) |
| 42 | |
| 43 | /-- The description `n, χ(0), …, χ(n-1), m, u₁, v₁, …, u_m, v_m` of a colored graph. -/ |
| 44 | noncomputable def graphDescription (G : ColoredGraph) : List ℕ := |
| 45 | G.n :: (List.finRange G.n).map G.color ++ |
| 46 | (edgeList G).length :: (edgeList G).flatMap fun e => [e.1, e.2] |
| 47 | |
| 48 | /-- The binary encoding of a pair of colored graphs. -/ |
| 49 | noncomputable def encodeGraphPair (G H : ColoredGraph) : List Bool := |
| 50 | encodeNats (graphDescription G ++ graphDescription H) |
| 51 | |
| 52 | end Lax119563.BinaryEncodings |
| 53 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments