Vorlesung10

Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind. Beispiel: p(n) = an^2 + bn + c.

Polynome bestehen aus den Rechenoperationen +, *, x^n.

Diese wurden bereits als primitiv rekursiv nachgewiesen. Deswegen kann man auch davon ausgehen, dass Polynome primitiv rekursiv sind.

Das Polynom könnte auch so dargestellt werden: p(n) = add(mult(a, pot(n, 2)),add(mult(b,n),c)).