Direkt zum Inhalt

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 (n 1,…, nk, m) die Gleichung „ f(n 1,…, nk) = m“ aus G mittels der Einsetzungs- und der Ersetzungsregel ableiten läßt genau dann wenn f(n 1,…, 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 t 1 = t 2 und f(x 1,…, xn) = y vorliegen, sodann kann man die Gleichung \({t}_{1}^{\prime}} = {t}_{2}^{\prime}}\) ableiten, wobei \({t}_{1}^{\prime}}\), \({t}_{2}^{\prime}}\) aus t 1, t 2 hervorgehen, indem an einigen (nicht notwendigerweise allen) Stellen f(x 1,…, 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-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}

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos