Lexikon der Mathematik: allgemein-rekursive Funktion
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 (n1,…, nk, m) die Gleichung „ f(n1,…, nk) = m“ aus G mittels der Einsetzungs- und der Ersetzungsregel ableiten läßt genau dann wenn f(n1,…, nk) = 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 t1 = t2 und f(x1,…, xn) = y vorliegen, sodann kann man die Gleichung \({t}_{1}^{\prime}} = {t}_{2}^{\prime}}\) ableiten, wobei \({t}_{1}^{\prime}}\), \({t}_{2}^{\prime}}\) aus t1, t2 hervorgehen, indem an einigen (nicht notwendigerweise allen) Stellen f(x1,…, xk) 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-Funktiona kann man beispielsweise folgendes Gleichungssystem angeben:
Durch Anwendungen der Einsetzungs- und der Ersetzungsregel läßt sich dann z. B. ableiten: a(1, 2) = 4, bzw. ausführlich:
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.