caml-urm

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# Urm

A OCaml module for manipulating unlimited register machines.

This module provides various types and functions for manipulating unlimited
register machines (URMs). This implementation is besed on the specification
provided in [Ramin Naimi's URM
simulator](https://sites.oxy.edu/rnaimi/home/URMsim.htm), which is in turn
based on that of [Computability, An introduction to recursive function
theory](https://doi.org/10.1017/CBO9781139171496) by Nigel J. Cutland. For
example, the instruction set is given by:

* `T(n, m)` transfers the contents of the `n`-th register to `m`-th register.
* `Z(n)` sets the value of the `n`-th register to zero.
* `S(n)` increments the value of the `n`-th register.
* `P(n)` decrements the value of the `n`-th register.
* `J(n, m, i)` jumps to the `i`-th instruction if the values of the `n`-th and
  `m`-th coincide. The instruction count starts at 1, so `i = 1` jumps to the
  first instruction.

The register set, however, is a bit different. In Nigel's specification the
registers are indexed by natural numbers (starting from 1), while in this
implementation the registers are indexed by arbitrary integers. Also, in
Nigel's specification store natural numbers (starting from 0) and in this
implementation they store arbitrary integers. Good luck getting a negative
integer from a machine whose registers are initially set to natural numbers
though.

## Documentation

See `docs.pdf` for further documentation.

## Dependencies

* [camlp-streams](https://opam.ocaml.org/packages/camlp-streams/)