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:
- Turing machines (To show counter machines are a universal computer, one shows they can simulate Turing machines.)
- 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)
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
- Section 8.5.3, "Counter machines," pages 358-359
- Section 8.5.4, "The power of counter machines," pages 359-361
- Earlier parts of Section 8.5 discuss constructions used in the Turing equivalence proof.
→ A Course in Mathematical Logic
A graduate textbook in mathematical logic.
- Section 6.2, "Algorithmic functions and functionals," pages 230-232
- Section 6.3, "The computer URIM," pages 232-237
- Section 6.4, "Computable functionals and functions," pages 237-239
- See Section 6.1 for basic definitions and notation.
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation