eine k-stellige Funktion f, k ≥ 0, für die es ein endliches Gleichungssystem G gibt, in dem „ f“ als Funktionsbezeichner vorkommt und sich für jedes (k + 1)-Tupel von natürlichen Zahlen (n ₁,…, n_k, m) die Gleichung „ f(n ₁,…, n_k) = m“ aus G mittels der Einsetzungs- und der Ersetzungsregel ableiten läßt genau dann wenn f(n ₁,…, n_k) = m gilt.

Hierbei bedeutet die Einsetzungsregel, daß man für alle Vorkommen einer bestimmten Variablen des Gleichungssystems eine Konstante einsetzt. Die Anwendung der Ersetzungsregel setzt voraus, daß bereits Gleichungen der Form t ₁ = t ₂ und f(x ₁,…, x_n) = y vorliegen, sodann kann man die Gleichung \({t}_{1}^{\prime}} = {t}_{2}^{\prime}}\) ableiten, wobei \({t}_{1}^{\prime}}\), \({t}_{2}^{\prime}}\) aus t ₁, t ₂ hervorgehen, indem an einigen (nicht notwendigerweise allen) Stellen f(x ₁,…, x_k) durch y ersetzt wird. Das Gleichungssystem G besteht aus einer endlichen Menge von Termgleichungen, wobei man die Terme aus den folgenden Primitiven aufbauen kann: Variablen, Konstanten (natürliche Zahlen), N (die Nachfolgerfunktion) und beliebigen weiteren Funktionsbezeichnern. (Die Konstanten sind hierbei nur als Abkürzungen für Terme der Form N(N(. . . N(0)…)) zu verstehen).

Dieses Konzept wurde von Gödel und Herbrand entwickelt und stellt eine weitere von vielen äquivalenten Möglichkeiten dar, den Berechenbarkeitsbegriff formal zu fassen (Berechnungstheorie, Churchsche These). Für die Ackermann-Funktion a kann man beispielsweise folgendes Gleichungssystem angeben: \begin{eqnarray}a(0,y) & = & N(y),\\ a(N(x),0) & = & a(x,N(0)),\\ a(N(x),N(y)) & = & a(x,a(N(x),y)).\end{eqnarray}

Durch Anwendungen der Einsetzungs- und der Ersetzungsregel läßt sich dann z. B. ableiten: a(1, 2) = 4, bzw. ausführlich: \begin{eqnarray}a(N(0),N(N(0)))=N(N(N(N(0)))).\end{eqnarray}