# 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-