caml-urm

A OCaml module for manipulating unlimited register machines
README.md (1538B)

 1 # Urm
 2 
 3 A OCaml module for manipulating unlimited register machines.
 4 
 5 This module provides various types and functions for manipulating unlimited
 6 register machines (URMs). This implementation is besed on the specification
 7 provided in [Ramin Naimi's URM
 8 simulator](https://sites.oxy.edu/rnaimi/home/URMsim.htm), which is in turn
 9 based on that of [Computability, An introduction to recursive function
10 theory](https://doi.org/10.1017/CBO9781139171496) by Nigel J. Cutland. For
11 example, the instruction set is given by:
12 
13 * `T(n, m)` transfers the contents of the `n`-th register to `m`-th register.
14 * `Z(n)` sets the value of the `n`-th register to zero.
15 * `S(n)` increments the value of the `n`-th register.
16 * `P(n)` decrements the value of the `n`-th register.
17 * `J(n, m, i)` jumps to the `i`-th instruction if the values of the `n`-th and
18   `m`-th coincide. The instruction count starts at 1, so `i = 1` jumps to the
19   first instruction.
20 
21 The register set, however, is a bit different. In Nigel's specification the
22 registers are indexed by natural numbers (starting from 1), while in this
23 implementation the registers are indexed by arbitrary integers. Also, in
24 Nigel's specification store natural numbers (starting from 0) and in this
25 implementation they store arbitrary integers. Good luck getting a negative
26 integer from a machine whose registers are initially set to natural numbers
27 though.
28 
29 ## Documentation
30 
31 See `docs.pdf` for further documentation.
32 
33 ## Dependencies
34 
35 * [camlp-streams](https://opam.ocaml.org/packages/camlp-streams/)