VonNeumannCore: The Stored-Program Form, Verified in Lean 4 — An Interpreter Proved to Simulate Its Machine
In the stored-program architecture, instructions are data: a program resides in memory, and a single fetch–decode–execute interpreter runs whatever the memory holds. This paper presents VonNeumannCore, a Lean 4 development that turns this architecture into proved statements about a universal register machine. Each instruction is encoded into three memory cells (an opcode and two arguments); the encoding is proved faithful, in that decoding is its inverse (decode_encode) and the canonical memory image of a program decodes back to that program at every instruction (encodeMem_encodes). The interpreter, which reads its instruction from memory at each cycle and never writes to memory, is proved to simulate the directly executed machine step for step (vsim, vsim_iter): at every step count, interpreted and direct execution agree on the program counter and the registers, with the memory untouched. The machine's halting guarantee is then proved to transfer to interpreted execution (interpreter_halts), and the worked example is run from memory to the same proved final state as its direct execution (progZero_interpreted). The development is self-contained in core Lean, without Mathlib and without sorry; its checked axiom basis is [propext, Quot.sound].
Authors
- Takeo Yamamoto (ORCID: https://orcid.org/0009-0003-0440-474X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-14
- DOI
- https://doi.org/10.5281/zenodo.24215472
- Citations
- 1
- Primary Topic
- Logic, programming, and type systems
- Type
- preprint