0 Daumen
253 Aufrufe

Wir betrachten die aus der Vorlesung bekannte Ackermann-Funktion:

ack : N×NNack(n,m)={m+1 if n=0ack(n1,1) if n>0,m=0ack(n1,ack(n,m1)) if n>0,m>0 \begin{array}{ll} a c k: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} & \\ a c k(n, m)=\left\{\begin{array}{ll} m+1 & \text { if } n=0 \\ \operatorname{ack}(n-1,1) & \text { if } n>0, m=0 \\ \operatorname{ack}(n-1, \operatorname{ack}(n, m-1)) & \text { if } n>0, m>0 \end{array}\right. \end{array}
Beweisen Sie durch Noethersche Induktion über die lexikographische Ordnung der Argumente:
n,mN.m<ack(n,m) \forall n, m \in \mathbb{N} . m<a c k(n, m)



Problem/Ansatz:

Frage existiert bereits: Beweis durch Noethersche Induktion
Avatar von

Ein anderes Problem?

Stell deine Frage