Registermaschine/Berechenbare Funktion/Mehrstellig/Definition

Register-berechenbar

Eine ${}k$-stellige Funktion

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

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