register machines


Register machines are a model of computation involving a set of registers which can hold arbitrarily large positive integers. Despite the model's simplicity, it is Turing complete. The simplicity of the definition is helpful in computability theory, because reductions from counter machines can be easier than reductions from Turing machines.


This concept has the prerequisites:


  • Define a register machine (there are many variants which are Turing complete)
  • Be able to write programs to compute simple functions
  • Show that register machines are Turing-complete

Core resources (read/watch one of the following)


See also

-No Additional Notes-