Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 22. September 2019 

Primitiv-rekursive Funktion


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Primitiv-rekursive Funktionen spielen in der Theoretischen Informatik eine Rolle insbesondere in Zusammenhang mit Berechenbarkeit .

Die Klasse <math>Pr</math> der primitiv-rekursiven Funktionen <math>\mathbb{N}^k \rightarrow \mathbb{N}</math>) umfasst:

  1. konstante Funktion: <math>f_c^k \left( n_1 ... n_k := c</math> <math>c \in \mathbb{N}</math>
  2. Projektion: <math>\pi_i^k \left( n_1 ... n_k \right) n_i</math> <math>1 \le i \le k</math>
  3. Nachfolgefunktion: <math>\nu \left( n \right) := n 1</math>
  4. Komposition: <math>f \left( n_1 ... n_k \right) g \left( h_1 \left( n_1 ... n_k ... h_m \left( n_1 ... n_k \right) falls <math>g h_1 ... h_m \in Pr</math>
  5. Primitive Rekursion: <math>f \left( 0 n_2 ... \right) := g \left( n_2 ... n_k <math>f \left( n_1 + 1 n_2 ... \right) := h \left( f \left( n_1 n_k \right) n_1 ... n_k \right)</math> falls g \in Pr</math>

Jede primitiv-rekursive Funktion ist LOOP-berechenbar (vgl. LOOP-Programm ) und umgekehrt.

Siehe auch: µ-Rekursion



Bücher zum Thema Primitiv-rekursive Funktion

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Primitiv-rekursive_Funktion.html">Primitiv-rekursive Funktion </a>