Eine ${\displaystyle {}k}$-stellige Funktion

${\displaystyle F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N} }$

heißt ${\displaystyle {}R}$-berechenbar (oder Register-berechenbar ), wenn es ein Programm ${\displaystyle {}P}$ für eine Registermaschine gibt, die bei jeder Eingabe ${\displaystyle {}(r_{1},\ldots ,r_{k})}$ (in den ersten ${\displaystyle {}k}$ Registern) anhält und ${\displaystyle {}F(r_{1},\ldots ,r_{k})}$ als (einzige) Ausgabe besitzt.