Es sei ${\displaystyle {}T\subseteq \mathbb {N} }$ eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge ${\displaystyle {}R}$-aufzählbar (oder Register-aufzählbar ) ist, wenn es ein Programm ${\displaystyle {}P}$ für eine Registermaschine gibt, die bei Eingabe von ${\displaystyle {}0}$ nach und nach genau die Zahlen aus ${\displaystyle {}T}$ ausdruckt (dabei dürfen Zahlen aus ${\displaystyle {}T}$ auch mehrfach ausgedruckt werden).