SE1: Aufgaben zur Parameterinduktion

Ich hatte ja noch versprochen die Aufgaben zur Parameterinduktion online zu stellen. Hier sind sie:

1
2
add x 0 = x
add x y = 1 + add x (y-1)

Behauptung: add x y = x + y

1
2
3
ack 0 m = m + 1
ack n 0 = ack (n-1) 1
ack n m = ack (n-1) (ack n (m-1))

Behauptung1: ack 1 m = m + 2
Behauptung2: ack 2 m = 2m + 3
Behauptung3: ack 3 m = 8 \cdot 2^m -3

Für die Behauptungen 2 und 3 können die vorherigen Behauptungen als gegeben angenommen werden.

Die Idee, die Ackermannfunktion als Aufgabe zu stellen, stammt übrigens nicht von mir, sondern von Jennifer. Das Schöne an dieser Aufgabe ist, dass sie zwar kompliziert aussieht, letztendlich aber gar nicht so schwer ist. Bietet also wunderbar die Möglichkeit die Angst vor der Parameterinduktion zu verlieren (sollte man sie denn haben).

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert