caml-urm

A OCaml module for manipulating unlimited register machines

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, which is in turn based on that of Computability, An introduction to recursive function theory by Nigel J. Cutland. For example, the instruction set is given by:

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.