eine k-stellige Relation über den natürlichen Zahlen (k ≥ 1), deren charakteristische Funktion berechenbar ist (berechenbare Funktion).

Dies bedeutet, daß es einen Algorithmus gibt, der für jede Eingabe (n₁, …, n_k) in endlich vielen Schritten entscheidet, ob die Relation auf die Eingabe zutrifft oder nicht.