Version history

Submission versions

Newest first. “Current version” is the latest registered successor; drafts are identified separately.

  1. lax-67viewingdraft

    The Word RAM

    GitHub sourceShown on this page
  2. lax-13current version

    The Word RAM

Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax67.Ram

The word RAM

concepts/Lax67/Ram.lean · lax-67

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimOpen claimDefinitionThis conceptRelated conceptA → B: B builds on A

    In the paper

    Definition

    A word RAM is a random access machine whose writable memory consists of 2w2 ^ w cells holding natural numbers below 2w2 ^ w. The word length ww 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. readaread a consumes the next entry of the sequential tape into cell aa, halting if the tape is empty. jeofljeof l branches on tape emptiness without consuming input. inputLengthainputLength a writes the original input length into cell aa. inputLoadabinputLoad a b reads the original input at the index in cell bb into cell aa, 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 2w2 ^ w. Subtraction is truncated at zero, and division is integer division with x/0=0x / 0 = 0. Input indices are words too. Program labels and the program counter are natural numbers and are not reduced modulo 2w2 ^ w.

    Lean source view on GitHub

    1import Mathlib.Data.List.Basic
    2
    3/-!
    4---
    5title: The word RAM
    6type: definition
    7---
    8A 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
    11is a read-only finite array supplied at initialization, also accessible
    12as a sequential tape. Output is an append-only tape. Working memory
    13starts at zero and output starts empty.
    14
    15The input interface has four operations. `read a` consumes the next
    16entry of the sequential tape into cell `a`, halting if the tape is
    17empty. `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
    20cell `a`, returning zero outside the input. Indexed access never
    21consumes the sequential tape, and sequential reads never change the
    22original input. Zero is ordinary data, not an end marker. Each operation
    23costs one instruction. No length header or other framing is added to
    24the supplied list.
    25
    26Arithmetic results, input values and lengths, output values, and
    27data-memory addresses are reduced modulo `2 ^ w`. Subtraction is
    28truncated at zero, and division is integer division with `x / 0 = 0`.
    29Input indices are words too. Program labels and the program counter are
    30natural numbers and are not reduced modulo `2 ^ w`.
    31
    32# Formalization notes
    33
    34The register-transfer format follows Cook and Reckhow (*Time bounded
    35random access machines*, JCSS 7, 1973): instructions act on numbered
    36cells, with indirection through a cell holding an address. Their cells
    37hold signed integers, and their sequential input has a distinguished
    38zero end marker outside its input alphabet. This definition instead
    39uses unsigned words, supplies explicit EOF detection, and additionally
    40provides indexed read-only input with its length available in constant
    41time. It therefore specifies its own input convention; the interface
    42is not an identification with the original Cook--Reckhow input tape.
    43
    44Word operations have unit cost, as in the bounded-word models of
    45Fredman and Willard (*Surpassing the information theoretic bound with
    46fusion trees*, JCSS 47, 1993) and Hagerup (*Sorting and searching on the
    47word RAM*, STACS 1998). Comparisons with other word-RAM presentations
    48must fix the available operations, input convention, and address-space
    49assumptions. Indexed input avoids a compulsory input scan, as in an
    50input-array RAM. A simulation that instead starts from sequential input
    51and 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`.
    53No 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
    57at use; output and input values are reduced too. From initialization,
    58every reachable memory cell holds a word. The function representation
    59of memory has domain `ℕ`, but execution accesses only the residues below
    60`2 ^ w`. Program control is separate: `jump`, `jzero`, and `jeof` use
    61untruncated program labels, ordinary advancement increments the full
    62program counter, and instruction fetch uses that counter.
    63
    64Oversized input entries and the length are reduced rather than
    65rejected. To recover an entry unchanged requires that entry to be below
    66`2 ^ w`; to recover the complete original length with `inputLength`
    67requires `x.length < 2 ^ w`. These fitting conditions belong in the
    68admissible domain of the theorem that needs them. EOF-based programs
    69can process lists whose total length does not fit in a word. Indexed
    70reads can address the prefix with indices below `2 ^ w`; the initial
    71array itself is read-only input storage, separate from writable memory.
    72
    73Subtraction is natural-number monus, so a comparison is `sub` followed
    74by `jzero`. Complement is `2 ^ w - 1 - m[b]`. No instruction returns
    75the word length. The following operations are derived at constant cost,
    76with scratch cells `t` and `u` whose physical addresses modulo `2 ^ w`
    77are distinct from each other and from every operand's physical address.
    78Distinct 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
    91An explicit `halt`, an exhausted `read`, or an out-of-range program
    92counter terminates execution. `step` returns `none` in all three cases.
    93`run w p k` counts successful transitions only. `RunsTo` adds the cost
    94of the fetched terminal instruction: one for `halt` or exhausted `read`,
    95and zero for an out-of-range counter, where no instruction exists.
    96Thus `RunsTo` counts every executed instruction exactly once, and an
    97empty program costs zero. Termination constrains the entire output
    98tape; memory is left unconstrained.
    99
    100The separate read-only input preserves a fixed working-memory layout.
    101An input-in-memory convention could also reserve fixed low-address
    102working cells and put input at a fixed base; no length-dependent input
    103base is necessary. Copying this model's input into writable memory,
    104when desired and when the chosen layout fits, takes constant overhead
    105per word and linear total time: a uniform loader uses `read` into a
    106temporary cell, an indirect `store`, and loop maintenance.
    107
    108There is no separate space measure or randomness primitive. A space
    109measure can be defined over executions; writable memory has `2 ^ w`
    110cells. A deterministic program can consume additional input words to
    111model supplied random choices.
    112-/
    113
    114namespace Lax67.Ram
    115
    116/-- An instruction. Every number naming a cell is read, except that
    117the first one names the destination for instructions that write a cell,
    118and the cell holding the destination address for `store`. `set` carries
    119a literal value; `jump`, `jzero`, and `jeof` carry program labels,
    120which are not data-memory addresses. -/
    121inductive 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`. -/
    173abbrev Program : Type := List Instr
    174
    175/-- A machine state: the program counter, the contents of every memory
    176cell, the immutable original input array, the remaining sequential input
    177tape, and the output tape written so far. -/
    178structure 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
    192address and the value written are both taken modulo `2 ^ w`. -/
    193def 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
    198from an exhausted input tape do. Data values, input indices, and
    199data-memory addresses are reduced modulo `2 ^ w`; program labels and
    200the counter are not. -/
    201def Instr.effect (w : ℕ) : InstrState → 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
    265the program counter points at and execute it. The result is `none` if
    266the machine has halted, which also happens when the program counter has
    267run past the program. -/
    268def 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
    273not include a fetched terminal instruction; `RunsTo` charges that too. -/
    274def 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
    279cells zero, the original input array and its sequential tape both `x`,
    280and the output tape empty. -/
    281def 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
    289terminal instruction costs one, while an out-of-range program counter
    290costs zero because there is no instruction to execute. -/
    291def 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
    295exactly `t` instructions and then halts, having written the word `y` to
    296its output tape. -/
    297def 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
    301end 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 nn-word array pays an additive O(n)O(n) cost, giving O(n+T)O(n + T), which is O(T)O(T) only under a suitable lower bound on TT. No unconditional constant-factor model-equivalence claim is made here.

    setCellsetCell reduces each value stored and each destination address modulo 2w2 ^ w. 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 N, but execution accesses only the residues below 2w2 ^ w. Program control is separate: jumpjump, jzerojzero, and jeofjeof 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 2w2 ^ w; to recover the complete original length with inputLengthinputLength requires x.length<2wx.length < 2 ^ w. 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 2w2 ^ w; the initial array itself is read-only input storage, separate from writable memory.

    Subtraction is natural-number monus, so a comparison is subsub followed by jzerojzero. Complement is 2w1m[b]2 ^ w - 1 - m[b]. No instruction returns the word length. The following operations are derived at constant cost, with scratch cells tt and uu whose physical addresses modulo 2w2 ^ w 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 aba ← b settb;loadatset t b; load a t 2
    abca ← b ∨ c andtbc;subtct;addabtand t b c; sub t c t; add a b t 3
    abca ← b ⊕ c andtbc;subuct;addubu;subautand t b c; sub u c t; add u b u; sub a u t 4
    abca ← b ≫ c sett1;shiftlttc;divabtset t 1; shiftl t t c; div a b t 3
    abmodca ← b mod c divtbc;multtc;subabtdiv t b c; mul t t c; sub a b t 3
    if bcb ≤ c goto ll subtbc;jzerotlsub t b c; jzero t l 2
    if b<cb < c goto ll subtcb;jzerotl;jumpl;l:sub t c b; jzero t l'; jump l; l': 3
    if b=cb = c goto ll subtbc;subucb;addttu;jzerotlsub t b c; sub u c b; add t t u; jzero t l 4

    An explicit halthalt, an exhausted readread, or an out-of-range program counter terminates execution. stepstep returns nonenone in all three cases. runwpkrun w p k counts successful transitions only. RunsToRunsTo adds the cost of the fetched terminal instruction: one for halthalt or exhausted readread, and zero for an out-of-range counter, where no instruction exists. Thus RunsToRunsTo 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 readread into a temporary cell, an indirect storestore, and loop maintenance.

    There is no separate space measure or randomness primitive. A space measure can be defined over executions; writable memory has 2w2 ^ w cells. A deterministic program can consume additional input words to model supplied random choices.

    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

    Loading discussion…