Primitiv rekursive Funktionen

Question 1

Primitiv rekursive Basisfunktionen

Answer 1

• Alle konstante Funktionen
• Alle identische Abbildungen(Projektion auf eine der Komponente)
• Die Nachfolgerfunktion succ(n) = n+1

Question 2

Jede Komposition von primitiv rekursiven Funktionen ist…

Answer 2

primitiv rekursiv

Question 3

Jede Funktion, die durch primitive Rekursion aus primitiv rekursiven Funktionen entsteht ist..

Answer 3

primitiv rekursiv

Question 4

Wenn g : N^(k) →N und h : N^(k+2) →N primitiv rekursiv, dann f : N^(k+1) →N primitiv rekursiv, mit den Regeln:

Answer 4

f(0, x_1, …, x_k) = g(x_1, … , x_k)

f(n+1, x_1, …, x_k) = h(n, f(n, x_1, …, x_k), x_1, …, x_k)

Question 5

Jede primitiv rekursive Funktion ist … und … .

Answer 5

berechenbar und total

Question 6

Additionsfunktion
add : N^(2) →N
add(x, y)= x+y

Answer 6

primitiv rekursiv

Question 7

Multiplikationsfunktion
mult : N^(2) →N
mult(x, y)= x∙y

Answer 7

primitiv rekursiv

Question 8

Vorgängerfunktion
pred : N →N
pred(x) = max {x-1, 0}

Answer 8

primitiv rekursiv

Question 9

Substraktionsfunktion
sub : N^(2) →N
sub(x, y) = x - ̇ y = max {x-y, 0}

Answer 9

primitiv rekursiv

Question 10

Signum
f : N → {0,1}
f(x) = [x ≥ 1]

Answer 10

primitiv rekursiv

Question 11

Gleichheit
f : N^(2) → {0,1}
f(x,y) = [x = y]

Answer 11

primitiv rekursiv

Question 12

Kleiner
f : N^(2) → {0,1}
f(x,y) = [x < y]

Answer 12

primitiv rekursiv

Question 13

Maximum
f : N^(2) → {0,1}
f(x,y) = max {x, y}

Answer 13

primitiv rekursiv

Question 14

Minimum
f : N^(2) → {0,1}
f(x,y) = min {x, y}

Answer 14

primitiv rekursiv

Question 15

Division
f : N^(2) → {0,1}
f(x,y) = ⌊x/y⌋

Answer 15

primitiv rekursiv

Question 16

Parität
f : N → {0,1}
f(x) = [x ungerade]

Answer 16

primitiv rekursiv

Question 17

Teilbarkeit
f : N^(2) → {0,1}
f(x,y) = [x|y]

Answer 17

primitiv rekursiv

Question 18

Primzahl
f : N → {0,1}
f(x) = [x prim]

Answer 18

primitiv rekursiv

Question 19

binom_2 : N → N

binom_2 (x) = 2-Combinations of x elements = [x(x-1)]/2

Answer 19

primitiv rekursiv

Question 20

β : N^(2) → N

β(x,y) =x + (2-Combinations of x+y+1 elements )

Answer 20

primitiv rekursiv

Bijektion zwischen N^(2) und N

Question 21

Umkehrfunktion der Bijektion β

Answer 21

γ : N → N primitiv rekursiv

γ(n) = h(n,n,n)

Question 22

Die Menge der primitiv rekursiven Funktionen fällt mit der Menge der … - berechenbare Funktionen zusammen.

Answer 22

LOOP und auch WHILE

Question 23

Definition: Es sei g : N^(k+1) → N ∪ {⊥} eine Funktion mit k+1 Argumenten. Durch Anwendung des μ-Operators auf g entsteht eine neue Funktion f : N^(k) → N ∪ {⊥} mit k Argumenten, wobei f(x_1, …, x_k) = …

Answer 23

= min {n | g(n,x_1, …, x_k)=0 und für alle m < n gilt g(m, x_1, …, x_k) ≠ ⊥}. Die entstehende Funktion f wird mit μg :N^(k) → N ∪ {⊥} bezeichnet.
(! Es gilt: min ∅ = ⊥)

Question 24

Die kleinste Klasse von Funktionen:

• die die Basisfunktionen enthält und
• die abgeschlossen ist unter Komposition, primitiver Rekursion und Anwendung des ….- Operators ist…

Answer 24

μ, die Klasse der μ-rekursiven Funktionen

Question 25

Die Klasse der μ-rekursiven Funktionen ist …

Answer 25

die kleinste Klasse von Funktionen:

• die die Basisfunktionen enthält und
• die abgeschlossen ist unter Komposition, primitiver Rekursion und Anwendung des μ-Operators

Question 26

WHILE Program die μ-rekursive Funktionen simuliert:

Answer 26

x_0 := 0;
y := g(0, x_1, ..., x_k);
WHILE y ≠ 0 DO 
      x_0 := x_0+1;
      y := g(x_0, x_1, ..., x_k);
ENDLOOP;

Question 27

μ-rekursive Funktionen sind…(Turing-mächtig/nicht Turing-mächtig)

Answer 27

Turing-mächtig

Question 28

primitiv rekursive Funktionen sind…(Turing-mächtig/nicht Turing-mächtig)

Answer 28

nicht Turing-mächtig

Question 29

Primitiv rekursive Funktionen sind..

Answer 29

eine Unterfamilie der Funktionen N^(k) → N mit k≥1.