register machines
Summary
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.
Context
This concept has the prerequisites:
- Turing machines (To show counter machines are a universal computer, one shows they can simulate Turing machines.)
Goals
- 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)
-Paid-
→ 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
Other notes:
- 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
Other notes:
- See Section 6.1 for basic definitions and notation.
See also
-No Additional Notes-