No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 2 of the paper of lax-242665, An Introduction to Lax
Definition
A word RAM is a random access machine whose writable memory consists of cells holding natural numbers below . The word length is a parameter; one finite program serves all word lengths. Input is a read-only finite array supplied at initialization, also accessible as a sequential tape. Output is an append-only tape. Working memory starts at zero and output starts empty.
The input interface has four operations. consumes the next entry of the sequential tape into cell , halting if the tape is empty. branches on tape emptiness without consuming input. writes the original input length into cell . reads the original input at the index in cell into cell , returning zero outside the input. Indexed access never consumes the sequential tape, and sequential reads never change the original input. Zero is ordinary data, not an end marker. Each operation costs one instruction. No length header or other framing is added to the supplied list.
Arithmetic results, input values and lengths, output values, and data-memory addresses are reduced modulo . Subtraction is truncated at zero, and division is integer division with . Input indices are words too. Program labels and the program counter are natural numbers and are not reduced modulo .
Lean source view on GitHub
| 1 | import Mathlib.Data.List.Basic |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The word RAM |
| 6 | type: definition |
| 7 | --- |
| 8 | A word RAM is a random access machine whose writable memory consists of |
| 9 | `2 ^ w` cells holding natural numbers below `2 ^ w`. The word length |
| 10 | `w` is a parameter; one finite program serves all word lengths. Input |
| 11 | is a read-only finite array supplied at initialization, also accessible |
| 12 | as a sequential tape. Output is an append-only tape. Working memory |
| 13 | starts at zero and output starts empty. |
| 14 | |
| 15 | The input interface has four operations. `read a` consumes the next |
| 16 | entry of the sequential tape into cell `a`, halting if the tape is |
| 17 | empty. `jeof l` branches on tape emptiness without consuming input. |
| 18 | `inputLength a` writes the original input length into cell `a`. |
| 19 | `inputLoad a b` reads the original input at the index in cell `b` into |
| 20 | cell `a`, returning zero outside the input. Indexed access never |
| 21 | consumes the sequential tape, and sequential reads never change the |
| 22 | original input. Zero is ordinary data, not an end marker. Each operation |
| 23 | costs one instruction. No length header or other framing is added to |
| 24 | the supplied list. |
| 25 | |
| 26 | Arithmetic results, input values and lengths, output values, and |
| 27 | data-memory addresses are reduced modulo `2 ^ w`. Subtraction is |
| 28 | truncated at zero, and division is integer division with `x / 0 = 0`. |
| 29 | Input indices are words too. Program labels and the program counter are |
| 30 | natural numbers and are not reduced modulo `2 ^ w`. |
| 31 | |
| 32 | # Formalization notes |
| 33 | |
| 34 | The register-transfer format follows Cook and Reckhow (*Time bounded |
| 35 | random access machines*, JCSS 7, 1973): instructions act on numbered |
| 36 | cells, with indirection through a cell holding an address. Their cells |
| 37 | hold signed integers, and their sequential input has a distinguished |
| 38 | zero end marker outside its input alphabet. This definition instead |
| 39 | uses unsigned words, supplies explicit EOF detection, and additionally |
| 40 | provides indexed read-only input with its length available in constant |
| 41 | time. It therefore specifies its own input convention; the interface |
| 42 | is not an identification with the original Cook--Reckhow input tape. |
| 43 | |
| 44 | Word operations have unit cost, as in the bounded-word models of |
| 45 | Fredman and Willard (*Surpassing the information theoretic bound with |
| 46 | fusion trees*, JCSS 47, 1993) and Hagerup (*Sorting and searching on the |
| 47 | word RAM*, STACS 1998). Comparisons with other word-RAM presentations |
| 48 | must fix the available operations, input convention, and address-space |
| 49 | assumptions. Indexed input avoids a compulsory input scan, as in an |
| 50 | input-array RAM. A simulation that instead starts from sequential input |
| 51 | and loads an `n`-word array pays an additive `O(n)` cost, giving |
| 52 | `O(n + T)`, which is `O(T)` only under a suitable lower bound on `T`. |
| 53 | No unconditional constant-factor model-equivalence claim is made here. |
| 54 | |
| 55 | `setCell` reduces each value stored and each destination address modulo |
| 56 | `2 ^ w`. Other data-memory operands and indirect addresses are reduced |
| 57 | at use; output and input values are reduced too. From initialization, |
| 58 | every reachable memory cell holds a word. The function representation |
| 59 | of memory has domain `ℕ`, but execution accesses only the residues below |
| 60 | `2 ^ w`. Program control is separate: `jump`, `jzero`, and `jeof` use |
| 61 | untruncated program labels, ordinary advancement increments the full |
| 62 | program counter, and instruction fetch uses that counter. |
| 63 | |
| 64 | Oversized input entries and the length are reduced rather than |
| 65 | rejected. To recover an entry unchanged requires that entry to be below |
| 66 | `2 ^ w`; to recover the complete original length with `inputLength` |
| 67 | requires `x.length < 2 ^ w`. These fitting conditions belong in the |
| 68 | admissible domain of the theorem that needs them. EOF-based programs |
| 69 | can process lists whose total length does not fit in a word. Indexed |
| 70 | reads can address the prefix with indices below `2 ^ w`; the initial |
| 71 | array itself is read-only input storage, separate from writable memory. |
| 72 | |
| 73 | Subtraction is natural-number monus, so a comparison is `sub` followed |
| 74 | by `jzero`. Complement is `2 ^ w - 1 - m[b]`. No instruction returns |
| 75 | the word length. The following operations are derived at constant cost, |
| 76 | with scratch cells `t` and `u` whose physical addresses modulo `2 ^ w` |
| 77 | are distinct from each other and from every operand's physical address. |
| 78 | Distinct natural-number literals alone do not ensure this condition: |
| 79 | |
| 80 | | operation | instructions | count | |
| 81 | |---|---|---| |
| 82 | | copy `a ← b` | `set t b; load a t` | 2 | |
| 83 | | `a ← b ∨ c` | `and t b c; sub t c t; add a b t` | 3 | |
| 84 | | `a ← b ⊕ c` | `and t b c; sub u c t; add u b u; sub a u t` | 4 | |
| 85 | | `a ← b ≫ c` | `set t 1; shiftl t t c; div a b t` | 3 | |
| 86 | | `a ← b mod c` | `div t b c; mul t t c; sub a b t` | 3 | |
| 87 | | if `b ≤ c` goto `l` | `sub t b c; jzero t l` | 2 | |
| 88 | | if `b < c` goto `l` | `sub t c b; jzero t l'; jump l; l':` | 3 | |
| 89 | | if `b = c` goto `l` | `sub t b c; sub u c b; add t t u; jzero t l` | 4 | |
| 90 | |
| 91 | An explicit `halt`, an exhausted `read`, or an out-of-range program |
| 92 | counter terminates execution. `step` returns `none` in all three cases. |
| 93 | `run w p k` counts successful transitions only. `RunsTo` adds the cost |
| 94 | of the fetched terminal instruction: one for `halt` or exhausted `read`, |
| 95 | and zero for an out-of-range counter, where no instruction exists. |
| 96 | Thus `RunsTo` counts every executed instruction exactly once, and an |
| 97 | empty program costs zero. Termination constrains the entire output |
| 98 | tape; memory is left unconstrained. |
| 99 | |
| 100 | The separate read-only input preserves a fixed working-memory layout. |
| 101 | An input-in-memory convention could also reserve fixed low-address |
| 102 | working cells and put input at a fixed base; no length-dependent input |
| 103 | base is necessary. Copying this model's input into writable memory, |
| 104 | when desired and when the chosen layout fits, takes constant overhead |
| 105 | per word and linear total time: a uniform loader uses `read` into a |
| 106 | temporary cell, an indirect `store`, and loop maintenance. |
| 107 | |
| 108 | There is no separate space measure or randomness primitive. A space |
| 109 | measure can be defined over executions; writable memory has `2 ^ w` |
| 110 | cells. A deterministic program can consume additional input words to |
| 111 | model supplied random choices. |
| 112 | -/ |
| 113 | |
| 114 | namespace Lax67.Ram |
| 115 | |
| 116 | /-- An instruction. Every number naming a cell is read, except that |
| 117 | the first one names the destination for instructions that write a cell, |
| 118 | and the cell holding the destination address for `store`. `set` carries |
| 119 | a literal value; `jump`, `jzero`, and `jeof` carry program labels, |
| 120 | which are not data-memory addresses. -/ |
| 121 | inductive Instr |
| 122 | /-- Set cell `a` to the literal `n`. -/ |
| 123 | | set (a n : ℕ) |
| 124 | /-- Set cell `a` to the contents of the cell whose address cell `b` |
| 125 | holds. -/ |
| 126 | | load (a b : ℕ) |
| 127 | /-- Set the cell whose address cell `a` holds to the contents of cell |
| 128 | `b`. -/ |
| 129 | | store (a b : ℕ) |
| 130 | /-- Set cell `a` to the sum of cells `b` and `c`, wrapping around |
| 131 | modulo `2 ^ w`. -/ |
| 132 | | add (a b c : ℕ) |
| 133 | /-- Set cell `a` to the difference of cells `b` and `c`, truncated at |
| 134 | zero rather than wrapping around. -/ |
| 135 | | sub (a b c : ℕ) |
| 136 | /-- Set cell `a` to the product of cells `b` and `c`, wrapping around |
| 137 | modulo `2 ^ w`. -/ |
| 138 | | mul (a b c : ℕ) |
| 139 | /-- Set cell `a` to the quotient of cells `b` and `c`, rounding |
| 140 | towards zero; division by zero yields zero. -/ |
| 141 | | div (a b c : ℕ) |
| 142 | /-- Set cell `a` to the bitwise conjunction of cells `b` and `c`. -/ |
| 143 | | and (a b c : ℕ) |
| 144 | /-- Set cell `a` to cell `b` shifted left by the number of bits cell |
| 145 | `c` holds, wrapping around modulo `2 ^ w`; a shift by `w` or more |
| 146 | yields zero. -/ |
| 147 | | shiftl (a b c : ℕ) |
| 148 | /-- Set cell `a` to the bitwise complement `2 ^ w - 1 - m[b]` of cell |
| 149 | `b` within the word length. -/ |
| 150 | | not (a b : ℕ) |
| 151 | /-- Continue at instruction `l`. -/ |
| 152 | | jump (l : ℕ) |
| 153 | /-- Continue at instruction `l` if cell `a` is zero. -/ |
| 154 | | jzero (a l : ℕ) |
| 155 | /-- Continue at instruction `l` exactly when the remaining input tape |
| 156 | is empty. This test does not consume input. -/ |
| 157 | | jeof (l : ℕ) |
| 158 | /-- Write the original input length, reduced to a word, into cell `a`. -/ |
| 159 | | inputLength (a : ℕ) |
| 160 | /-- Read original input at the word index in cell `b` into cell `a`, |
| 161 | returning zero outside the input. Read the index before writing `a`, |
| 162 | even when the two cell addresses coincide. Do not consume input. -/ |
| 163 | | inputLoad (a b : ℕ) |
| 164 | /-- Halt. -/ |
| 165 | | halt |
| 166 | /-- Read the next number of the input tape into cell `a`, or halt if |
| 167 | the tape is exhausted. -/ |
| 168 | | read (a : ℕ) |
| 169 | /-- Append the contents of cell `a` to the output tape. -/ |
| 170 | | write (a : ℕ) |
| 171 | |
| 172 | /-- A program: a finite sequence of instructions, numbered from `0`. -/ |
| 173 | abbrev Program : Type := List Instr |
| 174 | |
| 175 | /-- A machine state: the program counter, the contents of every memory |
| 176 | cell, the immutable original input array, the remaining sequential input |
| 177 | tape, and the output tape written so far. -/ |
| 178 | structure State where |
| 179 | /-- The number of the instruction to be executed next. -/ |
| 180 | pc : ℕ |
| 181 | /-- The contents of the memory cells; only the cells with number below |
| 182 | `2 ^ w` are ever addressed. -/ |
| 183 | mem : ℕ → ℕ |
| 184 | /-- The original read-only input, unchanged by every instruction. -/ |
| 185 | input : List ℕ |
| 186 | /-- The numbers still to be read from the input tape. -/ |
| 187 | inp : List ℕ |
| 188 | /-- The numbers written to the output tape so far. -/ |
| 189 | out : List ℕ |
| 190 | |
| 191 | /-- The memory `m` with cell `a` set to `v`, at word length `w`: the |
| 192 | address and the value written are both taken modulo `2 ^ w`. -/ |
| 193 | def setCell (w : ℕ) (m : ℕ → ℕ) (a v : ℕ) : ℕ → ℕ := |
| 194 | fun b => if b = a % 2 ^ w then v % 2 ^ w else m b |
| 195 | |
| 196 | /-- The effect of one instruction on the state at word length `w`, or |
| 197 | `none` if it halts the machine, which a `halt` instruction and a read |
| 198 | from an exhausted input tape do. Data values, input indices, and |
| 199 | data-memory addresses are reduced modulo `2 ^ w`; program labels and |
| 200 | the counter are not. -/ |
| 201 | def Instr.effect (w : ℕ) : Instr → State → Option State |
| 202 | | set a n, s => some { s with pc := s.pc + 1, mem := setCell w s.mem a n } |
| 203 | | load a b, s => |
| 204 | some |
| 205 | { s with |
| 206 | pc := s.pc + 1 |
| 207 | mem := setCell w s.mem a (s.mem (s.mem (b % 2 ^ w) % 2 ^ w)) } |
| 208 | | store a b, s => |
| 209 | some |
| 210 | { s with |
| 211 | pc := s.pc + 1 |
| 212 | mem := setCell w s.mem (s.mem (a % 2 ^ w)) (s.mem (b % 2 ^ w)) } |
| 213 | | add a b c, s => |
| 214 | some |
| 215 | { s with |
| 216 | pc := s.pc + 1 |
| 217 | mem := setCell w s.mem a (s.mem (b % 2 ^ w) + s.mem (c % 2 ^ w)) } |
| 218 | | sub a b c, s => |
| 219 | some |
| 220 | { s with |
| 221 | pc := s.pc + 1 |
| 222 | mem := setCell w s.mem a (s.mem (b % 2 ^ w) - s.mem (c % 2 ^ w)) } |
| 223 | | mul a b c, s => |
| 224 | some |
| 225 | { s with |
| 226 | pc := s.pc + 1 |
| 227 | mem := setCell w s.mem a (s.mem (b % 2 ^ w) * s.mem (c % 2 ^ w)) } |
| 228 | | div a b c, s => |
| 229 | some |
| 230 | { s with |
| 231 | pc := s.pc + 1 |
| 232 | mem := setCell w s.mem a (s.mem (b % 2 ^ w) / s.mem (c % 2 ^ w)) } |
| 233 | | and a b c, s => |
| 234 | some |
| 235 | { s with |
| 236 | pc := s.pc + 1 |
| 237 | mem := setCell w s.mem a (Nat.land (s.mem (b % 2 ^ w)) (s.mem (c % 2 ^ w))) } |
| 238 | | shiftl a b c, s => |
| 239 | some |
| 240 | { s with |
| 241 | pc := s.pc + 1 |
| 242 | mem := setCell w s.mem a (s.mem (b % 2 ^ w) * 2 ^ s.mem (c % 2 ^ w)) } |
| 243 | | not a b, s => |
| 244 | some |
| 245 | { s with |
| 246 | pc := s.pc + 1 |
| 247 | mem := setCell w s.mem a (2 ^ w - 1 - s.mem (b % 2 ^ w)) } |
| 248 | | jump l, s => some { s with pc := l } |
| 249 | | jzero a l, s => some { s with pc := if s.mem (a % 2 ^ w) = 0 then l else s.pc + 1 } |
| 250 | | jeof l, s => some { s with pc := if s.inp.isEmpty then l else s.pc + 1 } |
| 251 | | inputLength a, s => |
| 252 | some { s with pc := s.pc + 1, mem := setCell w s.mem a s.input.length } |
| 253 | | inputLoad a b, s => |
| 254 | some { s with |
| 255 | pc := s.pc + 1 |
| 256 | mem := setCell w s.mem a (s.input[s.mem (b % 2 ^ w) % 2 ^ w]?.getD 0) } |
| 257 | | halt, _ => none |
| 258 | | read a, s => |
| 259 | s.inp.head?.map fun v => |
| 260 | { s with pc := s.pc + 1, mem := setCell w s.mem a v, inp := s.inp.tail } |
| 261 | | write a, s => |
| 262 | some { s with pc := s.pc + 1, out := s.out ++ [s.mem (a % 2 ^ w) % 2 ^ w] } |
| 263 | |
| 264 | /-- One step of the machine at word length `w`: fetch the instruction |
| 265 | the program counter points at and execute it. The result is `none` if |
| 266 | the machine has halted, which also happens when the program counter has |
| 267 | run past the program. -/ |
| 268 | def step (w : ℕ) (p : Program) (s : State) : Option State := |
| 269 | p[s.pc]?.bind fun i => i.effect w s |
| 270 | |
| 271 | /-- The state after `t` successful transitions at word length `w`, or |
| 272 | `none` if one of those transitions terminates. This auxiliary count does |
| 273 | not include a fetched terminal instruction; `RunsTo` charges that too. -/ |
| 274 | def run (w : ℕ) (p : Program) : ℕ → State → Option State |
| 275 | | 0, s => some s |
| 276 | | t + 1, s => (step w p s).bind (run w p t) |
| 277 | |
| 278 | /-- The initial state on input `x`: program counter zero, all memory |
| 279 | cells zero, the original input array and its sequential tape both `x`, |
| 280 | and the output tape empty. -/ |
| 281 | def initState (x : List ℕ) : State where |
| 282 | pc := 0 |
| 283 | mem := fun _ => 0 |
| 284 | input := x |
| 285 | inp := x |
| 286 | out := [] |
| 287 | |
| 288 | /-- Cost of termination at `s`, when `step w p s = none`: a fetched |
| 289 | terminal instruction costs one, while an out-of-range program counter |
| 290 | costs zero because there is no instruction to execute. -/ |
| 291 | def terminalCost (p : Program) (s : State) : ℕ := |
| 292 | if s.pc < p.length then 1 else 0 |
| 293 | |
| 294 | /-- Started on input `x` at word length `w`, the machine executes |
| 295 | exactly `t` instructions and then halts, having written the word `y` to |
| 296 | its output tape. -/ |
| 297 | def RunsTo (w : ℕ) (p : Program) (x y : List ℕ) (t : ℕ) : Prop := |
| 298 | ∃ (k : ℕ) (s : State), run w p k (initState x) = some s ∧ |
| 299 | step w p s = none ∧ s.out = y ∧ t = k + terminalCost p s |
| 300 | |
| 301 | end Lax67.Ram |
| 302 |
Formalization notes
The register-transfer format follows Cook and Reckhow (Time bounded random access machines, JCSS 7, 1973): instructions act on numbered cells, with indirection through a cell holding an address. Their cells hold signed integers, and their sequential input has a distinguished zero end marker outside its input alphabet. This definition instead uses unsigned words, supplies explicit EOF detection, and additionally provides indexed read-only input with its length available in constant time. It therefore specifies its own input convention; the interface is not an identification with the original Cook–Reckhow input tape.
Word operations have unit cost, as in the bounded-word models of Fredman and Willard (Surpassing the information theoretic bound with fusion trees, JCSS 47, 1993) and Hagerup (Sorting and searching on the word RAM, STACS 1998). Comparisons with other word-RAM presentations must fix the available operations, input convention, and address-space assumptions. Indexed input avoids a compulsory input scan, as in an input-array RAM. A simulation that instead starts from sequential input and loads an -word array pays an additive cost, giving , which is only under a suitable lower bound on . No unconditional constant-factor model-equivalence claim is made here.
reduces each value stored and each destination address modulo . Other data-memory operands and indirect addresses are reduced at use; output and input values are reduced too. From initialization, every reachable memory cell holds a word. The function representation of memory has domain , but execution accesses only the residues below . Program control is separate: , , and use untruncated program labels, ordinary advancement increments the full program counter, and instruction fetch uses that counter.
Oversized input entries and the length are reduced rather than rejected. To recover an entry unchanged requires that entry to be below ; to recover the complete original length with requires . These fitting conditions belong in the admissible domain of the theorem that needs them. EOF-based programs can process lists whose total length does not fit in a word. Indexed reads can address the prefix with indices below ; the initial array itself is read-only input storage, separate from writable memory.
Subtraction is natural-number monus, so a comparison is followed by . Complement is . No instruction returns the word length. The following operations are derived at constant cost, with scratch cells and whose physical addresses modulo are distinct from each other and from every operand's physical address. Distinct natural-number literals alone do not ensure this condition:
| operation | instructions | count |
|---|---|---|
| copy | 2 | |
| 3 | ||
| 4 | ||
| 3 | ||
| 3 | ||
| if goto | 2 | |
| if goto | 3 | |
| if goto | 4 |
An explicit , an exhausted , or an out-of-range program counter terminates execution. returns in all three cases. counts successful transitions only. adds the cost of the fetched terminal instruction: one for or exhausted , and zero for an out-of-range counter, where no instruction exists. Thus counts every executed instruction exactly once, and an empty program costs zero. Termination constrains the entire output tape; memory is left unconstrained.
The separate read-only input preserves a fixed working-memory layout. An input-in-memory convention could also reserve fixed low-address working cells and put input at a fixed base; no length-dependent input base is necessary. Copying this model's input into writable memory, when desired and when the chosen layout fits, takes constant overhead per word and linear total time: a uniform loader uses into a temporary cell, an indirect , and loop maintenance.
There is no separate space measure or randomness primitive. A space measure can be defined over executions; writable memory has cells. A deterministic program can consume additional input words to model supplied random choices.
Builds on
none
From Mathlib
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments